Сортировка методом «турнира с выбыванием»
Действия метода отражают процесс разыгрывания некоторого турнира, где его участники состязаются друг с другом для определения наилучшего игрока. Эта сортировка также называется сортировкой посредством выбора из дерева. Рассмотрим некоторый турнир в виде дерева [3].
Такое дерево можно понимать следующим образом: Кейс играла в турнире с Гейл и проиграла, т.е. победила Гейл и ее имя помещается в узел дерева и т.д. То есть на представленном дереве показан турнир, в котором победила Гейл. А кто занял 2-е место? А 3-е место? Решение на основе просмотра дерева от листьев к корню позволяет сделать вывод, что 2-е место заняла Пэт, а Джордж с Фрэнком поделили 3-е место, т.е. Гейл выиграла 3 игры, а Пэт выиграла 2 игры, а Джорд с Фрэнком выиграли по 1 игре.
Рассмотрим тот же подход, но уже к сортировке чисел. Каждому первоначальному элементу приписывается некоторый узел с листом в некотором бинарном дереве. Это дерево строится снизу вверх от узлов с листьями до корня следующим образом. Выберем 2 узла с листьями и положим, что они являются сыновьями некоторого заново созданного узла, представляющего отца. Содержимое узла, являющееся отцом, устанавливается равным наибольшему из чисел, представляющих его сыновей.
Этот процесс повторяется до тех пор, пока не останется один лист или их совсем не останется. Если останется один лист, то этот узел надо переместить вверх на следующий уровень. Теперь этот процесс надо повторить с заново созданными узлами до тех пор, пока самое большое число не будет помещено в узел, являющийся корнем бинарного дерева, чьи листья содержат все числа из первоначального файла. Содержимое этого узла может быть затем выведено как самый большой элемент и т.д. пока не будут выведены все первоначальные элементы.
Пример. Задана последовательность чисел: 25, 57, 48, 37, 12, 92, 86, 33. Отсортировать ее методом «турнира с выбыванием».
Решение. Начинаем формировать дерево с листьев:
1
этап (в результате получили самое большое
число 92. Его следует вывести из дерева.)
2 этап
и т.д.
Реализация сортировки вставками. Алгоритм Шелла.
Если первоначальный файл отсортирован, то на каждом просмотре делается только одно сравнение, так что эта сортировка имеет порядок О(n). Если файл отсортирован первоначально в обратном порядке, то данная сортировка имеет общее число сравнений
(n-1) + (n-2) + … + 3 + 2 + 1 = (n-1)*n/2.
Сортировка простыми вставками лучше, чем сортировка «методом пузырька». Чем ближе файл к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Среднее число сравнений в сортировке простыми вставками, рассматривая все возможные перестановки во входном массиве, составляет О(n2). Требования на пространство для этой сортировки состоят только из одной временной переменной, например, Y.
Улучшение сортировки простыми вставками достигается использованием вставок в список. При таком подходе используется массив указателей link, по одному указателю на каждый элемент первоначального массива. Данный массив можно представить как некоторый линейный список, на который указывает некоторый внешний указатель first. Для того чтобы вставить k-й элемент, организуется прохождение данного связанного списка до тех пор, пока не будет найдена нужная позиция для X(k) или пока не будет достигнут конец списка. В этот момент X(k) может быть вставлен в этот список просто при помощи настройки указателей списка без какого-либо сдвига элементов в массиве. Это уменьшает время, требуемое для вставки, но не время, необходимое для поиска нужной позиции. Требование на пространство также возникает из-за дополнительного массива link. Среднее число сравнений по прежнему равно О(n2).
Сортировка Шелла (сортировка с убывающим шагом)
В этом методе в первоначальном файле сортируются отдельные подфайлы. Значение 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) …
Subfile5 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";
}
}