Сравнение методов внутренней сортировки
Для рассмотренных в начале этой части простых методов сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей (C) и пересылок элементов массива (M). Таблица 2.10 содержит данные, приводимые в книге Никласа Вирта.
Таблица 2.10. Характеристики простых методов сортировки
Min | Avg | Max | |
Прямое включение | C = n-1 M = 2x(n-1) | (n2 + n - 2)/4 (n2 - 9n - 10)/4 | (n2 -n)/2 - 1 (n2 -3n - 4)/2 |
Прямой выбор | C = (n2 - n)/2 M = 3x(n-1) | (n2 - n)/2 nx(ln n + 0.57) | (n2 - n)/2 n2/4 + 3x(n-1) |
Прямой обмен | C = (n2 - n)/2 M = 0 | (n2 - n)/2 (n2 - n)x0.75 | (n2 - n)/2 (n2 - n)x1.5 |
Для оценок сложности усовершенствованных методов сортировки точных формул нет. Известно лишь, что для сортировки методом Шелла порядок C и M есть O(n(1.2)), а для методов Quicksort, Heapsort и сортировки со слиянием - O(n?log n). Однако результаты экспериментов показывают, что Quicksort показывает результаты в 2-3 раза лучшие, чем Heapsort (в таблице 2.11 приводится выборка результатов из таблицы, опубликованной в книге Вирта; результаты получены при прогоне программ, написанных на языке Модула-2). Видимо, по этой причине именно Quicksort обычно используется в стандартных утилитах сортировки (в частности, в утилите sort, поставляемой с операционной системой UNIX).
Таблица 2.11. Время работы программ сортировки
Упорядоченный массив | Случайный массив | В обратном порядке | |
n = 256 | |||
Heapsort Quicksort Сортировка со слиянием | 0.20 0.20 0.20 | 0.08 0.12 0.08 | 0.18 0.18 0.18 |
n = 2048 | |||
Heapsort Quicksort Сортировка со слиянием | 2.32 2.22 2.12 | 0.72 1.22 0.76 | 1.98 2.06 1.98 |
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <stdlib.h>
#define N 20
void st1(int *a) // метод прямого включения
{ int i,j,k;
for (i=1; i<N; i++)
{
k=a[i];
j=i-1;
while(k<a[j]&&j>=0)
{
a[j+1]=a[j];
j--;
}
a[j+1]=k;
}
}
void st2(int *a) // метод прямого выбора
{int i,j,x,k;
for(i=0; i<N-1; i++)
{
x=a[i];
k=i;
for (j=i+1; j<N; j++)
{
if (a[j]<x)
{k=j;
x=a[k];
}
}
a[k]=a[i];
a[i]=x;
}
}
void st3(int *a) // метод пузырька
{int i,j,k,flag;
for (i=0; i<N-1; i++)
{
flag=0;
for (j=N-1; j>i; j--)
{
if (a[j]<a[j-1])
{
k=a[j];
a[j]=a[j-1];
a[j-1]=k;
flag=1;
}
}
if (flag==0)
break;
}
}
void st4(int *a) // Шейкерная сортировка
{
int i,j,k,x,L,R;
L=1;
R=N-1;
k=N-1;
do
{
for (j=R;j>=L;j--)
{
if (a[j-1]>a[j])
{
x=a[j-1];
a[j-1]=a[j];
a[j]=x;
k=j;
}
}
L=k+1;
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);
}
void sort_Shell(int *a) //Сортировка методом Шелла
{
int i,j,x, k=(N+1)/2;
while(k>0)
{
for(i=k;i<N;i++)
{
if(a[i-k] > a[i])
{
x = a[i];
j=i-k;
M1: a[j+k] = a[j];
if(j>k)
{
if(a[j-k]>x)
{j=j-k;
goto M1;
}
}
a[j] = x;
}
}
if(k>2)
k=(k+1)/2;
else k=k/2;
}
}
void Sift(int *a, int l,int r) //Postroenie piramidy
{ int i,j,x,k;
i=l;
j=2*l+1;
x=a[l];
if ((j<r)&&(a[j]<a[j+1]))
j++;
while ((j<=r)&&(x<a[j]))
{ k=a[i];
a[i]=a[j];
a[j]=k;
i=j;
j=2*j+1;
if ((j<r)&&(a[j]<a[j+1]))
j++;
}
}
void TreeSort(int *a) // Сортировка с помощью бинарного дерева
{ int l,r,x,i;
l=N/2;
r=N-1;
while (l>0) // Postroenie piramidy
{ l=l-1;
Sift(a,l,r);
}
while(r>0) //Sortirovka
{ x=a[0];
a[0]=a[r];
a[r]=x;
r--;
Sift(a,l,r);
}
}
void main (void)
{
int i, a[N],k;
srand(time(NULL));
for (i=0; i<N; i++)
{
a[i]=-10+rand()%N;
}
for (i=0; i<N; i++)
{
printf(" %3d", a[i]);
}
printf("\n Vyberite metod sortirovki:\n1 - vklu4enie;\n2-pryamoy vybor;\n3-babble;\n4-Cocktail sort;\n5-Shell;\n6 - TreeSort\n");
scanf("%d",&k);
switch(k)
{
case 1: st1(a); break;
case 2: st2(a); break;
case 3: st3(a); break;
case 4: st4(a); break;
case 5: sort_Shell(a); break;
case 6: TreeSort(a); break;
default: printf ("Ne vybran metod");
}
for (i=0; i<N; i++)
{
printf(" %3d", a[i]);
}
_getch();
}
Программа сортировки с помощью стандартной функции qsort:
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
int num[10] = { 1, 3, 6, 5, 8, 7, 9, 6, 2, 0};
int comp(const void *, const void *);
void main(void)
{
int i;
printf("Isxodniy massiv: ");
for(i=0; i<10; i++)
printf("%d ", num[i]);
qsort(num, 10, sizeof(int), comp);
printf("\nSort massiv: ");
for(i=0; i<10; i++) printf("%d ", num[i]);
_getch();
}
/* сравнение целых */
int comp(const void *i, const void *j)
{
return *(int *)i - *(int *)j;
}