Классификация методов сортировки Сортировка вставкой и сортировка выбором

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

Методы сортировки прямые методы сортировки; улучшенные методы сортировки.

Прямые методы сортировки сортировка вставкой (включением); сортировка выбором (выделением); сортировка обменом (так называемая "пузырьковая" сортировка).

Сортировка вставкой Массив разделяется на две части: отсортированную и не отсортированную. Элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной - все остальные элементы.

Алгоритм сортировки вставкой (состоит из n-1 прохода) i взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной; j поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов; ij-1 сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки; i вставка взятого элемента в найденную 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;

Сортировка выбором Принцип метода: Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

Алгоритм работы (пример)

Алгоритм работы (продолжение)

Процедура, реализующая данный алгоритм Procedure Vibor(Var a: MyArray); Var i, j, Min, MinI : integer; Begin for i:=1 to n-1 do begin Min:=a[i]; MinI:=i; for j:=i+1 to n do if a[j]<Min then begin Min:=a[j]; MinI:=j; end; a[MinI]:=a[i]; a[i]:=Min; end; End;

Решение задач В массиве X(N) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все единицы, затем все двойки и, наконец, все нули (дополнительного массива не заводить). Составьте алгоритм, упорядочивающий элементы массива, стоящие на нечетных местах, в возрастающем порядке, а на четных - в убывающем. Из двух упорядоченных по возрастанию одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный по убыванию.