Методы сортировки данных

Алгоритм сортировки вставкой

Суть сортировки:
Упорядочиваются два элемента массива
Вставка третьего элемента в соответствующее место

Сортировка вставкой

13

6

2

10

8

13

6

8

2

13

6

8

8

13

13

10

6<13

8>6 8<13

2<6 2<8 2<13

10<13

Массив отсортирован по возрастанию

по возрастанию

Пусть нужно отсортировать массив А по возрастанию, в котором N элементов

Начало алгоритма.
Шаг 1 j:=2,
Шаг 2 Пока j<=N выполнять:
Шаг 2.1 i:=j; f:=0,
Шаг

Алгоритм сортировки выбором

Суть сортировки:
Выбирается элемент с наименьшим значением и делается его обмен с

13

6

2

10

8

Сортировка выбором

Min

2

Min

6

Min

8

13

Min

10

13

Отсортиро-ванная часть

Отсортированная часть

Отсортированная часть

Массив отсортирован по возрастанию

по возрастанию

Постановка задачи

Пусть нужно отсортировать массив А по возрастанию, в котором N

Начало алгоритма.
Шаг 1 j:=1,
Шаг 2 Пока j<=N-1 выполнять:
Шаг 2.1 min:=a[j],

Алгоритм сортировки обменом («пузырьковая»)

Суть сортировки:
Последовательно просматривается массив и сравнивается каждая пара элементов между собой.

Сортировка обменом

13

6

2

10

8

Первый просмотр

6

13

8

13

13

2

10

13

Второй просмотр

6

8

2

8

Третий просмотр

6

2

6

Четвертый просмотр

2

6<13

8<13

2<13

10<13

Отсортиро-ванная часть

Отсортированная часть

Отсортированная часть

Массив отсортирован по

Пусть нужно отсортировать массив А по возрастанию, в котором N элементов

Начало алгоритма.
Шаг 1 j:=N,
Шаг 2 Пока j>=2 выполнять:
Шаг 2.1 i:=1; ,
Шаг

Алгоритм сортировки Шелла

Классифицируется как «слияние вставкой»;
Называется «сортировкой с убывающим шагом»
Общий метод, который использует

Условия реализации:
Конкретная последовательность шагов может быть другой, но последний шаг должен

Суть сортировки:
Сначала сортируются все элементы, отстоящие друг от друга на три

12

Сортировка Шелла

8

14

6

4

1

2

3

4

1

2

1 шаг. 4 группы из 2-х элементов

1

7

3

4

12

4

8

9

9

1

14

7

6

2 шаг. 2 группы

Сортировка Шелла

4

1

6

3 шаг. 1 группа из 8-ми элементов

Массив отсортирован по возрастанию

по

Пусть нужно отсортировать массив А по возрастанию, в котором N элементов

Начало алгоритма.
Шаг 1. M=целая часть N/2
Шаг 2. Пока M<>0 выполнять
Шаг

Алгоритм быстрой сортировки

Придумана Ч.А.Р. Хоаром (Charles Antony Richard Hoare);
В основе – сортировка обменами;
Основана

Суть сортировки:
Выбирается некоторое значение (x)- барьерный элемент, который определяется округлением до

Суть сортировки:

Меняем найденные элементы местами. В случае, если не найден наибольший

Быстрая сортировка

8

12

3

7

19

11

4

16

Барьерный элемент

4

3

7

8

12

3

4

Барьерный элемент

8

12

11

19

Барьерный элемент

12

19

16

19

8>7 переносим в правую часть, т. к.

Пусть нужно отсортировать массив А по возрастанию, в котором n элементов