Сортировка с помощью прямого обмена
Сортировка с помощью прямого выбора
Сортировка массива размером 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. Выполнить бинарный поиск элемента.