алгоритмы сортировки ответы на вопросы vkclub152685050

Теперь запишем алгоритм:

procedure DispersSort(n, m: integer;

var A: array[1..n] of integer);

{Процедура сортировки вырожденным распределением} var

i, j, k: integer;

Amount: array[1..m] of integer; begin

{Обнуляем массив Amount}

for i := 0 to m do Amount[i] := 0; {Заполняем массив Amount}

for i := 1 to n do Amount[A[i]] := Amount[A[i]] + 1;

{Заполняем массив A} k := 1;

for i := 0 to M do

for j := 1 to Amount[i] do begin

A[k] := i; k := k + 1;

end;

end;

Временную сложность метода можно оценить как O(m+n) (m появляется в сумме, так как изначально надо обнулить массив Amount, а это требует m действий). Пространственная сложность в этом случае пропорциональна O(m), поскольку требуется дополнительная память размером порядка m.

Недостатком этого метода является то, что требуется дополнительная память размером порядка m, а это может оказаться недопустимым из-за большого значения m. Но, если m>>n, то имеется способ уменьшить объем требуемой дополнительной памяти, который сейчас и рассмотрим, как общий случай сортировки распределением.

Пусть выделяется дополнительная память размером b+n, а элементы массива могут принимать значения от 0 до s, причем s>>b.

Каждый элемент этого массива можно представить в b-ичной системе счисления и разбить на k цифр этой системы счисления.

Заведем списки L1, L2, …, Lb общей суммарной длиной порядка n (это можно сделать, ограничившись дополнительной памятью O(b+n)) (рис. 48).

Тогда алгоритм сортировки распределением можно представить следующим образом:

vk.com/club152685050

vk.com/id446425943

for i := k downto 1 do begin for j := 1 to n do begin

if p = i-й цифре A[j] в b-й системе счисления then занести A[j] в L[p] список;

end;

Очистить массив A; for j := 1 to b do

Дописать элементы L[j] в массив A; end;

A

0

1

81

64

12

4

25

36

22

16

9

49

	Списки L
0	0
1	1		81
2	12		22
3
4	64		4
5	25
6	36		16
7
8
9	9		49

k = 1 (правый разряд)

		Списки L
0	0	1		4	9
1	12	16
2	22	25

336

4 49

5

6 64

7

8 81

9

vk.com/club152685050									k = 2 (левый разряд)
vk.com/id446425943								A
	0		1	4	9	12	16	22	25	36	49	64	81

Рис. 48. Сортировка распределением

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

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

Достигнув i = 1, получаем полностью отсортированный массив. Как нетрудно заметить, если положить s = b, то отпадает необходи-

мость заводить списки и производить запись в них: в j-ый список будут попадать только числа, равные j. В этом случае достаточно хранить лишь размеры списков, т. е. подсчитать количество элементов, равных j, для всех j от 1 до s. А потом просто заново заполнить массив A в соответствии с этими количествами, т. е. получаем вырожденную сортировку.

Рассмотрим на примере задачу сортировки 12 целых чисел из интервала от 0 до 99, т. е. n = 12, b = 10 (десятичная система счисления), s = =99, k = 2 (два разряда). При этом будем считать, что числа, содержащие только один разряд, дополняются слева нулем, т. е. число «0» будет «00», число «1» будет «01» и т. д.

Интересно, что временная сложность этого алгоритма пропорциональна O(k·n), а если учесть, что k фактически является константой, то получаем гарантированную (минимальную, среднюю и максимальную) линейную сложность. Но недостатком этого метода является необходимость выделять дополнительную память размером порядка b + n. Если бы не это ограничение, можно было бы считать этот метод самым эффективным при больших значениях n.

2.5.2.10. Сравнение алгоритмов внутренней сортировки

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

Теоретические временные и пространственные сложности рассмотренных методов сортировки показаны в табл. 4.

Эта таблица позволяет сделать ряд выводов.

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

						Таблица 4
Метод сортировки			Характеристики
	Tmax		Tmid		Tmin	Vmax
Подсчет			O(n2)			O(n)
Включение		O(n2)			O(n)	O(1)
Шелла	O(n2)		O(n1,25)		O(n)	O(1)
Извлечение			O(n2)			O(1)
Древесная			O(n*log n)			O(1)
Пузырьковая		O(n2)			O(n)	O(1)
Быстрая	O(n2)		O(n*log n)			O(log n)
Слияние			O(n*log n)			O(n)
Распределение			O(n)			O(n)

vk.com/club152685050

vk.com/id446425943

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

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

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

4.При сортировке больших массивов исходных данных лучше использовать быструю сортировку.

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

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

2.5.3. Алгоритмы внешней сортировки

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

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

Применение большинства алгоритмов внутренней сортировки для сортировки файлов требует порядка O(n) проходов. Однако, если несколько модифицировать алгоритм сортировки слиянием (см. п. 2.5.2.8), то можно произвести сортировку, осуществляя порядка O(log n) проходов.

Основное отличие сортировки слиянием для файлов, заключается в следующем. Вся сортируемая последовательность данных разбивается на два файла f1 и f2. Желательно, чтобы количество записей в этих файлах было поровну. Как и в алгоритме внутренней сортировки, считаем, что любой файл состоит из участков длиной 1. Затем можно объединить участки длины 1 и распределить их по файлам g1 и g2 в виде участков длины 2. После этого делаем f1 и f2 пустыми и объединяем g1 и g2 в f1 и f2, которые затем можно организовать в виде участков длины 4 и т. д.

После выполнения i подобного рода проходов получатся два файла, состоящие из участков длины 2i. Если 2i ≥ n, тогда один из этих двух файлов будет пустым, а другой будет содержать единственный участок длиной n, т. е. будет отсортирован. Так как 2i ≥ n при i ≥ log n, то не-

трудно заметить, что в этом случае будет достаточно порядка O(log n) проходов по данным.

Пример внешней сортировки слиянием приведен на рис. 49.

						Исходные файлы																									Участки длиной 2
28		3		93		10		54		65		30		90					28				31			93				96			54				85				30		39
31		5		96		40		85		9		39							3				5			10				40					9		65				90
				Участки длиной 4																							Участки длиной 8
3		5		28		31		9		54		65		85						3				5				10			28				31				40		93			96
10		40		93		96		30		39		90								9				30				39			54				65				85		90
															Участки длиной 16
		3		5		9		10		28		30		31			39	40				54				65			85				90			93				96

Рис. 49. Внешняя сортировка слиянием

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

vk.com/club152685050

vk.com/id446425943

vk.com/id446425943

vk.com/club152685050

ЛАБОРАТОРНАЯ РАБОТА №5 «АЛГОРИТМЫ СОРТИРОВКИ»

1.1 Цель работы

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

1.2 Задание на лабораторную работу

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

1)Поиск элемента либо по его порядковой позиции, либо по его содержимому;

2)Добавление/удаление элемента с последующей пересортировкой последовательности;

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

Варианты задания приведены в таблице 5.

			Таблица 1
№		Задание	Алгоритм сортировки
вар.
1	Найти количество	различных чисел среди элементов	Подсчетом
	массива
2		//	Простым включением
3		//	Шелла
4		//	Простым извлечением
5		//	Шейкерная
6		//	Чѐтно – нечѐтная
7		//	Расческой
8		//	Быстрая (Хоара)
9		//	Слиянием
10		//	Распределением
11	Найти количество повторяющихся чисел среди элементов		Подсчетом
	массива
12		//	Простым включением
13		//	Шелла
14		//	Простым извлечением
15		//	Шейкерная

	№	Задание	Алгоритм сортировки
	вар.
	16	//	Чѐтно – нечѐтная
	17	//	Быстрая (Хоара)
	18	//	Слиянием
	19	//	Распределением
	20	//	Расческой
	21	Найти k-ое по порядку число среди элементов массива	Подсчетом
	22	//	Простым включением
	23	//	Шелла
	24	//	Простым извлечением
	25	//	Шейкерная
	26	//	Чѐтно – нечѐтная
	27	//	Расческой
	28	//	Быстрая (Хоара)

1.3Порядок выполнения работы

1)выбрать вариант задания из подраздела в соответствии с требованиями;

2)изучить теоретический материал;

3)разработать и реализовать на языке программирования высокого уровня алгоритм, выполняющий требования задания;

4)подсчитать количество выполненных операций сравнения и перестановок элементов массива;

5)подсчитать сложность алгоритма

6)написать отчет о работе;

7)защитить отчет.

1.4Содержание отчета

Отчет должен содержать:

1)титульный лист;

2)цель работы;

3)вариант задания;

4)листинг программы, реализующей алгоритм;

5)контрольный пример;

6)количество выполненных операций сравнения и перестановок элементов массива;

2

7)временную и пространственную сложность алгоритма;

8)выводы по работе.

1.5Описание алгоритмов сортировки

Вданном разделе приведено описание некоторых алгоритмов сортировки, которые по своей сути являются модификацией алгоритма сортировки «Пузырьком.

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

Процесс сортировки на первой итерации схож с сортировкой «Пузырьком». Выполняется проход массива из n элементов слева - направо и попарно сравниваются элементы. Если левый элемент больше правого, они меняются местами. По окончанию итерации самый правый элемент будет максимальным. Затем происходит обход в обратную сторону, не затрагивающий последний отсортированный правый элемент. В результате обратного обхода самый левый элемент будет минимальным. Далее процедура повторяется, и, при каждом обходе слева - направо происходит сдвиг начала операций сравнений на +1, в обходе же справа – налево на -1. Выполнение алгоритма прекращается, когда произведена последняя перестановка в центре массива.

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

Итерации		Элементы
Начало		5	7	9	1	3	8
1	->	5	7	1	3	8	9
2	<-	1	5	7	3	8	9
3	->	1	5	3	7	8	9
4	<-	1	3	5	7	8	9
5	-> - Конец	1	3	5	7	8	9

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

Алгоритм имеет следующие сложности:

3

Худшее время:	O(n2)
Лучшее время:	O(n)
Среднее время:	O(n2)
Затраты памяти:	O(n)

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

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

Итерации		Элементы
Начало	5		7				9			1			3			8
1	5		7					1		9			3			8
2	5				1	7					3	9				8
3		1	5					3		7				8		9
4	1			3		5					7	8				9
5	1		3				5			7			8			9
6 - Конец	1				3	5					7	8				9

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

Алгоритм имеет следующие сложности:

Худшее время:	O(n2)
Лучшее время:	O(n)
Среднее время:	O(n2)
Затраты памяти:	O(n)

4