Материал: Глава 14. Алгоритмы сортировки

Скачать файл

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

if (mas[i] > mas[j])

на

if (mas[i] < mas[j]).

Данная функция возвращает отсортированный массив mas (строка 16)

§14.3 Простейшие методы сортировки: метод вставок

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

Пусть имеется n элементов а1 а2, а3, ..., аn, расположенных в ячейках массива. Сортировка выполняется за ( – 1) шаг, причем шаги удобно нумеровать от 2 до n. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

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

правую часть образуют еще не обработанные элементы аi, аi+1, аi+2,

. . ., аn

На шаге для элемента аi находится подходящее место в уже

отсортированной последовательности. Поиск подходящего места выполняется поэлементными сравнениями и перестановками по необходимости:

сравниваем аi с аi-1, если аi < аi-1, то переставляем их, потом сравниваем аi-1 с

аi-2 и т. д. Сравнения и, возможно, перестановки продолжаются до тех пор,

пока не будет выполнено одно из 2-х следующих условий:

в отсортированном наборе найден элемент, меньший аi (все остальные не просмотренные элементы будут еще меньше)

достигнут первый элемент набора а1, что произойдет в том случае,

если аi меньше всех элементов в отсортированном наборе и он должен занять первое место в массиве

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

		а1		а2		а3	а4	а5	а6	Выполняемые операции

шаг 2		15		33	42		07	12	19	сравнение 15 и 33, обмена нет, 15 – пока
шаг 2		15		33	42		07	12	19	первый
										первый

шаг 3	15			33		42	07	12	19	сравнение 33 и 42, обмена нет, 15 и 33 пока
шаг 3	15			33		42	07	12	19	первые
										первые

	15		33			07	42	12	19	сравнение 07 и 42, меняем их

							42	12	19	сравнение 07 и 33, меняем их
шаг 4	15			07		33	42	12	19	сравнение 07 и 33, меняем их
шаг 4
		07		15	33		42	12	19	сравнение 07 и 15, меняем их; 07-15-33 пока
		07		15	33		42	12	19	первые
										первые

	07		15		33		12	42	19	сравнение 12 и 42, меняем их

	07		15			12	33	42	19	сравнение 12 и 33, меняем их
шаг 5
шаг 5	07			12		15	33	42	19	сравнение 12 и 15, меняем их

		07		12	15		33	42	19	сравнение 12 и 07, обмена нет, пока: 07-12-
		07		12	15		33	42	19	15-33
										15-33

	07		12		15		33	19	42	сравнение 19 и 42, меняем их

шаг 6	07		12		15		19	33	42	сравнение 19 и 33, меняем их

									42	сравнение 19 и 15, обмена нет, все готово
	07		12			15	19	33	42	сравнение 19 и 15, обмена нет, все готово

Для данного примера было сделано 12 сравнений и 8 перестановок, что чуть лучше предыдущего метода. В среднем, число сравнений по данному методу примерно в 2 раза меньше, чем в методе пузырька, оставаясь тем не менее пропорциональным величине n2. Наилучший результат этот метод показывает для уже упорядоченного исходного массива – всего ( − 1)

сравнение.

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

	Пример программной реализации сортировки методом вставок
представлен в листинге 14.2.
		Листинг 14.2 – Сортировка методом вставок

	1	void InsertionSort(int n, int[] mass)
	2	{
	3	int newElement, location;
	4	for (int i = 1; i < n; i++)
	5	{
	6	newElement = mass[i];
	7	location = i - 1;
	8	while(location >= 0 && mass[location] > newElement)
	9	{
	10	mass[location + 1] = mass[location];
	11	location = location - 1;
	12	}
	13	mass[location + 1] = newElement;
	14	}
	15	}

§14.4 Простейшие методы сортировки: метод выбора

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

что в некоторых ситуациях выполняется перестановка не соседних элементов,

а отстоящих на некотором расстоянии друг от друга.

Пусть имеется n элементов а1 а2, а3, . . ., аn, расположенных в ячейках массива. Сортировка выполняется за ( – 1) шаг, пронумерованных от 1 до − 1. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

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

правую часть образуют еще не обработанные элементы аi, аi+1, аi+2, . . ., аn

Суть метода состоит в том, что в необработанном наборе отыскивается

наименьший элемент, который меняется местами с элементом аi. На первом шаге (при i = 1), когда необработанным является весь исходный набор, это

сводится к поиску наименьшего элемента в массиве и обмену его с первым элементом. Ясно, что поиск наименьшего элемента выполняется обычным попарным сравнением, но соседние элементы при этом не переставляются, что в целом уменьшает число пересылок.

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

	а1	а2	а3	а4	а5	а6	Выполняемые операции

шаг	15	33	42	07	12	19	сравнение 15 и 33, min = 15
1
1	15	33	42	07	12	19	сравнение 15 и 42, min = 15

	15	33	42	07	12	19	сравнение 15 и 07, min = 07

	15	33	42	07	12	19	сравнение 07 и 12, min = 07

	15	33	42	07	12	19	сравнение 07 и 19, min = 07, обмен 15 и
							07

шаг	07	33	42	15	12	19	сравнение 33 и 42, min = 33
2
2	07	33	42	15	12	19	сравнение 33 и 15, min = 15

	07	33	42	15	12	19	сравнение 15 и 12, min = 12

	07	33	42	15	12	19	сравнение 12 и 19, min = 12, обмен 33 и
							12

шаг	07	12	42	15	33	19	сравнение 42 и 15, min = 15
3
3	07	12	42	15	33	19	сравнение 15 и 33, min = 15

	07	12	42	15	33	19	сравнение 15 и 19, min = 15, обмен 42 и
							15

шаг	07	12	15	42	33	19	сравнение 42 и 33, min = 33
4
4	07	12	15	42	33	19	сравнение 33 и 19, min = 19, обмен 42 и
							19

шаг	07	12	15	19	33	42	сравнение 33 и 42, min = 33, обмена нет,
5							все готово

В данном примере сделано 15 сравнений (как и в методе пузырька), но всего 4 перестановки. Эта особенность сохраняется и в целом: по числу сравнений метод выбора близок к методу пузырька, но по числу перестановок

существенно превосходит оба рассмотренные выше методы (оценка числа перестановок n*log 2 n)

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

необработанной части массива.

	Пример программной реализации сортировки методом выбора
представлен в листинге 14.3.
		Листинг 14.3 – Сортировка методом выбора

	1	static int[] ViborSort(int[] mas)
	2	{
	3	for (int i = 0; i < mas.Length - 1; i++)
	4	{
	5	//поиск минимального числа
	6	int min=i;
	7	for (int j = i + 1; j < mas.Length; j++)
	8	{
	9	if (mas[j] < mas[min])
	10	{
	11	min = j;
	12	}
	13	}
	14	//обмен элементов
	15	int temp = mas[min];
	16	mas[min] = mas[i];
	17	mas[i] = temp;
	18	}
	19	return mas;
	20	}

Общее заключение по простейшим методам сортировки.

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

Метод вставок также дает хорошие результаты для упорядоченных входных данных (число сравнений и пересылок пропорционально n). Во всех

остальных случаях его показатели пропорциональны n2, хотя что касается

Источник: https://studfile.net/preview/16573799/

Смотрите также:

_1966(~1
_РГР № 1 (2)
"Логистическая технология JIT"
"Особенности правовой системы Российской Федерации" по дисциплине "Теория государства и права"
«Анализ ликвидности и платежеспособности предприятия» (на материалах ОАО Московская кондитерская фабрика «Красный Октябрь»)
«Дизайнерские дети» как профилактика инвалидизации общества
«ЗЕМЕЛЬНЫЕ РЕСУРСЫ КРАСНОДАРСКОГО КРАЯ»
«Методы учета затрат на производство продукции, работ, услуг»Курсовая работа
[2 курс] Определения
00338