При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
- количество присваиваний;
- количество сравнений.
Все методы сортировки можно разделить на две большие группы:
- прямые методы сортировки;
- улучшенные методы сортировки.
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:
1) сортировка вставкой (включением);
2) сортировка выбором (выделением);
3) сортировка обменом (так называемая "пузырьковая" сортировка).
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса
Рассмотрим сортировку методом вставки.
Принцип метода заключается в следующем:
Массив разделяется на две части: отсортированную и не отсортированную. элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной – все остальные элементы.
Таким образом, алгоритм будет состоять из (n-1)-го прохода (n – размерность массива), каждый из которых будет включать четыре действия:
• взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;
• поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
• сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;
• вставка взятого элемента в найденную i-ю позицию.
Для реализации данного метода можно предложить несколько алгоритмов, которые будут отличаться способом поиска позиции вставки.
Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:
Procedure Vstavka(Var a: Array1);
Var
i, j,e,g:integer;
Begin
for i:=2 to c do
begin
e:=A[i];
j:=1;
while (e>a[j]) do
Inc(j);
for g:=i-1 downto j do
a[g+1]:=a[g];
a[j]:=e;
end;
End;
Задание. Составьте программу сортировки одномерного массива рассмотренным методом.