Быстрая сортировка ( сортировка Хоара )

Теоретическая и практическая часть

Методы сортировки

Упорядочение элементов множества в возрастающем или убывающем порядке называется сортировкой.

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

Алгоритмы сортировки можно разбить на следующие группы: (рис. 1).

Методы сортировки

Сортировка в линейных структурах

Сортировка в нелинейных структурах

вставка	выбор	обмен	турнирная	пирамидальная
простая вставка	простой выбор	1. стандартный обмен
		2. Метод Шелла
бинарная вставка		3. Метод Хоара

Рис. 1 Алгоритмы сортировки

Обычно сортируемые элементы множества называют записями и обозначают через .

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

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

Например, требуется найти минимальный элемент списка:

{5, 11,6,4,9,2, 15, 7}.

Процесс выбора показан на рис. 2, где в каждой строчке выписаны сравниваемые пары. Выбираемые элементы с меньшим весом подчеркнуты. Нетрудно видеть, что число сравнений соответствует на рисунке числу строк, а число перемещений — количеству изменений выбранного элемента.

{5, 11, 6, 4, 9, 2, 15, 7}

5 11

5 6

5 4

4 9

4 2

2 15

2 7

Рис. 2. Сортировка выбором

Выбранный в исходном списке минимальный элемент размещается на предназначенном ему месте несколькими способами:

минимальный элемент после i-го просмотра перемещается на i-е место нового списка (i =1, 2, ..., п), а в исходном списке на место выбранного элемента записывается какое-то очень большое число, превосходящее по величине любой элемент списка, при этом длина заданного списка остается постоянной. Измененный таким образом список можно принимать за исходный;

· минимальный элемент записывается на i-е место исходного списка ( ), а элемент с i-го места — на место выбранного. При этом очевидно, что уже упорядоченные элементы (а они будут расположены, начиная с первого места) исключаются из дальнейшей сортировки, поэтому длина каждого последующего списка (списка, участвующего в каждом последующем просмотре) должна быть на один элемент меньше предыдущего;

· выбранный минимальный элемент, как и в предыдущем случае, перемещается на i -е место заданного списка, а чтобы это i-е место освободилось для записи очередного минимального элемента, левая от выбранного элемента часть списка перемещается вправо на одну позицию так, чтобы заполнилось место, занимаемое до этого выбранным элементом (элементы списка циклически сдвигаются).

Сложность метода сортировки выбором порядка составляет О(п²).

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

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

Сортировку вставкой рассмотрим на примере заданной неупорядоченной последовательности элементов:

{40, 11, 83, 57, 32, 21, 75, 64}.

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

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

На втором этапе из неупорядоченной последовательности выбирается элемент и сравнивается с двумя упорядоченными ранее элементами. Так как он больше предыдущих, то остается на месте. Затем анализируются четвертый, пятый и последующие элементы — до тех пор, пока весь список не будет упорядочен, что имеет место на последнем (седьмом) этапе.

1-й

40, 11, 83, 57, 32, 21, 75, 64

|11, 40,| 83, 57, 32, 21, 75, 64

2-й

11, 40, 83, 57, 32, 21, 75, 64

|11, 40, 57,| 83, 32, 21, 75, 64

3-й

11, 40, 83, 57, 32, 21, 75, 64

|11, 40, 57, 83,| 32, 21, 75, 64

4-й

11, 40, 57, 83, 32, 21, 75, 64

|11, 32, 40, 57, 83,| 21, 75, 64

5-й

11, 32, 40, 57, 83, 21, 75, 64

[11, 21, 32, 40, 57, 83,] 75, 64

6-й

11, 21, 32, 40, 57, 83, 75, 64

[11, 21, 32, 40, 5 7, 75, 83,] 64

7-й

11, 21, 32, 40, 57, 75, 83, 64

[11, 21, 32, 40, 57, 64, 75, 83]

Рис. 3. Сортировка вставкой

1.3 Сортировка слиянием

Разновидностью сортировки вставкой является метод фон Неймана.

Алгоритм решения этой задачи, известный как «сортировка фон Неймана» или сортировка слиянием, состоит в следующем: сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив. Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив. Полученный новый массив упорядочен таким же образом, как исходные.

Пусть имеются два отсортированных в порядке возрастания массива и и имеется пустой , который необходимо заполнить значениями массивов р и q в порядке возрастания. Для слияния выполняются следующие действия: сравниваются р[1] и q [1], и меньшее из значений записывается в r [1]. Предположим, что это значение р[1]. Тогда р[2] сравнивается с q [1] и меньшее из значений заносится в r [2]. Предположим, что это значение q [1]. Тогда на следующем шаге сравниваются значения р[2] и q [2] и т. д., пока не достигнута граница одного из массивов. Тогда остаток другого массива просто дописывается в «хвост» массива r.

Пример слияния двух массивов показан на рис. 4.

Сложность метода сортировки вставкой порядка О(п²).

1 шаг

255

2 шаг

255

3 шаг

255

4 шаг

255

5 шаг

255

6 шаг

255

7 шаг

255

5 шаг

255

Рис. 4. Сортировка слиянием

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

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

Требуется, например, провести сортировку списка методом •стандартного обмена или методом «пузырька»:

{40, 11, 83, 57, 32, 21, 75, 64}.

Первый этап сортировки показан на рис. 5, а второй этап — на рис. 6.

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

Второй просмотр выявляет максимальный элемент, равный 75 (см. рис. 5).

Процесс сортировки продолжается до тех пор, пока не будут сформированы все элементы конечного списка либо не выполнится условие Айверсона.

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

Исходный список	40	11	83	57	32	21	75	64
	11	40 40	83
Первый просмотр			57	83 32	83
					21	83
						75	83 64	83
Полученный список	11	40	57	32	21	75	64	83

Рис. 5. Сортировка обменом (первый просмотр)

Исходный список	11	40	57	32	21	75	64
	11	40
		40	57
Второй просмотр			32	57
				21	57
					57	75
						64	75
Полученный список	11	40	32	21	57	64	75

Рис.6. Сортировка обменом (второй просмотр)

Шейкерная сортировка

Модификацией сортировки стандартным обменом является шейкерная или челночная сортировка. Здесь, как и в методе пузырька, проводится попарное сравнение элементов. При этом первый проход осуществляется слева направо, второй — справа налево и т. д. Иными словами, меняется направление просмотра элементов списка.

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

-------------------------------------------------------------------------------------------------------------------------------------

Исходный массив:

27 412 71 81 59 14 273 87

Шаги сортировки:

14 27 412 71 81 59 87 273

14 27 71 81 59 87 273 412

14 27 59 71 81 87 273 412

Отсортированный массив

14 27 59 71 81 87 273 412

-------------------------------------------------------------------------------------------------------------------------------------

Сложность метода стандартного обмена — О(п²).

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

В методе Шелла сравниваются не соседние элементы, а элементы, расположенные на расстоянии ( ) (где — шаг между сравниваемыми элементами, [ ] — целая часть от числа). После каждого просмотра шаг уменьшается вдвое. На последнем просмотре он сокращается до .

Например, пусть дан список, в котором число элементов четно:

{40, 11, 83, 57, 32, 21, 75, 64}.

Список длины п разбивается на п/2 частей, т. е. .

При первом просмотре сравниваются элементы, отстоящие друг от друга на (рис. 7), т. е. и т. д. Если , то происходит обмен между позициями i и i + d . Перед вторым просмотром выбирается шаг (рис. 8). Затем выбираем шаг (рис. 9), т. е. имеем аналогию с методом стандартного обмена.

Сложность метода Шелла — .

Исходный массив	40	11	83	57	32	21	75	64
	32				40
		11				21
			75				83
				57				64
Полученный массив	32	11	75	57	40	21	83	64

Рис. 7. Метод Шелла (шаг ( )

Исходный массив	32	11	75	57	40	21	83	64
	32		75
		11		57
			40		75
				21		57
					75		83
						57		64
Полученный массив	32	11	40	21	75	57	83	64

Рис. 8. Метод Шелла (шаг ( )

Исходный массив	32	11	40	21	75	57	83	64
	11	32
		32	40
			21	40
				40	75
					57	75
						75	83
							64	83
Полученный массив	11	32	21	40	57	75	64	83

Рис. 9. Метод Шелла (шаг ( )

Быстрая сортировка ( сортировка Хоара )

В методе быстрой сортировки фиксируется какой - либо ключ (базовый), относительно которого все элементы с большим весом перебрасываются вправо, а с меньшим — влево. При этом весь список элементов делится относительно базового ключа на две части. Для каждой части процесс повторяется.

Поясним метод на примере.

На рис.10 представлен первый этап быстрой сортировки. В первой строке указана исходная последовательность.

Примем первый элемент последовательности за базовый ключ, выделим его квадратом и обозначим . Установим два указателя: i и j, из которых i начинает отсчет слева (i= 1), а j — справа (j = п).

Сравниваем базовый ключ и текущий ключ . Если , то устанавливаем и проводим следующее сравнение и . Продолжаем уменьшать j до тех пор, пока не достигнем условия . После этого меняем местами ключи и (шаг 3 на рис. 10).

Рис. 10. Метод Хоара

Теперь начинаем изменять индекс и сравнивать элементы и . Продолжаем увеличение i до тех пор, пока не получим условие , после чего следует обмен и (см. шаг 5). Снова возвращаемся к индексу j, уменьшаем его. Чередуя уменьшение j и увеличение i, продолжаем этот процесс с обоих концов к середине до тех пор, пока не получим (см. шаг 7).

В отличие от предыдущих рассмотренных сортировок уже на •м этапе имеют место два факта: во-первых, базовый ключ занял свое постоянное место в сортируемой последовательности; во-вторых, все элементы слева от будут меньше него, а справа — больше него. Таким образом, по окончании первого этапа имеем:

21, 11, 32	40	57, 83, 75, 64
Левая часть		Правая часть

Указанная процедура сортировки применяется независимо к левой и правой частям.

Сложность метода Хоара — .

Индивидуальные задания

Написать программу для каждого из перечисленных методов сортировки. Алгоритмы сортировок должны быть оформлены в виде функции.

Вариант				Составить программу
1, 9	1000	4000	6000	Простая вставка
2, 11	800	3000	7000	Сортировка слиянием
3, 13	2000	5000	6800	Метод Шелла
4, 15	1500	3500	6000	Простой выбор
5, 16	1000	2800	8500	Метод Хоара
6, 14	500	2500	6500	Бинарная вставка
7, 12	900	3000	8500	Шейкерная сортировка
8, 10	1200	2000	7500	Метод Шелла

Дата добавления: 2021-01-21; просмотров: 430; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!