Ответы:
Я часто использую вот эти две.
Сортировка Шелла:
int arr[] = { 75, 7, 42, 0, 91, 18, 10, 47, 456, 911 , 170};
int steps [] = {9,5,3,1};
int STEPS_LENGTH = 4;
int ARR_LENGTH = sizeof (arr) / sizeof (int);
for (int k=0; k < STEPS_LENGTH; k++)
{
int h = steps [k];
for (int i=h; i < ARR_LENGTH;i++)
{
int elt = arr [i];
int j;
for (j=i-h; j >=0 && arr [j]>elt; j-=h )
arr [j+h] = arr [j];
arr [j+h] = elt;
}
}
for (int i = 0; i < ARR_LENGTH; i++)cout<< arr[i]<<"\n";
---------------------------------------------------------------------
И моя любимая - Пирамидальная:
void shift(int * arr, int L, int R)
{
int i = L, j = 2 * L + 1, elt = arr[L];
if (j < R && arr[j + 1] < arr[j]) j++;
while (j <= R && arr[j] < elt)
{
arr[i] = arr[j];
i = j;
j = j * 2 + 1;
if (j < R && arr[j + 1] < arr[j])
j++;
}
arr[i] = elt;
}
void main(void)
{
int arr[] = { 44, 55, 12, 42, 94, 18, 06, 67 , 8 , 121 , 64 , 56 , 75 };
int ARR_LENGTH = sizeof (arr) / sizeof (int);
int L = ARR_LENGTH / 2 + 1;
int R = ARR_LENGTH - 1;
while (L >= 1)
{
L--;
shift(arr, L, R);
}
while (R > 0)
{
int tmp = arr[0];
arr[0] = arr[R];
arr[R] = tmp;
R--;
shift(arr, L, R);
}
for (int i = 0; i < ARR_LENGTH; i++) cout<< arr[i]<<"\n";
}
А в твоём алгоритме лично мне не нравится первая строчка. Передавать массивы в функции лучше по ссылке :
Описание: void sort(int *ar,int size)
Вызов: sort(ar,size)
Да и ваще не люблю я рекурсивные функции, они жрут слишком много ресурсов и для больших массивов довольно затратные!
P.S. точно не припомню в каком порядке упорядочивают приведённые алгоритмы, но это, надеюсь, не проблема!
Я часто использую вот эти две.
Сортировка Шелла:
int arr[] = { 75, 7, 42, 0, 91, 18, 10, 47, 456, 911 , 170};
int steps [] = {9,5,3,1};
int STEPS_LENGTH = 4;
int ARR_LENGTH = sizeof (arr) / sizeof (int);
for (int k=0; k < STEPS_LENGTH; k++)
{
int h = steps [k];
for (int i=h; i < ARR_LENGTH;i++)
{
int elt = arr [i];
int j;
for (j=i-h; j >=0 && arr [j]>elt; j-=h )
arr [j+h] = arr [j];
arr [j+h] = elt;
}
}
for (int i = 0; i < ARR_LENGTH; i++)cout<< arr[i]<<"\n";
---------------------------------------------------------------------
И моя любимая - Пирамидальная:
void shift(int * arr, int L, int R)
{
int i = L, j = 2 * L + 1, elt = arr[L];
if (j < R && arr[j + 1] < arr[j]) j++;
while (j <= R && arr[j] < elt)
{
arr[i] = arr[j];
i = j;
j = j * 2 + 1;
if (j < R && arr[j + 1] < arr[j])
j++;
}
arr[i] = elt;
}
void main(void)
{
int arr[] = { 44, 55, 12, 42, 94, 18, 06, 67 , 8 , 121 , 64 , 56 , 75 };
int ARR_LENGTH = sizeof (arr) / sizeof (int);
int L = ARR_LENGTH / 2 + 1;
int R = ARR_LENGTH - 1;
while (L >= 1)
{
L--;
shift(arr, L, R);
}
while (R > 0)
{
int tmp = arr[0];
arr[0] = arr[R];
arr[R] = tmp;
R--;
shift(arr, L, R);
}
for (int i = 0; i < ARR_LENGTH; i++) cout<< arr[i]<<"\n";
}
А в твоём алгоритме лично мне не нравится первая строчка. Передавать массивы в функции лучше по ссылке :
Описание: void sort(int *ar,int size)
Вызов: sort(ar,size)
Да и ваще не люблю я рекурсивные функции, они жрут слишком много ресурсов и для больших массивов довольно затратные!
P.S. точно не припомню в каком порядке упорядочивают приведённые алгоритмы, но это, надеюсь, не проблема!
Мля! Огнелиса решила продублировать ответ) ну да хрен с ней!
Я нашёл quicksort :
void sort(int arr[], int L, int R)
{
if (L >= R)
return;
int m = (L + R) /2;//int m = (L + R) >>1; сдвиг работает быстрее.
int mediana = arr[m];
int LL = L;
int RR = R;
while (LL < RR) {
while (arr[LL] < mediana)
LL++;
while (arr[RR] > mediana)
RR--;
if (LL <= RR) {
int swap = arr[LL];
arr[LL] = arr[RR];
arr[RR] = swap;
LL++;
RR--;
}
}
if (LL<R)
sort (arr , LL , R);
if (RR > L)
sort (arr , L , RR);
}
void main(void) {
int arr[] = { 1, 3, 2, 7, 5, 8, 0, 4, 6, 9 };
int ARR_LENGTH = sizeof (arr) / sizeof (int);
sort (arr , 0 , ARR_LENGTH - 1);
for (int i=0; i < ARR_LENGTH; i++)
printf ("%4d" , arr [i] );
}
Я заметил что sort(int arr[]... в обьявлении является вполне приемлемым и quicksort всё же содержит элементы рекурсии. Но я остаюсь при своем рекурсия- затратная, и алгоритм какой-то большой и не понятный.
16 лет назад