Методы упорядочивания данных

СОДЕРЖАНИЕ: 

  1. Сортировка «методом пузырька»
  2. Сортировка вставкой
  3. Сортировка посредством выбора
  4. Быстрая сортировка (сортировка Хоара)
  5. Сортировка Шелла

 

При работе с какими-либо данными часто возникают задачи, в которых требуется упорядочить исходные данные в определенном порядке. При работе с массивами можно осуществлять перестановки элементов в требуемом порядке. Такая задача называется сортировкой массивов.

 Она  заключается  в  следующем:  задан  список  целых  чисел  (простейший  случай)      B = < B1, B2, …, Bn>. Требуется  переставить  элементы  списка  B  так,  чтобы  получить  упорядоченный список  B’ = < B’1, B’2, …, B’n>, в котором для любого 1 <= i <= n элемент Bi <= Bi+1. Другими словами —  упорядочить список по возрастанию.

Для решения данной задачи существуют различные методы. Практически каждый алгоритм сортировки можно разбить на три части:

  • сравнение, определяющее упорядоченность пары элементов;
  • перестановку, меняющую местами пару элементов;
  • собственно сам сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

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

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

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

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

Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:

  • сортировка обменом;
  • сортировка выбором;
  • сортировка вставкой.

 

Сортировка «методом пузырька»

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

B’ получается из B систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.

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

Идея метода: производится последовательное упорядочивание смежных элементов массива: B1 и B2, B2 и B3, …, Bn-1 и Bn. В итоге максимальное значение переместится в Bn. Затем ту же процедуру повторяют до Bn-1  и т.д., вплоть до цепочки из двух элементов  B1 и B2.

Пример:

B = < 20, -5, 10, 8, 7>               — исходный список;

B1 = < -5, 10, 8, 7, 20>             — первый просмотр;

B2 = < -5, 8, 7, 10, 20>             — второй просмотр;

B? = B3 = < -5, 7, 8, 10, 20>     — третий просмотр.

В последующих примерах будем считать, что сортируется одномерный массив (либо его часть от индекса m до n индекса) в порядке возрастания элементов.

Ниже приведенная процедура сортирует исходный массив методом пузырьковой сортировки, начиная с элемента с номером m и заканчивая элементом с номером n.

/*      Сортировка пузырьковым методом      */

Type Mas = Array [1 .. n] of  Real;

Procedure Bubble (Var A: Mas; m, n: Integer);

Var i: Integer; c: Real;

is: Boolean;

Begin

is := True;

While Not is Do

Begin

is := False;

For i := m+1 To n Do

If  A[i] < A[i-1] Do

Begin

c := A[i];

A[i] := A[i-1];

A[i-1] := c;

is := True;

End;

End;

End.

Пузырьковая сортировка выполняется при количестве действий Q=(n-m)*(n-m) и не требует дополнительной памяти.

Сортировка вставкой

Требуется упорядочить массив B, состоящий из N элементов. Пусть B1, B2, …, Bi-1 уже отсортированная часть массива B, а  Bi, Bi+1, …, Bn не отсортированная. Идея метода:

  • выбираем очередной элемент Bi (начинаем с i=1);
  • в упорядоченной части массива находим k-ое место, такое чтобы при вставке на это место элемента Bi порядок не нарушился;
  • все элементы начиная с Bk–го до Bi-1 сдвигаем на одну позицию вправо и вставляем элемент Bi на k-ое место;
  • повторяем пункты 1-3 до тех пор пока i < N.

Например, для начального списка B = < 20, -5, 10, 8, 7> имеем: 

123

При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.

Сортировка посредством выбора

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

123

При сортировке посредством выбора требуется Q=(n-m)*(n-m) действий и не требуется дополнительной памяти.

Пример программы с процедурами сортировки простого выбора (SortVybor) и простой вставки (SortVstav):

Uses Crt;
Const n=10;
Type
Mas = Array [1 .. n] Of Integer;
Var A: Mas;

Procedure SetRandomMas ( Var A: Mas ); {Задание случайного массива}
Var i: Integer;
Begin
Randomize;
For i := 1 To n Do A[i] := Random (100);
End;

 

Procedure OutPutMas ( Var A: Mas ); {Вывод массива на экран}
Var i: Integer;
Begin

For i := 1 To n Do Write( A[i]:3 );

WriteLn;
End;

 

Procedure SortVybor ( Var A: Mas ); {Сортировка выбором}
Var i, k, m, j,Temp, Min: Integer;
Begin
For i := 1 To n Do

Begin
Min := A[i];
k := i;
For j := i+1 To n Do 
If A[j] < Min Then Begin Min := A[j]; k := j; End;
Temp := Min;
For m := k-1 DownTo i Do A[m+1] := A[m];
A[i] := Temp;
End;
End;
Procedure SortVstav ( Var A: Mas ); {Сортировка вставкой}
Var i, k, j, Temp: Integer;
Begin
For i := 1 To n-1 Do 
Begin
If A[i+1] < A[i] Then
Begin
j := i;
While (A[j] > A[i+1]) And (j >0) Do j := j – 1;
k := j + 1;
Temp := A[i+1];
For j := i  DownTo k Do A[j+1] := A[j];
A[k] := Temp;
End;
End;
End;
Begin

ClrScr;
SetRandomMas(A);

OutPutMas(A);
SortVstav(A);
OutPutMas(A)
End.

 

Быстрая сортировка (сортировка Хоара)

Этот метод, называемый также быстрой сортировкой (QuickSort), был разработан в 1962г. Э. Хоаром. Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его. Эту идею можно реализовать многими способами.

Рассмотрим этот метод подробнее.  Быстрая сортировка состоит в том,  что  список  B=<K1, K2, …, Kn>  реорганизуется в список 1232 <K1>, 1232 , где 1232— подсписок B с элементами не большими K1, а 1232   — подсписок B с элементами большими  K1. В списке 1232 <K1>, 1232 элемент  <K1> расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам 1232 и 1232 снова применяется упорядочивание быстрой сортировкой.

Пример:

123

Время работы по сортировке списка методом быстрой сортировки зависит от упорядоченности списка. Оно будет минимальным, если на каждом шаге разбиения получаются подписки B’  и  приблизительно равной длины, и тогда требуется около N*log2(N) шагов. Если список близок к упорядоченному, то требуется около (N*N)/2 шагов. Быстрая сортировка требует дополнительной памяти порядка log2(N).

Пример программы, использующий сортировку Хоара:

Procedure Sort( Var Mas: TMas; L, R: Integer ); {Сортировка Хоара}

Var

 i, j: Integer;Const n=10; Type TMas=Array[1..n] Of Integer;
w, x: Integer;

Begin

i := L;

j := R;

x := i + (j - 1) div 2;

Repeat

While (Mas[i] < Mas[x]) Do Inc(i);
While (Mas[j] > Mas[x]) Do Dec(j);

If (i <= j) Then

Begin

w := Mas[i];
Mas[i] := Mas[j];

Mas[j] := w;

Inc(i);

Dec(j);

End;

Until (i > j);
If (L < j) Then Sort(Mas, L, j);

If (i < R) Then Sort(Mas, i, R);

End;

Var A: Tmas; i: Integer;

Begin

Randomize;

For i := 1 To n Do A[i] := Random (100);

For i := 1 To n Do Write( A[i]:3 );

WriteLn;

Sort (Massiv, 1, N);

For i := 1 To n Do Write( A[i]:3 );

WriteLn

End.

Сортировка Шелла

Алгоритм предложен в 1959 году как усовершенствование метода простых вставок. Является самым простым среди улучшенных алгоритмов сортировки. Может работать и как улучшенный метод простого обмена (метод «пузырька»).

123
Идея метода
состоит в следующем: сначала переставлять элементы на большие расстояния, а затем расстояния сужать. Расстояние между сравниваемыми элементами задается с помощью вспомогательной величины h – шага перестановки элементов. На каждом этапе рассматриваются ai и ai+h.В «пузырьке» сравниваем соседние элементы. Но если в массиве элементы стоят далеко от своего истинного места, то придется совершить очень много перестановок.

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

При уменьшении шага h количество цепочек уменьшается, а длина их возрастает. На самом последнем этапе h=1 (обязательно!), и весь массив представляет собой цепочку. «Пузырек» — частный случай алгоритма Шелла при h=1. Пример сортировки методом Шелла:

123

Таким образом, мы видим, что внешне процесс существенно усложняется: вместо одной сортировки необходимо несколько (при каждом h — несколько цепочек и для каждой нужно провести  сортировку). В чем же преимущество?

Дело в том, что на каждом шаге либо сортируется относительно мало элементов (на первых этапах), либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок (на последующих  этапах). Это важно, т.к. перестановки (присваивания) – более медленные операции, чем сравнения. В конце концов, массив окажется упорядоченным, т.к. последнее значение шага h=1 и весь массив окончательно упорядочивается как одна цепочка.

Теперь запишем весь алгоритм.

Const n= …;

Type

Mas = Array[1..n] of Real;

Procedure SHELL( n: Integer; Var A: Mas );

Var

H, I: Integer;

Begin

H := (n+2) div 3;

While H>0 Do

Begin

For I:=1 To H Do

Begin

{Упорядочение алгоритма с шагом H, начиная с i-го элемента}

End;

If H>5 Then H:=(H-1) div 2  

Else If H=1 Then H:=0

else H:=1

End

End;

Важно знать!!!

H:=(H-1) div 2  -  работает не для всех H. Можем перескочить через 1. 
H=2, H-1=1, (H-1 div 2=0)

 

На практике алгоритм Шелла целесообразнее применять, если n<=(1-5)·103 элементов. Теоретически показано, что трудоемкость оптимального алгоритма сортировки должна быть         ~nlog2n.

Для небольших n нецелесообразно применять сложные алгоритмы. Но при больших n улучшенные алгоритмы имеют преимущества.

 

Контрольные вопросы

  1. В чем заключается задача сортировки массивов?
  2. На какие части можно разбить любой алгоритм сортировки?
  3. В чем заключается идея сортировки методом «пузырька»?
  4. Объясните суть метода сортировки вставкой.
  5. Объясните суть метода сортировки посредством выбора.
  6. В чем заключается идея сортировки методом Хоара?
  7. В чем заключается сущность метода Шелла?