Написание простого алгоритма сортировки на c ++ вместе с версией псевдокода
Я пытаюсь написать алгоритм сортировки сортов в C ++, а затем записать его в псевдокоде, после чего, теперь писать его в псевдо-коде не так уж и плохо, однако получение его в моей голове превращается в борьбу, поэтому Вопрос, который я задаю вам, ребята:
Я ищу, чтобы создать алгоритм, который принимает несортированный массив вместе с двумя целыми числами (скажем, B и C) и выводит TRUE, если A содержит элемент, который больше, чем B, и меньше, чем C, в противном случае он возвращает FALSE.
For J <-- 1 to Length[A]
Count <-- j+1
while Count =< Length[A]
Это мой старт для псевдокода, потому что это кажется логичным для начала, а затем реализовать его в C ++. Однако я обнаружил, что вращаюсь по кругу, создавая циклы и не добиваясь большого прогресса. Надеюсь, что все, что я сказал, имеет смысл, и кто-то может собрать все это вместе, чтобы создать какую-то форму решения. Благодарю.
Решение
Из того, что я помню из Стива Макконнелла Код завершен, Ваш псевдокод в идеале должен выглядеть больше как английский, чем он. Ты слишком быстро прыгаешь к реализации, по моему скромному мнению.
Как насчет этого:
for each element in array
check to see if element is between B and C
if element is between B and C
return TRUE
else
continue loop
next
return FALSE
Вот что я понял из вашего заявления:
Я ищу, чтобы создать алгоритм, который принимает несортированный массив, а также
с двумя целыми числами (скажем, B и C) и выводит TRUE, если A содержит
элемент, который больше, чем B, и меньше, чем C, в противном случае он
возвращает ЛОЖЬ.
Другие решения
Я бы начал с функции для проверки состояния, которое вас волнует: с учетом числа оно попадает в указанный диапазон:
boolean function in_range(A, B, C) {
return (A > B) and (A < C);
}
Оттуда становится просто сканировать массив и вызывать функцию, передавая каждый элемент массива как A (и B а также C которые были поставлены как B а также C). Если функция возвращает true в любой момент вы можете остановить сканирование, и внешняя функция также возвращает true (чего бы это ни стоило, C ++ 11 предоставляет std::any_of для такого рода ситуации).
Вы просто ищете x внутри массива, который соответствует критериям x> B && Икс < C. Линейный поиск будет делать — если вы собираетесь делать поиск только один раз. Если поиск должен выполняться несколько раз (что-то большее, чем log (размер массива)), то имеет смысл сначала отсортировать, а затем выполнить бинарный поиск.
bool InRangeSearch(low, high)
{
index = upper_bound(array, low);
if(index==-1)
return false;
index2 = lower_bound(array, high);
if(index2==-1)
return true;
return ((index2-1)>index);
}
псевдокод:
Quicksort(A as array, low as int, high as int)
if (low < high)
pivot_location = Partition(A,low,high)
Quicksort(A,low, pivot_location - 1)
Quicksort(A, pivot_location + 1, high)
Partition(A as array, low as int, high as int)
pivot = A[low]
leftwall = low
for i = low + 1 to high
if (A[i] < pivot) then
leftwall = leftwall + 1
swap(A[i], A[leftwall])
swap(A[low],A[leftwall])
return (leftwall)
Код программы:
#include <stdio.h>
void quickSort( int[], int, int);
int partition( int[], int, int);int main()
{
int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};
int i;
printf("\n\nUnsorted array is: ");
for(i = 0; i < 9; ++i) printf(" %d ", a[i]);
quickSort( a, 0, 8);
printf("\n\nSorted array is: ");
for(i = 0; i < 9; ++i) printf(" %d ", a[i]);
printf("\n\n " );
return 0;
}void quickSort( int a[], int l, int r)
{
int j;
if( l < r )
{
j = partition( a, l, r);
quickSort( a, l, j-1);
quickSort( a, j+1, r);
}
}int partition( int a[], int l, int r) {
int pivot, i, j, t;
pivot = a[l];
i = l; j = r+1;
while( 1)
{
do ++i; while( a[i] <= pivot && i <= r );
do --j; while( a[j] > pivot );
if( i >= j ) break;
t = a[i]; a[i] = a[j]; a[j] = t;
}
t = a[l]; a[l] = a[j]; a[j] = t;
return j;
}