Методы сортировки с помощью вставок

Метод двоичных вставок. В методе простых вставок производится поиск позиции нового элемента, который добавляется к отсортированной части массива. С помощью двоичного поиска можно уменьшить количество сравнений и, следовательно, сложность алгоритма по времени.

Модификация операторов

t = x [ i ];

for(j=i-1; j>=0 && t<x[j]; j--)

x [ j +1]= x [ j ];

x [ j +1]= t ;

приводит к следующему уменьшению количества сравнений:

t=x[i]; l=0; u=i-1; // i>0

if(t<=x[0]) m=0;

else if(t>=x[i-1]) m=i;

else

while(l<=u)

{

m=(l+u)/2;

if(t<x[m]) u=m-1;

else if(x[m]<t) l=++m;

else break; // x[m]==t

}

for(j=i-1; j>=m; j--)

x[j+1]=x[j];

x [ j +1]= t ;

Добавляя внешний цикл для i =1,2,…, n -1 , получим подпрограмму, реализующую метод двоичных вставок.

Двухпутевые вставки. Главный недостаток метода простых вставок заключается в том, что приходится сдвигать большое количество элементов. С целью устранения этого недостатка первый элемент исходного массива переписывается не в начало, а в середину динамического массива, состоящего из 2 n -1 элементов. Место для последующих элементов освобождается с помощью сдвигов влево и вправо.

Пример. Отсортируем массив

503 87 512 61 908 897 276

методом двухпутевых вставок, начиная с x [6]=503

x [6]=503,

x [5]=87, x [6]=503,

x [5]=87, x [6]=503, x [7]=512,

x [4]=61, x [5]=87, x [6]=503, x [7]=512,

x [4]=61, x [5]=87, x [6]=503, x [7]=512, x [8]=908,

x [4]=61, x [5]=87, x [6]=503, x [7]=512, x [8]=897, x [9]=908,

x [3]=61, x [4]=87, x [5]=276, x [6]=503, x [7]=512, x [8]=897, x [9]=908.

Затем полученный массив переписывается в исходный, а область памяти, занятая динамическим массивом, освобождается. Приведем текст программы :

#include <stdlib.h>

#include <alloc.h>

#include <time.h>

#include <stdio.h>

#include <conio.h>

int tinsert (int *a, int n)

{

// возвращает 0, если нет памяти

int *x,i,j, left=n-1, right=n-1,t;

if((x=(int *) malloc((2*n-1)*sizeof(int)))==0) return 0;

x[n-1]=a[0];

for(i=1; i<n; i++)

{

t=a[i];

if(t>=a[0])

{

for(j=right; j>=0&&t<x[j]; j--)

x[j+1]=x[j];

x[j+1]=t;

right++;

}

else

{

for(j=left; j<=2*n-1&&t>x[j]; j++)

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

x[j-1]=t;

left--;

}

}

for(j=left; j<left+n; j++)

a[j-left]=x[j];

free(x);

return 1;

}

main()

{

int a[10], i;

clrscr ();

printf ("Сортировка методом вставок:\ n ");

randomize();

for(i=0; i<10; i++) a[i]=rand();

printf(" До сортировки :\n");

for(i=0; i<10; i++) printf(" %d ",a[i]);

printf("\n После сортировки :\n");

if(tinsert(a,10))

for(i=0; i<10; i++) printf(" %d ",a[i]);

else

printf("\n ошибка памяти ");

}

Результат работы программы

Сортировка методом вставок:

До сортировки:

26641 349 29743 23437 9082 27431 1530 4217 8156 28559

После сортировки:

349 1530 4217 8156 9082 23437 26641 27431 28559 29743

Вставки в список. Для того чтобы полностью избавиться от перестановок, создается упорядоченный список. Элементы массива переписываются в список. При добавлении элемента производится его сравнение с элементами списка, начиная с первого. Добавляемый элемент записывается перед тем, который окажется больше него. Добавлять элементы можно с помощью подпрограммы:

queue* addsort(queue *q, char *a)

{

queue *s=new queue; // захват памяти

s->info=a;

s->next=0;

if ( q ==0) return s ; // если список был пуст

if(strcmp(a,q->info)<0)

{

p->next=q;

return p;

}

else

return addsort(q->next,a);

}

Здесь узел списка – структура

queue

{

char * info ;

queue * next ;

}

Список определяется в главной программе как

queue * s =0;

и состоит из символьных строк.

Метод Шелла. При сортировке простыми вставками элементы массива передвигаются на соседние позиции. Если мы хотим уменьшить время сортировки, то нам необходимо использовать механизм, с помощью которого записи могли бы перемещаться большими скачками. Такой механизм был предложен Д.Л. Шеллом.

При добавлении в массив элемента x [ i ] рассматриваются элементы массива

x[i-gap], x[i-2*gap], x[i-3*gap],...

где gap – целое число, большее единицы, которое называется шагом. Как только x [ i ] станет не меньше, чем один из рассматриваемых элементов, этот элемент вставляется в массив, а рассматриваемые элементы сдвигаются вправо на gap позиций. Таким образом, добавление с шагом gap осуществляется с помощью операторов:

t=x[i];

for(j=i-gap; t<x[j]&&j>=0; j=j-gap)

x[j+gap]=x[j];

x[j+gap]=t;

Если использовать последовательность убывающих шагов, например, gap =9,5,3,2,1, и для каждого шага организовать цикл

for(i=gap; i<n; i++)

{

t=x[i];

for(j=i-gap; t<x[j]&&j>=0; j=j-gap)

x[j+gap]=x[j];

x[j+gap]=t;

}

то в результате получим отсортированный массив, поскольку шаг gap =1 присутствует.

При удачном выборе последовательности убывающих шагов количество копирований (перемещений) элементов пропорционально n 3/2 . Это значительное улучшение по сравнению с оценкой n 2 для метода простых вставок.

Рекомендуется выбирать шаги gap I { h 1 , h 2 , ...}, где h 1 =1, h s +1 =3 h s +1 , при s >0 . Последовательность заканчивается шагом h t , для которого h t +2 >= n . Например, для n =100 получаем h 1 =1, h 2 =3 ? 1+1=4, h 3 =13, h 4 =40, h 5 =121 . В этом случае нужно выбирать шаги gap =13,4,1 . Рекомендуется также последовательность h s =2 h s -1 +1 , до s =[ log 2 n ]-1 .

Приведем текст подпрограммы и вызывающей ее программы:

#include <stdio.h>

void shell(int *x, int n)

{

int i,j,k,gap,t;

int a[5]={9,5,3,2,1};

for(k=0; k<5; k++)

{

gap=a[k];

for(i=gap; i<n; i++)

{

t=x[i];

for(j=i-gap; t<x[j]&&j>=0; j=j-gap)

x[j+gap]=x[j];

x[j+gap]=t;

}

}

}

main()

{

int i, nums[]={5,7,3,9,5,1,8};

printf(" Сортировка Шелла \n До сортировки :\n");

for(i=0; i<7; i++) printf(“%d ”,nums[i]);

shell ( nums ,7);

printf ("\ n После сортировки:\ n ");

for(i=0; i<7; i++) printf(“%d ”,nums[i]);

}

Результаты работы программы

Сортировка Шелла

До сортировки:

5 7 3 9 5 1 8

После сортировки:

1 3 5 5 7 8 9

Вставки в дерево. Для сокращения числа сравнений мы использовали двоичный поиск, для сокращения числа перестановок – упорядоченный список. Для соединения лучших свойств этих методов используется дерево поиска. Входные данные считываются из массива и записываются в двоичное дерево поиска. Затем из двоичного дерева поиска они читаются в симметричном порядке и записываются в исходный массив, например, с помощью вызова подпрограммы:

void writesort(NODE *tree)

{

if(tree) // если дерево не пусто

{

writesort(tree->left);

x[i++]=tree->info;

writesort ( tree -> right );

}

}

Здесь x [] – внешний массив, а i – внешний счетчик, инициализированный нулем.

for (j=n; j>=1; j--)

{ i=count[k[j]]; S[i]=R[j]; count[k[j]]=i-1;

}