Сортировка с помощью прямого обмена

Сортировка с помощью прямого выбора

Сортировка массива размером n в неубывающем (невозрастающем) порядке методом прямого выбора выполняется по следующему алгоритму.

1. Выбирается элемент данного массива с минимальным (максимальным) значением (или ключом).

2. Выбранный элемент и первый элемент меняются местами.

3. Этот процесс повторяется с оставшимися n - 1 элементами, затем с n - 2 элементами и т.д. до тех пор, пока не останется один, самый большой (меньший) элемент.

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

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

Напомним, что во всех рассматриваемых методах сортировки мы не используем промежуточных массивов.

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

Исходный массив:		-14					-5					-15^*
1-й шаг	-15	-14^*					-5
2-й шаг:	-15	-14					-5^*
3-й шаг:	-15	-14	-5						0^*
4-й шаг:	-15	-14	-5		6^*
5-й шаг:	-15	-14	-5								6^*
6-й шаг:	-15	-14	-5				13^*
7-й шаг:	-15	-14	-5					18^*
8-й шаг:	-15	-14	-5									22^*
9-й шаг:	-15	-14	-5									28^*
10-й шаг:	-15	-14	-5									35
11-й шаг:	-15	-14	-5

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

Пусть задан массив a размером n. Начинаем просмотр массива с первой пары элементов a[1] и a[2]. Если первый элемент этой пары больше второго, то меняем их местами, иначе оставляем их без изменения и сравниваем вторую пару элементов а[2] и а[3]. Если а|2] > а[3], то меняем их местами и т.д. На первом шаге будут просмотрены все пары элементов массива: а[i] и а[i+1] для i от 1 до n -1. В результате такого просмотра и необходимых обменов максимальный элемент переместится в конец массива и будет являться отсортированной частью. На втором шаге аналогичная процедура проводится с первого до (n - 1)-гo элемента. Тем самым второй по величине элемент массива переместится на предпоследнее место. Отсортированная часть будет содержать два элемента. Эти действия продолжаются до тех пор, пока количество элементов в неотсортированной части массива не уменьшится до двух.Нaпоследнем шаге выполняется упорядочение оставшихся двух элементов. После (n - 1) шагов массив окажется отсортированным по неубыванию. Для иллюстрации отсортируем массив по неубыванию методом простого обмена. Отсортированная часть выделена полужирным шрифтом.

Исходный массив:		-14					-5					-15
1-й шаг	-14					-5					-15
2-й шаг:	-14				-5					-15
3-й шаг:	-14			-5					-15
4-й шаг:	-14		-5					-15
5-й шаг:	-14	-5					-15
6-й шаг:	-14	-5				-15
7-й шаг:	-14	-5			-15
8-й шаг:	-14	-5		-15
9-й шаг:	-14	-5	-15
10-й шаг:	-14	-15	-5
11-й шаг:	-15	-14	-5

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

Лабораторная работа № 9
Задачи сортировки и поиска

ЦЕЛЬ РАБОТЫ: Закрепление теоретических знаний и приобретение практических навыков по составлению алгоритмов и программ различных методов сортировки.

Выполнение работы:

1. Сформировать при помощи генератора псевдослучайных чисел линейный целочисленный массив A[20], таким образом, что бы элементы массива принадлежали отрезку [-50, 50].

2. Выполнить в нём линейный поиск заданного элемента.

3. Отсортировать массив определённым методом в соответствии с вариантом (см. таблицу).

4. Выполнить бинарный поиск элемента.

Дата добавления: 2014-11-16