Сортировка Шелла, обший принцип

Сортировка Шелла это, по-сути, модификация схем сортировки других алгоритмов. Фактически для сортировки элементов используются другие алгоритмы, такие как: пузырьком, вставками, выбором и т.д. Но только эти алгоритмы применяются не ко всей исходной последовательности, а к ее частям.

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

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

Пример. Имеется последовательность [2, 3, 9, 2, 8, 4, 6, 8, 11, 12, 4, 6], n=12. Символом d - будем обозначать расстояние между сортируемыми элементами на каждом шаге (на первом шаге d = n/2, на втором d = d/2 и т.д.)

1 шаг. d = n/2 = 6. => Получаем 6 сортируемых групп(имеют одинаковый цвет):
[2, 3, 9, 2, 8, 4, 6, 8, 11, 12, 4, 6]
После сортировки в пределах каждой группы, имеем:
[2, 3, 9, 2, 4, 4, 6, 8, 11, 12, 8, 6]

2 шаг. d = d/2 = 3. => Получаем 2 сортируемых группы(имеют одинаковый цвет):
[2, 3, 9, 2, 4, 4, 6, 8, 11, 12, 8, 6]
После сортировки в пределах каждой группы, имеем:
[2, 3, 4, 2, 4, 6, 6, 8, 9, 12, 8, 11]

3 шаг. d = d/2 = 1(целочисленное деление) => заключительный шаг. Сортируем всю последовательность:
[2, 3, 4, 2, 4, 6, 6, 8, 9, 12, 8, 11] в итоге получим:
[2, 2, 3, 4, 4, 6, 6, 8, 8, 9, 11, 12]

В качестве самой сортировки элементов в группе можно использують различные алгоритмы простой сортировки: вставками, выбором, пузырьком и проч. Но, если подумать, самым оптимальным вариантом в данном случае - будет прогонка только лишь 1-ой итерации пузырькового метода. Т.к. в первых 2-х случаях нужно будет расходовать память на формирование дополнительной последовательности элементов группы, чтобы передавать ее на вход сортировки вставкой или выбором, ну или формирование последовательности индексов этих элементов... хотя можно будет также продумать вариант передачи всей исходной последовательности и в дополнительных параметрах указывать смещение первого нужного элемента и шаг прохода по этим элементам с целью, чтобы пройти элементы именно нужной нам группы(в этом случае не надо будет формировать дополнительные последовательности элементов в группах, но придется модифицировать базовые алгоритмы упомянутых сортировок).

При использовании же пузырького подхода мы в самом алгоритме сортировки Шелла проходимся по каждому элементу каждой группы и меняем его местами со следующим(из его же группы конечно) если он его больше(в случае сортировки по возрастанию конечно). В результате, мы к элементам каждой группы применим как-бы 1 проход пузырьковой сортировки. Остальные проходы - делать не нужно: это будет делаться на каждой следующей итерации основного нашего алгоритма шелла, поскольку шаг d разбиения на группы уменьшается. НО! На заключительной сортировке всей последовательности метод пузырьком должен отработать полностью. Либо же следует вызвать сортировку вставками, либо выбором. 

Соответственно, получим:

d = n
while d > 1
  d = d / 2 /* целочисленное */
  i = 0
  /* делаем 1 "пузырьковый" проход
     для элементов каждой группы */
  while (j = i + d) < n
    if x[i] > x[j]
      /* x[i] и x[j] меняем местами */
      swap(i, j)
    i++
 
BubbleSort()
/* либо InsertSort(), либо SelectSort() */

При этом производительность алгоритма пропорциональна ~ O(n²), но количество перестановок по-сравнению с простыми методами вставкой, выбором или пузырьком - заметно сокращается. Дополнительная память - не используется(не считая счетчиков циклов и проч.).

Величина шага d - называется приращением и является важной характеристикой алгоритма Шелла. И выбор динамики уменьшения этой величины очень существенно сказывается на производительности алгоритма в целом, позволяя достигать пропорций от ~ O(n^7/6) в лучшем случае до ~ O(n^4/3) в худшем, о чем рассказывает следующая задача сортировка Шелла, оптимальный выбор приращений.

Реализации:

заполните необходимые поля!

название:
uri-имя*:
заголовок окна:
ЯП:	[другой...] pseudojavajavascriptpythonC++C#CphpGoqbasicrailsrubysmartytsqlvbnetvisualfoxproxmlactionscriptplsqlpascaloracle8sqlvbfortransmalltalkasmcssdelphigroovylispperlmysqlmatlab
код (double click - редактирование) (Esc - предпросмотр)
описание:
автор:	email:
пароль:	[для последующего редактирования]
	подписаться на комментарии**

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

 Базовая сортировка Шелла с результирующей сортировкой вставками ссылка |режим:

template<class T>
void swap(T* x, int i, int j) {
    T tmp;
    tmp = x[i]; x[i] = x[j]; x[j] = tmp;
}
 
template<class T>
void ShellSortBin(T* x) {
    int d = n;
    while (d > 1) {
        d /= 2;
        int i = 0, j = 0;
         /* делаем 1 "пузырьковый" проход
            для элементов каждой группы */
        while (j = i + d < n) {
            if (x[i] > x[j]) {
                swap(x, i, j);
            }
            i++;
        }
    }
    InsertSort(x);
}

template<class T> void swap(T* x, int i, int j) { T tmp; tmp = x[i]; x[i] = x[j]; x[j] = tmp; } template<class T> void ShellSortBin(T* x) { int d = n; while (d > 1) { d /= 2; int i = 0, j = 0; /* делаем 1 "пузырьковый" проход для элементов каждой группы */ while (j = i + d < n) { if (x[i] > x[j]) { swap(x, i, j); } i++; } } InsertSort(x); }

Приращение на каждом шаге - уменьшается вдвое.
В прелах каждой группы алгоритм выполняет 1 проход пузырьковой сортировки.
Результирующая сортировка - вставками.

Производительность: ~ O(n²)
Расход памяти: только на хранение счетчиков цикла и пары вспомогательных переменных

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

 

 Базовая сортировка Шелла без результирующей сортировки ссылка |режим:

template<class T>
void ShellSortBin2(T* x) {
    int d = n, i, j;
    while (d > 0) {
        d /= 2;
 
        /* Данный цикл представляет собой
           1 "пузырьковый" проход по всем группам элементов
           на данном шаге. Кроме того, здесь, он выполняется
           и в конце, когда d=1, позволяя избежать результирующей
           сортировки */
        for (i = d; i < n; i++) {
            T tmp = x[i];
            for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
                x[j+d] = x[j];
            }
            x[j+d] = tmp;
        }
    }
}

template<class T> void ShellSortBin2(T* x) { int d = n, i, j; while (d > 0) { d /= 2; /* Данный цикл представляет собой 1 "пузырьковый" проход по всем группам элементов на данном шаге. Кроме того, здесь, он выполняется и в конце, когда d=1, позволяя избежать результирующей сортировки */ for (i = d; i < n; i++) { T tmp = x[i]; for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) { x[j+d] = x[j]; } x[j+d] = tmp; } } }

Приращение на каждом шаге - уменьшается вдвое.
Результирующая сортировка не выполняется поскольку для конечной последовательности Шелла, т.е. когда d=1 и имеются 2 отсортированные группы элементов - к этой последовательности был также применен проход "пузырька", окончательно расставляющий элементы по своим местам.

Производительность: менее ~ O(n²)
Расход памяти: - (только на счетчики цикла, доп. переменные и проч.)
При этом следует отметить, что расход памяти меньше чем в базовом варианте, т.к. не запускается фукнция результирующей сортировки и swap также не используется.

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

 

 сортировка методом Шелла(с использованием структуры) ссылка |режим: ?

struct massiv
{char fio[40];
int key;
};
 
void sort(massiv *a,int n)
{massiv temp;
int i,j,incr=n/2;
while(incr>0)
{
 for(i=incr;i<n;i++)
  {
   j=i-incr;  
    while(j>=0)
		if(a[j].key > a[j+incr].key)
		{temp=a[j];
	a[j]=a[j+incr];
	a[j+incr]=temp;
	j=j-incr;}
		else j=-1;}   
 incr=incr/2;
}
};

struct massiv {char fio[40]; int key; }; void sort(massiv *a,int n) {massiv temp; int i,j,incr=n/2; while(incr>0) { for(i=incr;i<n;i++) { j=i-incr; while(j>=0) if(a[j].key > a[j+incr].key) {temp=a[j]; a[j]=a[j+incr]; a[j+incr]=temp; j=j-incr;} else j=-1;} incr=incr/2; } };

a - массив и n записей.
key - одно из полей записи, которое является ключом.
temp - переменная того же типа, что и элементы.