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

UptoLike

ВУЗ: 

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

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

Рубрика: 

5.2. Сортировка вставками 59
В дальнейшем, будем считать, что мы сортируем массив целых чи-
сел K
1
, K
2
, ..., K
n
.
5.2. Сортировка вставками
Сортировка простыми вставками
Пусть ключи K
1
, K
2
, ..., K
j−1
уже упорядочены, т. е. K
1
≤ K
2
≤
... ≤ K
j−1
. Ключ K
j
последовательно сравниваем с ключами K
j−1
,
K
j−2
, ... , K
1
, сдвигая при необходимости ключи на одну позицию
вверх до тех пор, пока не найдем место ключа K
j
в упорядоченном
массиве.
Пример: 7, 5, 1, 10, 4
5, 7, 1, 10, 4
5, 1, 7, 10, 4
1, 5, 7, 10, 4
1, 5, 7, 4, 10
1, 5, 4, 7, 10
1, 4, 5, 7, 10
Для поиска места для ключа K
j
необходимо произвести в среднем
j−1
2
сравнений. Тогда среднее число сравнений вычисляется по фор-
муле T = 1 + 2 + ... +
j−1
2
+ ... +
n−1
2
. Среднее время работы алгоритма
равно T = C · n
2
.
Метод Шелла
Пусть даны ключи: K
1
, K
2
, ..., K
8
и задана последовательность це-
лых чисел (шагов) h = (4, 2, 1).
1) сортируем ключи, отстоящие друг от друга на четыре позиции,
т. е. пары (K
1
, K
5
), (K
2
, K
6
), (K
3
, K
7
), (K
4
, K
8
) методом простых
вставок;
2) сортируем ключи, отстающие друг от друга на 2 позиции, т. е.
четверки (K
1
, K
3
, K
5
, K
7
), (K
2
, K
4
, K
6
, K
8
) методом простых вста-
вок;
3) сортируем весь массив методом простых вставок.
5.2.    Сортировка вставками                                               59


   В дальнейшем, будем считать, что мы сортируем массив целых чи-
сел K1 , K2 , ..., Kn .



                  5.2. Сортировка вставками
                 Сортировка простыми вставками
    Пусть ключи K1 , K2 , ..., Kj−1 уже упорядочены, т. е. K1 ≤ K2 ≤
... ≤ Kj−1 . Ключ Kj последовательно сравниваем с ключами Kj−1 ,
Kj−2 , ... , K1 , сдвигая при необходимости ключи на одну позицию
вверх до тех пор, пока не найдем место ключа Kj в упорядоченном
массиве.

       Пример: 7, 5, 1, 10, 4
               5, 7, 1, 10, 4
               5, 1, 7, 10, 4
               1, 5, 7, 10, 4
               1, 5, 7, 4, 10
               1, 5, 4, 7, 10
               1, 4, 5, 7, 10
   Для поиска места для ключа Kj необходимо произвести в среднем
j−1
 2  сравнений. Тогда среднее число сравнений вычисляется по фор-
муле T = 1 + 2 + ... + j−1       n−1
                        2 + ... + 2 . Среднее время работы алгоритма
               2
равно T = C · n .

                             Метод Шелла
  Пусть даны ключи: K1 , K2 , ..., K8 и задана последовательность це-
лых чисел (шагов) h = (4, 2, 1).

  1) сортируем ключи, отстоящие друг от друга на четыре позиции,
     т. е. пары (K1 , K5 ), (K2 , K6 ), (K3 , K7 ), (K4 , K8 ) методом простых
     вставок;
  2) сортируем ключи, отстающие друг от друга на 2 позиции, т. е.
     четверки (K1 , K3 , K5 , K7 ), (K2 , K4 , K6 , K8 ) методом простых вста-
     вок;
  3) сортируем весь массив методом простых вставок.

Страницы