Исследование алгоритма сортировки методом Шелла.

Автор megabax

03.01.2013 г.

Циклы

Исследование алгоритма сортировки методом Шелла.

Это последний урок из серии "Алгоритмы", публикуемый в бесплатном разделе. Начиная со следующего, публикация уроков будет продолжена в платном разделе. В бесплатном же разделе, возможно, иногда будут публиковать некоторые статьи, посвященные алгоритмам.

Исходники к уроку можно скачать здесь.

На прошлом уроке мы запрограммировали и протестировали алгоритм сортировки методом Шелла. И результат нас несколько разочаровал. Может, мы неудачно выбрали последовательность проходов? Давайте проверим другие варианты.

Но сначала мы чуть чуть изменим метод ShellSort:

public void SortShell(int[] a, int N)

{

int i, j, gap, k;

TType x;

int count = list.Count;

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

{

gap = a[k];

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

{

x = list[i];

for (j = i - gap; j >= 0 && isLess(x,list[j]); j = j - gap)

{

list[j + gap] = list[j];

}

list[j + gap] = x;

}

Как видим, последовательность чисел мы теперь будет задавать в параметре. И попробуем задать другую последовательность чисел, вместо 9,5,3,2,1 зададим 15,9,5,3,2,1 (выделено маркером):

private void btnShell_Click(object sender, EventArgs e)

{

int count = 240000;

InitInt(count);

DateTime dt1 = DateTime.Now;

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

intsort.SortShell(a,6);

DateTime dt2 = DateTime.Now;

MessageBox.Show("Отсортировано " + count.ToString() + " элементов. Время нач.: " + dt1.ToString() + " кон.: " + dt2.ToString());

}

Теперь время сортировки составило 50 секунд (в прошлый раз было 84 сек.):

Теперь попробуем поменять числа в последовательности, например, попробуем так: 15,11,5,3,2,1. Время получилось 47 секунд. Как видим, изменилось мало. Попробуем добавить впереди еще одно число: 17,15,11,5,3,2,1. Время 46 секцнд:

Тоже мало что изменилось. А если первое число не 17, а например, 25? Получается 31 секунда:

Сделаем еще более длинную последовательность: 50, 45, 35, 25, 15, 11, 5, 3, 2, 1. У нас получается вообще 15 секунд:

Какую закономерность мы наблюдаем? Чем больше чисел в последовательности, тем более быстро идет сортировка! Если честно это уже давно примечено. Так, согласно Википедии, существует ряд стандартных последовательностей для алгоритма сортировки Шелла, например 2ⁱ-1≤N, где N - число элементов в сортируемом массиве. При этом сложность алгоритма, по утверждению Википедии, должна быть N^3/2.Давайте это проверим. Для начала переделаем слегка метод SortShell:

public void SortShell()

{

int i, j, gap, k;

TType x;

int count = list.Count;

int N = SequenceForShell.Count;

for (k = N-1; k >= 0; k--)

{

gap = SequenceForShell[k];

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

{

x = list[i];

for (j = i - gap; j >= 0 && isLess(x,list[j]); j = j - gap)

{

list[j + gap] = list[j];

}

list[j + gap] = x;

}

SequenceForShell - это список чисел, он должен быть объявлен в классе Sort:

class Sort<TType>

{

//сортируемый массив

public List<TType> list;

//Последовательность для сортировки методом Шелла

public List<int> SequenceForShell;

...

И для инициализации этого массива предусмотрим метод CreateSequenceForShell:

public void CreateSequenceForShell(int N)

{

int curritem = 1;

int i = 2;

if (SequenceForShell == null) SequenceForShell = new List<int>();

SequenceForShell.Clear();

while (curritem <= N)

{

SequenceForShell.Add(curritem);

curritem = Convert.ToInt32(Math.Pow(2,i)-1);

i++;

}

Теперь немного переделам обработчик нажатия на кнопочку пуск, что бы протестить изменения, которые мы внесли в алгоритм сортировки методом Шелла:

private void btnStart_Click(object sender, EventArgs e)

{

lbIntAfter.Items.Clear();

lbIntBefore.Items.Clear();

lbStringAfter.Items.Clear();

lbStringBefore.Items.Clear();

InitInt(amount);

InitString(amount);

ShowInt(lbIntBefore, intsort.list);

ShowString(lbStringBefore, stringsort.list);

intsort.CreateSequenceForShell(amount);

intsort.SortShell();

stringsort.CreateSequenceForShell(amount);

stringsort.SortShell();

ShowInt(lbIntAfter, intsort.list);

ShowString(lbStringAfter, stringsort.list);

}

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

И так, проверим работу алгоритма:

И приступим к его тестированию:

private void btnShell_Click(object sender, EventArgs e)

{

int count = 240000;

InitInt(count);

DateTime dt0 = DateTime.Now;

DateTime dt1 = DateTime.Now;

intsort.CreateSequenceForShell(count);

intsort.SortShell();

DateTime dt2 = DateTime.Now;

MessageBox.Show("Отсортировано " + count.ToString() + " элементов. "+

"время нач. создания массива " + dt0.ToString() + " Время нач. сортировки: " + dt1.ToString() + " кон.: " + dt2.ToString());

}

И что мы видим? Действительно, работать стало не просто быстро, а очень быстро. 240 тыс. элементов примерно за 1 секунду:

А если миллион? То получается около двух секунд:

А вот если взять 10 миллионов элементов, то время сортировки растягивается уже на 8 секунд:

При чем заметьте, мы увеличили размер массива в 10 раз, а время сортировки возросло всего лишь в 4 раза. Эффект налицо!

Для прикола попробуем отсортировать сто миллионов элементов. Получилось 2 минуты с копейками:

Исходники к уроку можно скачать здесь.

* Г. Шилдт, "Теория и практика С++".

Последнее обновление ( 03.01.2013 г. )

Пред. »

Вернуться