См. http://www.vzmakh.ru/info/pascal/modules/page14.html#swp
Лекция 7: Методы сортировки массивов
Сортировка массива
Поиск заданного элемента массива
Под поиском заданного элемента массива понимается необходимость определить, содержит ли массив определенную информацию или нет. Наиболее простой алгоритм поиска – простой перебор неупорядоченных элементов.
Поиск осуществляется последовательным сравнением элементов массива с образцом до тех пор, пока не будет найден элемент, равный образцу, или пока не будут проверены все элементы.
Для поиска элементов удобно использовать операторы цикла For, Repeat..until или While..do.
Задача2. Найти заданный элемент в массиве и вывести его на экран дисплея.
признак
отсутствия
признак
обнаружения
Новые стандартные процедуры:
Процедура Break позволяет досрочно завершить цикл, не дожидаясь его окончания.
Процедура Continue позволяет начать новую итерацию цикла, даже если предыдущая не завершена.
Под сортировкой массива подразумевается процесс перестановки элементов массива, с целью размещения элементов массива в определенном порядке.
Например, для целых чисел А после сортировки по возрастанию должно выполняться условие:
A[1] £ A[2] £ A[3] £ . . . £ A[size], где size – верхний индекс
Алгоритм сортировки:
1. Просмотреть массив от 1 элемента, найти min элемент и поместить его на место 1 элемента, а 1-й на место min.
2. Просмотреть массив от 2 элемента, найти min элемент и поместить его на место 2 элемента, а 2-й на место min
3. И так далее до последнего элемента.
Элементы массива А
A[ 1 ]= 2
A[ 2 ]= 6
A[ 3 ]= -5
A[ 4 ]= 3
A[ 5 ]= 20
A[ 6 ]= -10
A[ 7 ]= 8
A[ 8 ]= 0
A[ 9 ]= 9
A[ 10 ]= -2
Сортировка массива
-10 6 -5 3 20 2 8 0 9 -2
-10 -5 6 3 20 2 8 0 9 -2
-10 -5 -2 3 20 2 8 0 9 6
-10 -5 -2 0 20 2 8 3 9 6
-10 -5 -2 0 2 20 8 3 9 6
-10 -5 -2 0 2 3 8 20 9 6
-10 -5 -2 0 2 3 6 20 9 8
-10 -5 -2 0 2 3 6 8 9 20
-10 -5 -2 0 2 3 6 8 9 20
Отсортированный массив
-10 -5 -2 0 2 3 6 8 9 20
Задача3. Отсортировать массив целых чисел по возрастанию.
От порядка расположения данных в памяти ЭВМ, во многом зависит скорость и простота выполнения алгоритмов, предназначенных для обработки этих данных. Поэтому в программировании часто возникает задача перегруппировки данных в невозрастающем или неубывающем, порядке. Такая задача называется упорядочением или сортировкой элементов данной структуры.
Под сортировкой понимают, процесс перестановки объектов множества в определенном порядке, (обычно в алфавитном или числовом).
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.
При сортировке массивов будем предполагать, что перестановки, переводящие элементы массива в нужный порядок, должны выполняться на том же месте, т.е. без использования промежуточного массива. Методы, в которых элементы из массива A передаются в результирующий массив В, представляют значительно меньший интерес.
Все методы сортировки можно разделить на две большие группы:
прямые методы сортировки;
быстрые или улучшенные методы сортировки.
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:
сортировка вставкой (включением);
сортировка выбором (выделением);
сортировка обменом (так называемая "пузырьковая" сортировка).
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса.
Вообще говоря, это большая и сложная тема, в которой известно много различных алгоритмов. Критерии оценки эффективности этих алгоритмов могут включать следующие параметры:
количество шагов алгоритма, необходимых для упорядочения;
количество сравнений элементов;
количество перестановок, выполняемых при сортировке.
Для прямых методов сортировки требуется порядка n^2 сравнений ключей, они более просты и удобны для объяснения характерных черт основных принципов большинства сортировок. Программы этих методов легко понимать и они короче программ быстрых алгоритмов.
Улучшенные методы сортировки требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших значениях n их использовать не следует.
Мы рассмотрим только три простейшие схемы сортировки.
Но прежде чем перейти к рассмотрению конкретного алгоритма той или иной сортировки немного вспомним материал, который пригодится нам в дальнейшем.
Задача. Даны две целочисленные переменные х и y. Составить фрагмент программы, после выполнения которого значения этих переменных распределяются в порядке убывания.
Обмен значений переменных нужно производить лишь в том случае, если х<у. Для того чтобы не потерять начальное значение переменной х, введем дополнительную переменную t.
if x<y then begin t:=x; x:=y; y:=t; end;
Задача. Составить фрагмент программы поиска максимального числа из трех введенных с клавиатуры чисел.
Пусть а, b, c - вводимые с клавиатуры числа, Max - максимальное из их значений. На первом шаге предположим , что а - максимальное из чисел и поэтому Max:=a. Затем сравним значение предполагаемого максимума со значениями переменных b и с. Если значение m окажется меньше, чем значение очередной переменной, то переопределим значение максимума.
. . . m:=a; if m<b then m:=b; if m<c then m:=c; . . .
Задача. Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.
Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива.
. . . Max:=a[1]; for i := 2 to 10 do if Max<a[i] then Max := a[i]; . . .
Метод "пузырька" (или метод обмена)
По-видимому, самым простым методом сортировки является так называемый метод "пузырька".
Принцип метода:
Слева направо поочередно сравниваются два соседних элемента, и если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент ("всплыл" первый "пузырек"). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента.
И так далее. Всего требуется (n-1) проход.
Итак, этот алгоритм в исходном списке ищет пары цифр, которые следуют не по порядку и затем меняет их местами. Процесс повторяется до тех пор пока весь список не будет отсортированным. Элемент двигается к вершине, как пузырёк воздуха к поверхности воды. Этот эффект и дал название алгоритму пузырьковой сортировке.
Чтобы уяснить его идею, представьте, что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход "снизу", берется первый элемент и поочередно сравнивается с последующими. При этом:
если встречается более "легкий" (с меньшим значением) элемент, то они меняются местами;
при встрече с более "тяжелым" элементом, последний становится "эталоном" для сравнения, и все следующие сравниваются с ним .
В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее "всплывшие" элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.
Теперь можно привести текст программы упорядочения массива M[1..N]:
begin for j:=1 to N-1 do for i:=1 to N-j do if M[i] > M[i+1] then swap(M[i],M[i+1]) end;
Стандартная процедураswapбудет использоваться и в остальных алгоритмах сортировки для перестановки элементов (их тип мы уточнять не будем) местами:
procedure swap(var x,y: ...); var t: ...; begin t := x; x := y; y := t end;
Заметим, что если массив M — глобальный, то процедура могла бы содержать только аргументы (а не результаты). Кроме того, учитывая специфику ее применения в данном алгоритме, можно свести число парметров к одному (какому?), а не двум.
Применение метода "пузырька" можно проследить здесь.
Это тоже предельно простой для понимания алгоритм. Идея в том, чтобы создать новый массив, а затем последовательно вставлять в новый массив элементы из старого массива, чтобы созданный массив был всё время упорядоченным.
Метод называется метод вставок., т.к. на j-ом этапе мы "вставляем" j-ый элемент M[j]в нужную позицию среди элементов M[1], M[2],. . ., M[j-1], которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Принцип метода заключается в следующем:
Массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной - все остальные элементы.
Чтобы сделать процесс перемещения элемента M[j], более простым, полезно воспользоваться барьером: ввести "фиктивный" элемент M[0], чье значение будет заведомо меньше значения любого из "реальных"элементов массива (как это можно сделать?). Мы обозначим это значение через -oo.
Если барьер не использовать, то перед вставкой M[j], в позицию i-1 надо проверить, не будет ли i=1. Если нет, тогда сравнить M[j]( который в этот момент будет находиться в позиции i) с элементом M[i-1].
Описанный алгоритм имеет следующий вид:
begin M[0] := -oo; for j:=2 to N do begin i := j; while M[i] < M[i-1] do begin swap(M[i],M[i-1]); i := i-1 end end end;
Новые стандартные процедуры:
A[ 6 ]= -10
-10 -5 -2 0 2 20 8 3 9 6
