ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ. Под сортировкой обычно понимают процесс перестановки элементов данного множества в определенном порядке.

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

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

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

Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, что переупорядочивание элементов нужно выполнять на одном и том же месте и что методы, которые пересылают элементы из массива А в массив В, не представляют для нас интереса. Проблема сортировки массивов относится в информатике к классичес­ким. Она кажется простой, ведь всем приходилось выполнять какую-либо механическую сортировку, была ли то раскладка игральных карт, гардеробных номерков, карточек из библиотечного каталога или денежных счетов. Однако простота эта иллюзорна. Хотя первые программы сортировки были написаны Дж. фон Нейманом в 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.)

Сортировка выбором

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

Выбранный в исходной последовательности минимальный элемент размещается на предназначенном ему месте упорядоченной последовательности несколькими способами:

а) минимальный элемент после i-го просмотра перемещается на i-е место (i=1,2,3,...) другого специально созданного массива, а в старом, исходном, на месте выбранного размещается какое-то очень большое число, превосходящее по величине любой элемент сортируемого массива. Измененный таким образом массив принимается за исходный, и осуществляется следующий просмотр;

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

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

Не нашли, что искали? Воспользуйтесь поиском: