Сортировка представляет собой процесс упорядочения элементов в массиве в
порядке возрастания или убывания их значений. Например, массив А из n
элементов будет отсортирован в порядке возрастания значений его элементов,
если
, и в порядке убывания, если
.
Существует большое количество алгоритмов сортировки, но все они базируются на трех основных:
- сортировка обменом;
- сортировка выбором;
- сортировка вставкой;
Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается:
- количество сравнений;
- количество обменов, произведённых в процессе работы.
Элементы массива можно сортировать:
- по возрастанию – каждый следующий элемент больше предыдущего A[1]<A[2]<…<A[n];
- по неубыванию - каждый следующий элемент не меньше предыдущего A[1] ≤A[2] ≤ … ≤ A[N];
- по убыванию - каждый следующий элемент меньше предыдущего A[1]>A[2]>…>A[N];
- по невозрастанию - каждый следующий элемент не больше предыдущего A[1]≥A[2] ≥ … ≥ A[N]
Сортировка обменом (метод «пузырька»)
· Последовательно сравниваются пары соседних элементов x[k] и x[k+1] (k = 1,2, ... , n-1) и, если их взаиморасположение не удовлетворяет заданному условию, то они переставляются (меняются местами).
Сортировка выбором
· Отыскивается максимальный (минимальный) элемент и переносится в конец массива. Затем этот метод применяется ко всем элементам, кроме последнего (он уже находится на своем месте) и т.д.
· Другой вариант метода - перенос найденного элемента в начало массива и последующее применение метода ко всем элементам, кроме первого и т.д.
Сортировка вставками
· Массив разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть таким образом, что не нарушают упорядоченность элементов. В начале, в качестве отсортированной части принимают только один первый элемент.
Итак, решим следующую задачу. Задан массив А из n целых чисел. Расположить элементы массива в порядке возрастания их значений.
Сортировка методом «пузырька»
Это один из простейших методов сортировки. В алгоритме выполняются последовательные перемещения соседних элементов. Последовательно просматриваются все пары рядом стоящих элементов массива и, если они расположены в неправильном порядке, они меняются местами. Отсортированные элементы не нуждаются в сравнении при последующих перемещениях, поэтому второй проход перемещений выполняется до предпоследнего элемента и т. д. Всего для массива размерности n требуется (n-1) проход. Это правило действует до тех пор, пока все пары не будут стоять в правильном порядке (то есть, по возрастанию или убыванию).
Алгоритм: последовательно сравниваем каждую пару соседних чисел и, в зависимости от результата сравнения, переставляем элементы или оставляем на месте. Алгоритм реализуется с помощью двух вложенных циклов.
Сортировка элементов массива в порядке возрастания значений:
for i:=1 to n-1 do begin for j:=1 to n-i do if A[j] <= A[j+1] then begin P:= A[j]; A[j]:= A[j+1]; A[j+1]:= P; end; end;
или
for i:=1 to n-1 do for j:=n downto i+1 do if a[j-1]>a[j] then begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; end; end.
Сортировка выбором
Находится минимальный элемент массива и записывается в первую ячейку массива, содержимое которой записывается на место найденного минимального элемента. После чего находится минимальный элемент массива, начиная со второго элемента, он записывается во вторую ячейку массива, содержимое которой записывается на место найденного минимального элемента. Таким образом, постепенно выстраивается упорядоченный массив.
for i:=1 to n-1 do begin k:=i; x:=a[i]; for j:=i+1 to n do begin if a[j]< x then begin k:=j; x:=a[k]; end; end; a[k]:=a[i]; a[i]:=x; end;
Сортировка вставками
Сортировка вставками - примитивный алгоритм сортировки с высокой вычислительной сложностью.
Плюсы:
- эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
- эффективен на наборах данных, которые уже частично отсортированы;
- это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
- может сортировать список по мере его получения;
Минусы:
- Очень высокая вычислительная сложность алгоритма.
Основным преимуществом алгоритма сортировки вставками является возможность сортировать массив по мере его получения, т. е. имея часть массива, можно начинать его сортировать.
Сортировка вставками — простой алгоритм сортировки. Хотя этот метод сортировки намного менее эффективен чем более сложные алгоритмы (такие как быстрая сортировка), у него есть ряд преимуществ:
- прост в реализации;
- эффективен на небольших наборах данных;
- эффективен на наборах данных, которые уже частично отсортированы* это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
- может сортировать список по мере его получения;
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Выбор очередного элемента, выбираемого из исходного массива, произволен; может использоваться практически любой алгоритм выбора.
for i := 2 to N do if a[i - 1] > a[i] then begin x := a[i]; j := i - 1; while (j > 0) and (a[j] > x) do begin a[j + 1] := a[j]; j := j - 1; end; a[j + 1] := x; end.
или
for i:=2 to N do begin x:=a[i]; j:=i; while (j>1) and (x< a[j-1]) do begin a[j]:=a[j-1]; j:=j-1; end; a[j]:=x; end.
Инструкция