Сравнение методов внутренней сортировки

Для рассмотренных в начале этой части простых методов сортировки существуют точные формулы, вычисление которых дает минимальное, максимальное и среднее число сравнений ключей (C) и пересылок элементов массива (M). Таблица 2.10 содержит данные, приводимые в книге Никласа Вирта.

Таблица 2.10. Характеристики простых методов сортировки

Для оценок сложности усовершенствованных методов сортировки точных формул нет. Известно лишь, что для сортировки методом Шелла порядок C и M есть O(n(1.2)), а для методов Quicksort, Heapsort и сортировки со слиянием - O(n?log n). Однако результаты экспериментов показывают, что Quicksort показывает результаты в 2-3 раза лучшие, чем Heapsort (в таблице 2.11 приводится выборка результатов из таблицы, опубликованной в книге Вирта; результаты получены при прогоне программ, написанных на языке Модула-2). Видимо, по этой причине именно Quicksort обычно используется в стандартных утилитах сортировки (в частности, в утилите sort, поставляемой с операционной системой UNIX).

Таблица 2.11. Время работы программ сортировки

#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();

}