Билет 26. Вопрос 1. Методы сортировки элементов массива.
Под сортировкой(упорядочением) понимают перераспределение элементов массива в некотором порядке. Цель сортировки - облегчить последующий поиск элементов в таком упорядоченном массиве. Мы встречаемся с упорядоченными объектами на складах, в телефонных справочниках, в библиотечных каталогах, в словарях - почти везде, где нужно искать хранимые объекты. Даже малышей учат держать вещи в "порядке", и они уже сталкиваюся с некоторыми видами упорядочения задолго до того, как познакомятся с азами информатики. Примером задачи сортировки может служить следующая. В массиве из N различных чисел осуществить их перестановку так, чтобы после перестановки в массиве первым элементом было самое большое число. Каждое следующее должно быть меньше предыдущего, а последнее самое маленькое из чисел массива. Такой порядок расположения чисел называется убывающим. Порядок, при котором в массиве первым является самое маленькое число, а каждое следующее число больше предыдущего, а последнее - самое большое из чисел массива, называют возрастающим. Сортировку можно осуществить несколькими способами. Каждый из них имеет свои достоинства и свои недостатки, поэтому выбирать наилучший алгоритм необходимо, исходя из конкретной постановки задачи.
1. СОРТИРОВКА ВЫБОРОМ.
Эта сортировка основана на следующих принципах:
Выбирается максимальный элемент. Он меняется местами с первым элементом А[1]. На первом месте оказывается максимальный элемент. Дальше рассматривается только неотсортированная часть массива, и этот процесс повторяется с оставшимися N-1, N-2 элементами и т.д. до тех пор, пока не останется, самый маленький элемент. Рассмотрим работу данного метода на примере массива А={0,1,9,2,4,3,6,5}.
1) 0, 1, 9, 2, 4, 3, 6, 5 2) 9, 1, 0, 2, 4, 3, 6, 5 3) 9, 6, 0, 2, 4, 3, 1, 5 4) 9, 6, 5, 2, 4, 3, 1, 0 5) 9, 6, 5, 4, 2, 3, 1, 0 6) 9, 6, 5, 4, 3, 2, 1, 0 7) 9, 6, 5, 4, 3, 2,1, 0
Алгоритм метода будет следующим:
for i:=1 to N-1 do begin K:=i; max:=A[i]; for j:=i+1 to N do if A[j] > max then begin max:=A[j]; K:=j; end; A[K]:=A[i]; A[i]:=max; end;
Число сравнений K, которое пришдось сделать для упорядочения массива вычисляется по формуле:
K=(N 2 -N)/2
2.СОРТИРОВКА ОБМЕНОМ.
Эта же задача (упорядочить элементы массива по убыванию) может быть решена другим способом.
Этот способ основан на следующих принципах:
Сравниваем первые два элемента. Если первый меньше второго, то меняем их местами. Cравниваем второй и третий, третий и четвертый, ..., предпоследний и последний, при необходимости меняя их местами. Самый маленький окажется на последнем месте. Просматривая массив сначала, уменьшая на единицу кол-во просматриваемых элементов. Массив будет отсортирован после просмотра, в котором участвует только первый и второй элементы. Если рассматривать массивы не как горизонтальные, а как вертикальные построения, то элементы можно представить как пузырьки в чане с водой, причем масса каждого пузырька соответствует значению элемента. В этом случае при каждом просмотре один пузырек как бы поднимается до уровня, соответственно его массе. Такой метод широко известен под названием ”пузырьковая сортировка”.
Рассмотрим его на примере того же массива А={0,1,9,2,4,3,6,5}
1) 1, 9, 2, 4, 3, 6, 5, 0 2) 9, 2, 4, 3, 6, 5, 1, 0 3) 9, 4, 3, 6, 5, 2, 1, 0 4) 9, 4, 6, 5, 3, 2, 1, 0 5) 9, 6, 5, 4, 3, 2, 1, 0 6) 9, 6, 5, 4, 3, 2, 1, 0 7) 9, 6, 5, 4, 3, 2, 1, 0
Алгоритм метода имеет вид :
for i:=1 to N-1 do for j:=1 to N-i do if А [j]<A[j+1] then begin x:=A[j+1]; A[j+1]:=A[j]; A[j]:=x end;
Число сравнений K, которое пришлось сделать для упорядочения массива также вычисляется по формуле:
K=(N 2 -N)/2
По определению, сортировка - программа, распологающая исходный массив чисел или строк в порядке возрастания или убывания элементов. Существует очень много алгоритмов сортировки и большинство из лучших описаны в литературе по языку Паскаль.
3. СОРТИРОВКА ВКЛЮЧЕНИЕМ.
Сортировка включением - самый простой алгоритм, реализующий ручную сортировку карт при игре в Бридж. Просматривая массив с одного конца до другого, каждый элемент массива ставится в правильную позицию по отношению к уже отсортированным элементам. Все программы данного примера сортируют исходных массив целых чисел в порядке возрастания (т.е., элемент theArray[1] будет наименьшим, а элемент theArray[ARRAYSIZE] - наибольшим), хотя при очень незначительном изменении эти же алгоритмы могут сортировать строки или создавать убывающий порядок. const ARRAYSIZE = 100; type arrayType = array[1..ARRAYSIZE] of integer; procedure InsertionSort (var theArray: arrayType ); var newValue, newPos, currentPos: integer; begin for newPos := 2 to ARRAYSIZE do begin newValue := theArray[newPos]; currentPos := newPos; while (currentPos > 1) and (theArray[currentPos-1] > newValue) do begin theArray[currentPos] := theArray[currentPos-1]; currentPos := currentPos - 1; end; theArray[currentPos] := newValue; end; end; { InsertionSort } Сортировка Шелла
Этот алгоритм разработан учёным в области компьютеров Дональдом Шеллом. По его алгоритму вначале сравниваются два наиболее удалённых элемента, затем, два более близких и так до тех пор, пока не сравнятся два соседних элемента. Текст процедуры :
procedure ShellSort(var List: ListType; ListMax: integer); label ExitLoop; var Indx, Jndx, TheVal, Incr : integer; begin Incr := 1; repeat Incr := 3 * Incr + 1; until Incr > ListMax; repeat Incr := Incr div 3; for Indx := Incr + 1 to ListMax do begin TheVal := List[Indx]; Jndx := Indx; while List[Jndx - Incr] > TheVal do begin List[Jndx] := List[Jndx - Incr]; Jndx := Jndx - Incr; if Jndx <= Incr then goto ExitLoop; end; ExitLoop: List[Jndx] := TheVal; end; until Incr = 1; end; { ShellSort } Быстрая сортировка
Это король алгоритмов сортировки. Основные особенности этого алгоритма приведены ниже:
-- Выбирается "центральный" элемент массива.
-- Массив имеет две части левую и правую: Левая часть просматривается слева, а правая - справа. Если элемент левой части больше или равен элементу правой, то они меняются местами. Процесс продолжается до тех пор, пока все левые элементы не будут меньше каждого правого элемента, а произвольно выбранный вначале "центральный" элемент массива не переместится в крайнюю правую позицию массива.
-- Если слева от выбранного "центра" более одного элемента, то процедура Quicksort делает рекурсию для левой части массива.
-- Если справа от выбранного "центра" более одного элемента, то процедура Quicksort делает рекурсию для правой части массива.
procedure Quicksort(start, finish: integer); { сортировка глобальной переменной theArray } var pivot, left, right : integer; begin { установка "центра" } left := start; right := finish; pivot := theArray[(start + finish) div 2]; { разделение } repeat while theArray[left] < pivot do left := left + 1; while pivot < theArray[right] do right := right - 1; if left <= right then begin Swap( theArray[left], theArray[right] ); left := left + 1; right := right - 1; end; until right <= left; { сортировка левой и правой частей } if start < right then QuickSort(start, right); if left < finish then QuickSort(left, finish); end; { QuickSort } |