Линейная сортировка (сортировка отбором)

Сортировка массива.

Лекция 22.

Тема: «Сортировка массива».

Сортировка – один из наиболее распространенных процессов современной обработки данных. Сортировкой называется распределение элементов множества по группам в соответствии с определенными правилами. Например, сортировка элементов массива, в результате которой получается массив, каждый элемент которого, начиная со второго, не больше стоящего от него слева, называется сортировкой по не возрастанию.

Рассмотрим следующую задачу:

Составить программу, которая выводит несортированный массив целых чисел на экран, затем выполняет его сортировку по не возрастанию и выводит отсортированный массив на экран.

Рассмотрим три метода сортировки одного и того же массива М из 20-ти целых чисел. Использование одного массива позволит объективно сравнить эффективность разных методов.

В связи с этим описание массива во всех примерах выполним следующим образом:

Const

Count=20;

M: array [1.. Count] of

Byte=(9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);

Для сравнения эффективности разных способов сортировки введем целую переменную А, значение которой будет равно числу итераций (повтор просмотра массива). Для наблюдения текущего состояния массива после каждой перестановки элементов будем выводить его на экран:

for L:=1 to Count do Write (‘’,M[L]); Writeln(′Число итераций′,А);

Идея линейной сортировки по не возрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольшее число и поместить его на первую позицию, обменяв его с элементом, который ранее занимал первую позицию. Затем просматриваются все остальные элементы массива и выполняется аналогичная операция по отбору из рассматриваемой части массива максимального элемента и обмену местами этого элемента и первого в рассматриваемой части и т.д.

Введем в разделе описание следующие целые переменные:

I-для указания позиции первого элемента в рассматриваемой части массива;

J-для указания позиции очередного сравниваемого с ним элемента;

N-для временного хранения значения первого элемента для обмена значениями с максимальным из рассматриваемой части массива;

L-параметр цикла при выводе текущего значения элементов массива в процессе сортировки для наблюдения происходящих в массиве наблюдений;

A-переменная, значение которой будет равно числу перестановок элементов.

Вначале запишем вывод исходного массива на экран:

Writeln (′Исходный массив:′);

for I:=1 to Count do Write (‘’,M[I]);

Writeln;

Переход началом сортировки установим значение счетчика итераций А, равно 0. для сортировки организуем два цикла for. Внешний цикл с параметром I, указывающим позицию первого элемента в не отсортированной части массива, и внутренний цикл с параметром J, указывающим позицию очередного, сравниваемого с первым, элемента не отсортированной части массива. Сравнение элементов запишем оператором:

if M[I]<M[J] then

begin

N:= M[I];

M[I]:= M[J];

M[J]:=N;

end;

Если условие M[I]<M[J] выполняется, т.е. в не отсортированной части массива найден элемент, больший, чем первый, то обменять местами эти элементы. Обмен осуществляется следующим образом: сначала значение M[i] запоминается в переменой N, затем значение элемента массива из J-й позиции записывается в 1-го позицию, а после этого в J-ю позицию массива записывается значение переменной N. Для наблюдения изменений состояния массива после каждой перестановки зададим цикл вывода значений всех элементов массива и напечатаем текущее значение числа перестановок элементов А следующим образом:

for L:=1 to Count do Write (‘’,M[L]); Writeln(′Число итераций=′,А);

Полный текст программы линейной сортировки массива М по невозрастанию может быть записан так:

Program Sort Lin; {Линейная сортировка по невозрастанию}

const

Count=20;

M: array [1.. Count] of byte=(9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5);

var

I, J, N, L: Byte;

A:integer;

begin

Writeln(′Исходный массив:′);

for I:=1 to Count do

Write (‘’, M [L]); Writeln

A:=0;

for I:=1 to Count-1do{Изменять размер неотсортированной части массива}

for J:=I+1 to Count do {Сравниваем поочередной 1-й элемент неотсортированной части массива со всеми отI+1-го до конца}

begin

A:=A+1;

if M[I]<M[J] than {Если в неотсортированной части массива нашли элемент/больший, чем 1-й, то обменять их местами}

begin

N: = M [I]; {Запомнить на время значение M [I]}

M [I]: = M [J];

M [J]: = N;

end;

for L:=1 to Count do

Write (‘’, M [L]); Writeln (′Число итераций=′,А);

end;

end.

Дата добавления: 2014-01-06