Быстрая сортировка (нерекурсивный алгоритм)
// Обратите внимание на то, что в программе использован тип 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(n2) время сортировки вставками отражает тот факт, что на i-ом проходе требуется лишь i/2 сравнений. Этот алгоритм явно превосходит все прочие сортировки порядка O(n2). Заметьте, что самую худшую общую производительность демонстрирует сортировка методом пузырька. Результаты испытаний показаны в таблице 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 log2 n), он явно превосходит любой алгоритм порядка O(n2). Судя по результатам испытаний, приведенных в следующей таблице, он также быстрее любой из сортировок порядка O(n log2n). Обратите внимание, что эффективность «быстрой» сортировки составляет O(n log2n) даже в экстремальных случаях. Зато сортировка посредством поискового дерева становится в этих случаях O(n2) сложной, так как формируемое дерево является вырожденным.
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 |