Алгоритми за сортиране 2част. Лекция

Алгоритми за сортиране
Лекция 4-2

2.3. Бързи алгоритми
2.3.1. Сортиране с алгоритъма на Шел – 1959 г.
За пръв път сложността пада под n2
В първата фаза (интервал h1) се сортират (с алгоритъма с пряко вмъкване)
следните елементи: 1, 1+h1, 1+2h1, 1+3h1 и т.н. В следващата фаза се
прилага сортиране с интервал h2 и т.н.
Размерът на интервалите е намаляващ и стига до 1: h1, h2,..., 1.

1

1+h1

h1

1+2h1

h1

А -масив
h1

за този интервал не
може да се приложи
изцяло

http://www.youtube.com/watch?v=CmPA7zE8mx0 -Shell-sort with Hungarian (Székely) folk dance

Определяне на интервалите:

ShellSort.cpp

2.3.2. Бързо сортиране
Предложено е от Хоор през 1962г. На всяка стъпка се избира елемент X
(среден по стойност) от масива. Спрямо елемента X се разделят останалите
елементи на масива (множеството S) на две части: S1X и S2X, като е
желателно S1 и S2 да са почти еднакви по размер. Използват се два
показалеца i и j към елементи в масива, които се движат от двата края на
масива към средата му. Рекурсивно определяме S1 и S2, докато размерът на
сортираната част стане 1. Показалецът i спира движението си при A[i]X, а
показалецът j при A[j]X.

Бързото сортиране се извършва, докато се достигне размер на участъка <=b,
т.е. не се извършва пълно сортиране. След това сортирането се извършва чрез
алгоритъма с пряко вмъкване.

QuickSort (S);
If S>b {
избор на X;
определят се S1 и S2 чрез сравнение на елементите с
X и движение на двата показалеца i и j,