Rambler's Top100
 

Билет 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 }

 

Вверх

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ Faststart - рейтинг сайтов, каталог интернет ресурсов, счетчик посещаемос­ти Яндекс.Метрика
Hosted by uCoz