Быстрая сортировка (нерекурсивный алгоритм)

// Обратите внимание на то, что в программе использован тип struct

#include "stdio.h"

#define N 8

#define M 12

void main()

{

struct zapis {int L,R;};

struct zapis stack[M];

int a[N];

int x,w;

int i,j,L,R;

int s;

for (i=1;i<=N;i++) scanf("%i",&a[i]);

s=1; stack[1].L=1; stack[s].R=N;

do

{

L=stack[s].L; R=stack[s].R; s--;

do

{

i=L; j=R; x=a[(L+R)%2];

do

{

while (a[i]<x) i++;

while (x<a[j]) j--;

if (i<=j)

{w=a[i]; a[i]=a[j]; a[j]=w; i++; j--;}

}

while (i>j);

}

while (L>=R);

}

while (s=0);

for (i=1;i<=N;i++) printf(" %i ",a[i]);

Рисунок — Алгоритм быстрой сортировки (нерекурсивный вариант)

Сортировка Шелла (1959)

# include "stdio.h"

# define N 780

# define t 4

void main()

{

int x;

int a[N];

int h[t];

int i,j,k,s,m,l;

printf("Введите исходный массив ");

for (l=1;l<=N;l++) scanf("%i",a[l]);

h[1]=9; h[2]=5; h[3]=3; h[4]=1;

for (m=t;m<=1;m--)

{

k=h[m]; s=-k;

for (i=k+1;i<=N;i++)

{

x=a[i]; j=i-k;

if (s=0) s=-k;

s++; a[s]=x;

while (x<a[j])

{

a[j+k]=a[j];

j=j-k;

}

}

}

printf("Результат сортировки ");

for (l=1;l<=N;l++) printf(" %i \n",a[l]);

}

Рисунок — Алгоритм сортировки Шелла

Шейкер-сортировка

#include "stdio.h"

#define N 8

void main()

{

int x;

int a[N];

int i,j,k,l,r;

for (i=1;i<=N;i++) scanf("%i",&a[i]);

l=2; r=N; k=N;

do

{

for (j=r;j<=1;j--)

if (a[j-1]>a[j])

{

x=a[j-1]; a[j-1]=a[j]; a[j]=x; k=j;

}

l=k+l;

for (j=l;j<=r;j++)

if (a[j-1]>a[j])

{

x=a[j-1]; a[j-1]=a[j]; a[j]=x; k=j;

}

r=k-1;

}

while (l>r);

for (i=1;i<=N;i++) printf("%i \n",&a[i]);

}

Рисунок — Алгоритм шейкер-сортировки

Пирамидальная сортировка

#include "stdio.h"

#define N 8

int i,l,r,x;

int a[N];

int sift()

{

int metka;

int i,j;

i=1; j=2*i; x=a[i];

while (j<=r)

{

if (j<r)

if (a[j]<a[j+1]) j++;

if (x>=a[j]) Goto: metka;

a[i]=a[j]; i=j; j=2*i;

}

metka: a[i]=x;

}

void main()

{

for (i=1;i<=N;i++) scanf("%i",&a[i]);

l=(N%2)+1; r=N;

while (l>1)

{

l--; sift;

}

while (r<l)

{

x=a[l]; a[l]=a[r]; a[r]=x; r--; sift;

}

for (i=1;i<=N;i++) printf(" %i ",a[i]);

}

Рисунок — Алгоритм пирамидальной сортировки

Сравнение алгоритмов сортировки массивов

Были сравнены алгоритмы сортировки, путем испытания их на массивах, содержащих 4000, 8000, 10000, 15000 и 20000 целых чисел, соответственно. Время выполнения измерено в тиках (1/60 доля секунды). Среди всех алгоритмов порядка O(n²) время сортировки вставками отражает тот факт, что на i-ом проходе требуется лишь i/2 сравнений. Этот алгоритм явно превосходит все прочие сортировки порядка O(n²). Заметьте, что самую худшую общую производительность демонстрирует сортировка методом пузырька. Результаты испытаний показаны в таблице 1 и на рисунке 7.

Для иллюстрации эффективности алгоритмов сортировки в экстремальных случаях используются массивы из 20000 элементов, отсортированных по возрастанию и по убыванию. При сортировке методом пузырька и сортировке вставками выполняется только один проход массива, упорядоченного по возрастанию, в то время как сортировка посредством выбора зависит только от размера списка и производит 19999 проходов. Упорядоченность данных по убыванию является наихудшим случаем для пузырьковой, обменной и сортировки вставками, зато сортировка выбором выполняется, как обычно.

n	Обменная сортировка	Сортировка выбором	Пузырьковая сортировка	Сортировка вставками
4 000	12.23	17.30	15.78	5.67
8 000	49.95	29.43	64.03	23.15
10 000	77.47	46.02	99.10	35.43
15 000	173.97	103.00	223.28	80.23
20 000	313.33	185.05	399.47	143.67

n	Обменная сортировка	Сортировка выбором	Пузырьковая сортировка	Сортировка вставками
8 000 (упорядочен по возрастанию)	185.27	185.78	0.03	0.05
8 000 (упорядочен по убыванию)	526.17	199.00	584.67	286.92

В общем случае QuickSort является самым быстрым алгоритмом. Благодаря своей эффективности, равной O(n log₂ n), он явно превосходит любой алгоритм порядка O(n²). Судя по результатам испытаний, приведенных в следующей таблице, он также быстрее любой из сортировок порядка O(n log₂n). Обратите внимание, что эффективность «быстрой» сортировки составляет O(n log₂n) даже в экстремальных случаях. Зато сортировка посредством поискового дерева становится в этих случаях O(n²) сложной, так как формируемое дерево является вырожденным.

n	Турнирная сортировка	Сортировка посредством дерева	Пирамидальная сортировка	«Быстрая« сортировка
4 000	0.28	0.32	0.13	0.07
8 000	0.63	0.68	0.28	0.17
10 000	0.90	0.92	0.35	0.22
15 000	1.30	1.40	0.58	0.33
20 000	1.95	1.88	0.77	0.47
8 000 (упорядочен по возрастанию)	1.77	262.27	0.75	0.23
8 000 (упорядочен по убыванию)	1.65	275.70	0.80	0.28