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

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

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

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

Ниже мы рассмотрим методы сортировки элементов в массивах (методы сортировки массивов).

Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, что переупорядочивание элементов нужно выполнять на одном и том же месте и что методы, которые пересылают элементы из массива А в массив В, не представляют для нас интереса. Проблема сортировки массивов относится в информатике к классичес­ким. Она кажется простой, ведь всем приходилось выполнять какую-либо механическую сортировку, была ли то раскладка игральных карт, гардеробных номерков, карточек из библиотечного каталога или денежных счетов. Однако простота эта иллюзорна. Хотя первые программы сортировки были написаны Дж. фон Нейманом в 1945 г., какого-либо значительного продвижения в теории сортировки не наблюдалось в течение последующих двадцати лет.

Рассмотрим несколько методов сортировки массивов. Для определен­ности, приведем методы сортировки (упорядочивания) векторов по неубыванию.

Пусть n - число элементов вектора A, а iизменяется от 0 до n-2.

1. Вектор называется упорядоченным по неубыванию, если для всех i выполнено A(i)<=A(i+1).

2. Вектор называется упорядоченным по невозрастанию, если для всех i выполнено A(i)>=A(i+1).

3. Вектор называется упорядоченным по убыванию, если для всех i выполнено A(i)>A(i+1).

4. Вектор называется упорядоченным по возрастанию, если для всех i выполнено A(i)<A(i+1).

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

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

(См. Пример 1.)

Дата добавления: 2014-12-29