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

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

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

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

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