Информатика -продвинутый курс




ВАЖНЕЙШИЕ НЕВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ (ПОИСК И СОРТИРОВКА) - часть 6


for i:=l to N do

begin write(a[i], ' ');

end; , readln;

end.

Один из вариантов улучшенной сортировки включением был предложен Д.Шеллом. Его метод предполагает сначала отдельную группировку и сортировку элементов, отстоящих друг от друга на некотором расстоянии, например 4 (четвертная сортировка), после первого прохода перегруппировку элементов таким образом, чтобы каждый элемент группы отстоял от другого на 2 номера, после двойной сортировки на третьем проходе одинарную (обычную) сортировку.

Исходные элементы

44

55

12

42

94

18

6

67

Четвертная сортировка

44

18

6

42

94

55

12

67

Двойная сортировка

6

18

12

42

44

55

94

67

Одинарная сортировка

6

12

18

42

44

55

67

94

Каждая из сортировок основывается на алгоритме прямого включения и, соответственно, должна программироваться аналогично. Если для условия окончания поиска использовать барьер, а их необходимо ставить для каждой из сортировок, то необходимо расширить границы массива на несколько компонентов (барьеров) влево, т.е. использовать массив а[-r..n], где r - количество сортировок.

Сортировка с помощью прямого выбора.

Алгоритм прямого выбора является одним из распространенных в силу своей простоты. Сначала определяют минимальный элемент среди всех элементов массива, затем его меняют местами с первым. Далее процесс повторяется с той лишь разницей, что минимальный ищется со второго и меняется со вторым и т.д.

1

2

3

4

5

12

15

17

11

13

i=2, min= 11

11

15

17

12

13

i=3.min=12

11

12

17

15

13

i=4, min=13

11

12

13

15

17

i=5,min=15.

<


Содержание  Назад  Вперед