Реализация сортировки вставками. Алгоритм Шелла.

 

Если первоначальный файл отсортирован, то на каждом просмотре делается только одно сравнение, так что эта сортировка имеет порядок О(n). Если файл отсортирован первоначально в обратном порядке, то данная сортировка имеет общее число сравнений

 

(n -1) + (n -2) + … + 3 + 2 + 1 = (n -1)* n /2.

Сортировка простыми вставками лучше, чем сортировка «методом пузырька». Чем ближе файл к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Среднее число сравнений в сортировке простыми вставками, рассматривая все возможные перестановки во входном массиве, составляет О(n ²). Требования на пространство для этой сортировки состоят только из одной временной переменной, например, Y.

Улучшение сортировки простыми вставками достигается использованием вставок в список. При таком подходе используется массив указателей link, по одному указателю на каждый элемент первоначального массива. Данный массив можно представить как некоторый линейный список, на который указывает некоторый внешний указатель first. Для того чтобы вставить k -й элемент, организуется прохождение данного связанного списка до тех пор, пока не будет найдена нужная позиция для X (k) или пока не будет достигнут конец списка. В этот момент X (k) может быть вставлен в этот список просто при помощи настройки указателей списка без какого-либо сдвига элементов в массиве. Это уменьшает время, требуемое для вставки, но не время, необходимое для поиска нужной позиции. Требование на пространство также возникает из-за дополнительного массива link. Среднее число сравнений по прежнему равно О(n ²).

 

Сортировка Шелла (сортировка с убывающим шагом)

 

В этом методе в первоначальном файле сортируются отдельные подфайлы. Значение k назовем шагом. Например, если k =5, то первым сортируется подфайл, состоящий из элементов X (1), X (6), X (11) … Пять подфайлов каждый содержащий одну пятую элементов первоначального файла, сортируются аналогичным образом:

 

Subfile1 Þ X(1), X(6), X(11) …

Subfile2 Þ X(2), X(7), X(12) …

Subfile3 Þ X(3), X(8), X(13) …

Subfile4 Þ X(4), X(9), X(14) …

Subfile 5 Þ X (5), X (10), X (15) …

После того как первые k подфайлов будут отсортированы (обычно при помощи метода простых вставок), выбираем некоторое новое меньшее значение k и данный файл снова разделяется на новый набор подфайлов. Каждый из подфайлов сортируется, и данный процесс повторяется опять с еще меньшим значением k. В конце концов k принимает значение 1, и тогда сортируется подфайл, состоящий из всего файла [3].

Пример. Задана последовательность 25, 57, 48, 37, 12, 92, 86, 33. Отсортировать ее по возрастанию элементов, используя алгоритм Шелла.

 

 

Решение.

Первоначальный файл 25 57 48 37 12 92 86 33

Просмотр 1, шаг 5 25 57 48 37 12 92 86 33

 

 

Просмотр 2, шаг 3 25 57 33 37 12 92 86 48

 

 

Просмотр 3, шаг 1 25 12 33 37 48 92 86 57

 

 

Отсортированный файл 12 25 33 37 48 57 86 92

 

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

 

#include "stdafx.h"

#include <math.h>

#include <iostream>

using namespace std;

#include <conio.h>

 

void shell (int *, int, int);

 

 int main ()

{

/* Инициализация */

int A[40];

int i,n;     

           

cout<<"Enter n= ";

cin>>n;

cout<<"\n Enter array \n";

 

for(i=0;i<n;i++) cin>>A[i];

     

shell(A,n,5); //5 - начальный шаг

 

cout<<"Result:\n";

for(i=0;i<n;i++) cout<<" "<<A[i];

 

_getch();

return 0;

}

 

void shell (int * A, int n, int k)

{

for (;k>=1;k--) // для каждого убывающего шага

{

       for (int i=0;i<n;i++) // цикл по индексу массива

        {

             for (int j=i;j+k<n;j=j+k)

// выполняем сортировку j+k чисел

             {    

                   for (int l=j+k;l<n;l=l+k)

                   {

                        if(A[j]>A[l])

                        {

                              int X=A[j];

                              A[j]=A[l];

                              A[l]=X;       

                        }

                   }

             }

        }

       cout<<"\n k="<<k;

       for(int v=0;v<n;v++) cout<<" "<<A[v];

       cout<<"\n";

}

}