Сортировки. Алгоритмы сортировок

Презентация содержит 26 слайдов.

Сортировка — одна из наиболее активно изучаемых тем в компьютерных алгоритмах.

Сортировка — это задача, которая часто встречается во многих приложениях. Многие сортировки являются интересными примерами программирования.

Пузырьковая сортировка

Она основана на выполнении в цикле операций сравнения и  при необходимости обмена соседних элементов.  Ее название происходит из-за подобия процессу движения пузырьков в резервуаре  с водой, когда каждый пузырек находит свой собственный уровень.

Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место вместо того, чтобы вставлять его в произвольное место, а затем заново сортировать весь список.

Сортировка слиянием

АЛГОРИТМ СОРТИРОВКИ

MergeSort(list.first,last)

list    сортируемый список элементов

first номер первого элемента в сортируемой части списка

last    номер последнего элемента в сортируемой части списка

if first

middle=(first+last)/2

MergeSort(list,first.middle)

MergeSort(list,middle+l,last)

MergeLists(list.first.middle,middle+l,last)

end if

Быстрая сортировка.

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

• Сортировка — одна из наиболее активно изучаемых тем в компьютерных алгоритмах.

Сортировка — это задача, которая часто встречается во многих приложениях. Многие сортировки являются интересными примерами программирования.

• Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень.

2 1 8 7 6 5

2 1 8 7 6 5

1 2 8 7 6 5

1 2 8 7 6 5

1 2 7 8 6 5

1 2 8 7 6 5

1 2 7 8 6 5

1 2 7 6 8 5

1 2 7 6 5 8 / сортируем без последнего

1 2 7 6 8 5

1 2 7 6 5 8

1 2 7 6 5 8

1 2 7 6 5 8

1 2 7 6 5 8

1 2 6 7 5 8

a(J), то значения меняются местами. Алгоритм останавливается, когда больше нечего переставлять; в этом случае массив отсортирован. " width="640"

• Сравнивают пары значений a(I) и a(J) при I в интервале от 1 до N-1 и J изменяющемся в интервале от I+1 до N: если a(I)a(J), то значения меняются местами. Алгоритм останавливается, когда больше нечего переставлять; в этом случае массив отсортирован.

a[j] then swap(a[i],a[j]); (меняем местами 2 числа) end ; 3 2 5 N=3 // число эл-ов i:=1,2. j:=2,3 // индексы эл-ов а [1]a[2] Swap(a[1],a[2]) " width="640"

procedure swap (var k,l:integer);// объявление процедуры

var m:integer;

Begin

m:=k;k:=l;l:=m; (инструкции процедуры)

end;

procedure sort;

begin

for i:=1 to n-1 do

for j:=i+1 to n do

if a[i]a[j] then swap(a[i],a[j]); (меняем местами 2 числа)

end ;

3 2 5

N=3 // число эл-ов

i:=1,2. j:=2,3 // индексы эл-ов

а [1]a[2]

Swap(a[1],a[2])

a[i+1] then swap(a[i],a[i+1]); until f =1; // массив сортируется заново, пока f не равно 1 . end ; " width="640"

procedure swap(var k,l:integer); // объявление процедуры обмена 2-х чисел

var m:integer;

begin

m:=k;k:=l;l:=m; f:=0;

end;

procedure sort;

begin

repeat

f:=1;

for i:=1 to n-1 do

if a[i]a[i+1] then swap(a[i],a[i+1]);

until f =1; // массив сортируется заново, пока f не равно 1 .

end ;

• Число операций обмена будет нулевым для наилучшего случая , когда исходный массив уже является отсортированным.
• Число операций обмена для среднего случая будет равно 3/4 (n**2-n).
• Для наихудшего случая будет равно 3/2 (n**2-n) раз.

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

Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место вместо того, чтобы вставлять его в произвольное место, а затем заново сортировать весь список.

• 1 4 5 8 10 –отсортированный массив

• 4 5 8 10

1 4 7 5 8 10

1 4 5 7 8 10 / список по возрастанию

если А [2]

7

1 7 4 5 8 10

procedure sort;

begin

for j:=2 to n do // объявляем индексы правой части

begin

x:=a[j];i:=j-1;

while not((i

begin

a[i+1]:=a[i]; // переставляем элементы

i:=i-1;

end ;

a [ i +1]:= x ;

end ;

• 5 2 3 4 7 9 /разбиваем на 2 списка
• 5 2 3 и 4 7 9 / переставляем элементы в списках 2 5 3 и 4 7 9
• 2 3 5 и 4 7 9 / объединяем списки

• 3 5 2 3 4 5 7 9

4 7 9

• АЛГОРИТМ СОРТИРОВКИ
• MergeSort ( list . first , last )
• list сортируемый список элементов
• first номер первого элемента в сортируемой части списка
• last номер последнего элемента в сортируемой части списка

if first

middle=(first+last)/2

MergeSort(list,first.middle)

MergeSort(list,middle+l,last)

MergeLists(list.first.middle,middle+l,last)

end if

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

• В среднем такая сортировка эффективна, однако в наихудшем случае ее эффективность такая же, как у сортировки вставками и пузырьковой.

• 5 4 2 1 3 7 9

Выбираем осевой элемент

• 4 2 1 3 7 9 1 2 4 5 3 7 9

1 2 4 5 3 7 9 1 2 3 4 5 7 9

j; if l if l end; begin qs(1, count, item); end; { конец быстрой сортировки } " width="640"

procedure QuickSort(var item: DataArray; count:integer);

procedure qs(l, r: integer; var it: DataArray);

var

i, j: integer;

x, y: DataItem;

begin

i:=l; j:=r;

x:=it[(l+r) div 2];

repeat

while it[i]

while x

if y

begin

y := it[i];

it[i] := it[j];

it[j] := y;

i := i+1; j := j-1;

end;

until ij;

if l

if l

end;

begin

qs(1, count, item);

end; { конец быстрой сортировки }

Быстрая сортировка реализует

N log2 N операций сравнения и зачастую еще меньшее число операций присваивания, хотя теоретическая оценка для худшего случая является квадратичной по N .

При первом проходе ищется минимальное значение массива а, которое затем меняется местами с первым элементом а(1), затем поиск продолжается на оставшихся N -1 элементах, ищется второй минимум, который переставляется с элементом а(2) и т.д.

a[j] then begin min:=a[j];nom:=j; end; swap(a[i],a[nom]); end ; end ; " width="640"

procedure sort;

begin

for i:=1 to n-1 do

begin

min:=a[i];nom:=i;

for j:=i+1 to n do

if mina[j] then begin min:=a[j];nom:=j; end;

swap(a[i],a[nom]);

end ;

end ;