8. Основные идеи методов сортировок с помощью вставок.

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

• сортируем первые два элемента

• смотрим третий элемент и вставляем его в нужную позицию по отношению к первым двум

Продолжаем процесс до конца сортируемого множества.

Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отсортированными).

Основная идея методов

b1…bj-1 bj… bn ((|b₁ b₂ …b_j-1 |b_j b_j+1 ..b_n)) сказать про отсортированную часть..

1)Метод простых вставок: (сортировка по возрастанию)

2)Улучшение метода простых вставок:

Для поиска места вставляемого эл-та исп. метод двоичного поиска, метод деления пополам.

b1 b2 b3 b4 b5a

3) сортировка с убывающем смещением = сортировка Шелла

9. Сортировка методом простых вставок.

Метод простых вставок: (сортировка по возрастанию)

b1…bj-1 bj… bn

k1<=k2<=…<kj-1

Берем bj и сравниваем с bj-1. Если bj > bj-1 – все ок. Иначе если bj < bj-1, тогда сравниваем bj и bj-2

Операции сравнения и перемещения эл. по отсортированной части чередуют между собой. Метод просеивания или погружения.

Алгоритм:

1. запоминание bj в Х

2. сравниваем эл. bj-1 с Х

3. если меньше, чем Х, то просмотр закончен, т.к. bj уже на своем месте. Увеличиваем отсортированную часть на 1 эл. и Шаг 1.

4. если больше, то сдвиг в отсортирован. части влево (перемещ. bj-1 вперед на 1 эл.) и сравнение bj-2 с Х.

В начальный момент мы берем только 1 эл.

Пример этого метода:

4

1

5

1

7

3

6

х=1

сравниваем 4 и 1.

4>1 =>

4

4

5

1

7

3

6

1

4

5

1

7

3

6

х=5

сравниваем 4 с 5

все остается также.

х=1

1

4

5

5

7

3

6

1

4

4

5

7

3

6

1

1

4

5

7

3

6

х=7

также

х=3

1	1	4	5	7	7	6
1	1	4	5	5	7	6
1	1	4	4	5	7	6
1	1	3	4	5	7	6

х=6

1	2	3	4	5	7	7
1	1	3	4	5	6	7

10. Основные идеи методов сортировок с помощью выбора.-min эл.

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

//Один из самых простых методов сортировки работает следующим образом: находим наименьший элемент в массиве и обмениваем его с элементом находящимся на первом месте, потом повторяем процесс со второй позиции в файле и найденный элемент обмениваем со вторым элементом и так далее пока весь массив не будет отсортирован. Этот метод называется сортировка выбором поскольку он работает циклически выбирая наименьший из оставшихся элементов.

Есть массив элементов |b₁ b₂ …|b_i ..b_n|

На некотором i-ом этапе сортировки среди элементов b_i…b_n выбирается эл b_j с наименьшим ключом и он меняется местами с эл b_i. В результате после выполнения н-1 этапов сортировки получаем отсортированный массив.

|b₁ b₂ …|b_i ..b_j b_n|

Эта сортировка начинается с того, что отсортированная часть = 0.Заканчивается, когда в ее отсортированной части остается 1 элемент