Урок №22. Сортировка одномерного массива.
Сортировка — это расстановка элементов массива в заданном порядке.
Порядок сортировки может быть любым, для чисел обычно рассматривают сортировку по возрастанию (или убыванию) значений.
Возникает естественный вопрос: зачем сортировать данные? На него легко ответить, вспомнив, например, работу со словарями: сортировка слов по алфавиту облегчает поиск нужной информации.
Программисты изобрели множество способов сортировки. В целом их можно разделить на две группы: 1) простые, но медленно работающие (на больших массивах) и 2) сложные, но быстрые. Мы изучим два классических метода из первой группы и один метод из второй — знаменитую «быструю сортировку», предложенную Ч. Хоаром.
Далее мы будем рассматривать сортировку массива по возрастанию (или убыванию) значений. Для массивов, в которых есть одинаковые элементы, используются понятия «сортировка по неубыванию» и «сортировка по возрастанию». Сортировка по убыванию выполняется аналогично.
Название этого метода произошло от известного физического явления — пузырёк воздуха в воде поднимается вверх. Если говорить о сортировке массива, сначала поднимается «наверх» (к началу массива) самый «лёгкий» элемент (элемент с минимальными значениями), затем следующий и т. д.
Сначала сравниваем последний элемент с предпоследним. Если они стоят неправильно (меньший элемент «ниже»), то меняем их местами. Далее так же рассматриваем следующую пару элементов и т. д.
После обработки пары (А[1], А[2]) минимальный элемент стоит на месте А[1]. Это значит, что на следующих этапах его можно не рассматривать. Первый цикл, устанавливающий на свое место первый (минимальный) элемент, можно на псевдокоде записать так:
нц для j от N-1 до 1 шаг -1
если A[j+l]<A[j] то
поменять местами A[j] и A[j+1]
все
кц
Здесь j — целочисленная переменная. Обратите внимание, что на очередном шаге сравниваются элементы А[j] и А[j+1], поэтому цикл начинается с j = N — 1. Если начать с j = N, то на первом же шаге получаем выход за границы массива — обращение к элементу А[N+1].
За один проход такой цикл ставит на место один элемент. Чтобы «подтянуть» второй элемент, нужно написать ещё один почти такой же цикл, который будет отличаться только конечным значением j в заголовке цикла. Так как верхний элемент уже стоит на месте, его не нужно трогать:
нц для j от N-1 до 2 шаг -1
если A[j+l]<A[j] то
поменять местами А[j] и A[j+1]
все
кц
При установке 3-го элемента конечное значение для j будет 3 и т. д. Таких циклов нужно сделать N — 1: на 1 меньше, чем количество элементов массива. Почему не N? Дело в том, что если N — 1 элементов поставлены на свои места, то оставшийся автоматически встает на своё место — другого места нет. Поэтому полный алгоритм сортировки представляет собой такой вложенный цикл:
нц для i от 1 до N-1
нц для j от N-1 до i шаг -1
если A[j+l]<A[j] то
поменять местами A[j] и А[j +1]
все
кц
кц
Записать полную программу на выбранном языке вы можете самостоятельно.
Ещё один популярный простой метод сортировки — метод выбора, при котором на каждом этапе выбирается минимальный элемент (из оставшихся) и ставится на свое место. Алгоритм в общем виде можно записать так:
нц для i от 1 до N-1
найти номер nMin минимального элемента из A[i]..A[N]
если i<>Min то
поменять местами A[i] и A[nMin]
все
кц
Здесь перестановка происходит только тогда, когда найденный минимальный элемент стоит не на своём месте, т. е. ionMin. Поскольку поиск минимального элемента выполняется в цикле, этот алгоритм сортировки также представляет собой вложенный цикл:
нц для i от 1 до N-1
nMin:= i
нц для j от i+1 до N
если A[j]<A[nMin] то
nMin:=j
все
кц
если i<>nMin то
поменять местами A[i] и A[nMin]
все
кц