Алгоритмы и структуры данных на С++. Аксёнова Е.А - 60 стр.

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

60 Глава 5. Сортировка
На каждом шаге сортируются частично отсортированные массивы.
Среднее число сравнений в этом методе T = 1.66n
1.25
. Кнут рекомен-
дует выбирать последовательность шагов по формуле h
s+1
= 3h
s
+ 1,
где h
1
= 1. Остановиться следует на значении h
t
, когда h
t+2
≥ n.
Сортировка выбором
В этом методе сначала находим наибольший элемент массива и
меняем местами этот элемент с последним элементом массива. Затем
делаем то же самое с предпоследним элементом и т. д. Среднее вре-
мя работы этого метода, как и у всех простейших методов сортиров-
ки, пропорционально n
2
. Усовершенствованный метод, основанный на
использовании бинарных деревьев, называется пирамидальной сорти-
ровкой.
5.3. Обменная сортировка
Сортировка методом пузырька
Сравниваем K
1
и K
2
и, если надо, меняем местами. Затем сравни-
ваем K
2
и K
3
и, если надо, меняем местами. Таким образом доходим
до K
n−1
и K
n
и, если надо, меняем местами. Затем повторяем этот
алгоритм для n − 1 элементов (т. к. самый большой уже поднят на-
верх) и т. д.
Быстрая сортировка Хоара
Дан массив K
1
, ..., K
n
. Сначала i = 1, j = n. Сравниваем K
i
и
K
j
. Если обмен не нужен, то уменьшаем j на 1 и продолжаем. После
первого обмена продолжаем сравнение, увеличивая i на 1. После оче-
редного обмена уменьшаем j и т. д., до тех пор пока i 6= j. К этому
моменту ключ K
1
займет свою позицию, т. е. все ключи слева меньше
K
1
, а справа – больше (рис. 5.2).
Заносим границы правого массива в стек и сортируем левый мас-
сив тем же способом. Возможна также и рекурсивная реализация.
Метод требует память размера M = C
1
(n+2·log
2
n) и среднее время
T = C
2
· n · ln(n). В среднем метод очень хороший, но в худшем случае
(когда массив почти упорядочен) оценка становится n
2
. Чтобы избе-
жать этого случая, ключ разделения выбирают не K
1
, а случайным
60                                              Глава 5. Сортировка


   На каждом шаге сортируются частично отсортированные массивы.
Среднее число сравнений в этом методе T = 1.66n1.25 . Кнут рекомен-
дует выбирать последовательность шагов по формуле hs+1 = 3hs + 1,
где h1 = 1. Остановиться следует на значении ht , когда ht+2 ≥ n.

                      Сортировка выбором
   В этом методе сначала находим наибольший элемент массива и
меняем местами этот элемент с последним элементом массива. Затем
делаем то же самое с предпоследним элементом и т. д. Среднее вре-
мя работы этого метода, как и у всех простейших методов сортиров-
ки, пропорционально n2 . Усовершенствованный метод, основанный на
использовании бинарных деревьев, называется пирамидальной сорти-
ровкой.



                 5.3. Обменная сортировка
                Сортировка методом пузырька
   Сравниваем K1 и K2 и, если надо, меняем местами. Затем сравни-
ваем K2 и K3 и, если надо, меняем местами. Таким образом доходим
до Kn−1 и Kn и, если надо, меняем местами. Затем повторяем этот
алгоритм для n − 1 элементов (т. к. самый большой уже поднят на-
верх) и т. д.

                  Быстрая сортировка Хоара
    Дан массив K1 , ..., Kn . Сначала i = 1, j = n. Сравниваем Ki и
Kj . Если обмен не нужен, то уменьшаем j на 1 и продолжаем. После
первого обмена продолжаем сравнение, увеличивая i на 1. После оче-
редного обмена уменьшаем j и т. д., до тех пор пока i 6= j. К этому
моменту ключ K1 займет свою позицию, т. е. все ключи слева меньше
K1 , а справа – больше (рис. 5.2).
    Заносим границы правого массива в стек и сортируем левый мас-
сив тем же способом. Возможна также и рекурсивная реализация.
    Метод требует память размера M = C1 (n+2·log2 n) и среднее время
T = C2 · n · ln(n). В среднем метод очень хороший, но в худшем случае
(когда массив почти упорядочен) оценка становится n2 . Чтобы избе-
жать этого случая, ключ разделения выбирают не K1 , а случайным

Страницы