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

1. Задать массив А из n чисел.

2. Для k от0 до n -1

2.1. j = k

2.2. Для i от k + 1 до n-1

2.2.1. Если A_i < A_j,

j = i.

2.3. Если k ≠ j, то

Поменять местами A_k и A_j.

3. Вывести массив A.

4. Закончить.

Число сравнений и пересылок в худшем случае пропорционально n², т.е. сложность алгоритма равна О(n²), а в среднем - О(n*log(n)). Таким образом, сортировка выбором предпочтительнее метода вставок.

 

3.2.3. Сортировка обменом
(Пузырьковая сортировка)

 

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

1) элементы массива сравниваются попарно: первое со вторым; второе с третьим; i -тое – с (i +1) - вым;

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

За один такой просмотр массива при сортировке по возрастанию минимальный элемент «вытолкнется», по крайней мере, на одно место вверх (вперед), а максимальный – переместится в самый конец (вниз). Таким образом, минимальный элемент как легкий пузырек воздуха в жидкости постепенно «всплывает» вверх (в начало последовательности). Отсюда – название метода.

Большие числа сразу оказываются на своем месте, т.е. глубину просмотра можно уменьшать, а индекс элемента изменять не до n -1, а до n - k. В нем последние числа, которые стоят на своем месте, выделены жирным шрифтом.

За n- 1 просмотр произойдет полное упорядочение массива при любом исходном расположении элементов в нем.

Алгоритм сортировки пузырьком

1. Задать массив из n чисел.

2. Для номера_просмотра (k) от 1 до n -1 выполнить

2.1. Для номера_элемента (i) от 0 до n - k выполнить

Если элементы i -тый и (i +1)-вый стоят неправильно, то

Поменять их местами;

3. Вывести отсортированный массив.

4. Закончить.

Сокращение количества просмотров улучшает временные характеристики метода. Из алгоритма можно понять, что если на одном из просмотров не было перестановок, то их не будет и потом – данные уже отсортированы, а процесс следует закончить. Такой подход дает значительную экономию времени при работе с большими «почти отсортированными» массивами.

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

Алгоритм ускоренной сортировки пузырьком

 

1. Задать массив из n чисел.

2.1 Номер_просмотра (k) = 1.

2.2. Повторять

2.2.1. Перестановка = ложь.

2.2.2. Для i от 0 до n-k выполнить

Если элементы i -тый и (i +1)-вый стоят неправильно, то

a) Поменять местами i -тый и (i +1)-вый элементы;

b) Перестановка = истина.

2.2.3. k = k +1

Пока Перестановка.

3. Вывести отсортированный массив.

4. Закончить.

Число сравнений и пересылок даже ускоренного алгоритма пузырьковой сортировки в худшем случае пропорционально n², т.е. его сложность равна О(n²).

 

3.2.4.Сортировка Шейкером

 

Метод является усовершенствованием алгоритма «пузырька». В нем на каждом проходе массив просматривается слева направо до середины, а потом – наоборот (справа налево). В результате, как при сортировке «пузырьком», при просмотре слева направо максимальный элемент попадает на свое место, а при обратном – минимальный. Таким образом, за каждый проход два элемента оказываются на своих местах, поэтому понадобится n /2 проходов, где n — количество элементов.

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