С ортировка Выбором
О
дин
из самых простых методов сортировки
работает следующим образом: находим
наименьший элемент в массиве и обмениваем
его с элементом находящимся на первом
месте, потом повторяем процесс со второй
позиции в файле и найденный элемент
обмениваем со вторым элементом и так
далее пока весь массив не будет
отсортирован. Этот метод называется
сортировка выбором поскольку он работает
циклически выбирая наименьший из
оставшихся элементов.
Сортировка
выбором
procedure
selection;
var
i, j, min, t : integer;
begin
for i:=1 to N-1 do
begin
min := i;
for j:=i+1
to N do
if a[j]<a[min] then
min := j;
t := a[min];
a[min] :=a[i];
a[i] := t;
end;
end;
По мере продвижения указателя i слева направо через файл, элементы слева от указателя находятся уже в своей конечной позиции (и их не больше уже не будут трогать), поэтому массив становится полностью отсортированным к тому моменту, когда указатель достигает правого края.
Этот метод - один из простейших, и от работает очень хорошо для небольших файлов. Его "внутренний цикл" состоит из сравнения a[i]<a[min] (плюс код необходимый для увеличения j и проверки на то, что он не превысил N), что вряд ли можно еще упростить. Ниже мы обсудим то, сколько скорее всего раз эти инструкции будут выполняться.
Более того, несмотря на то, что этот метод очевидно является методом "грубой силы", он имеет очень важное применение: поскольку каждый элемент передвигается не более чем раз, то он очень хорош для больших записей с маленькими ключами. Это обсуждается ниже.
Сортировка Вставкой
Сортировка вставкой - это метод который почти настолько же прост, что и сортировка выбором, но гораздо более гибкий. Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отсортированными).
type Index = 0..n; var a: array[1..n] of elem; procedure Insert; var i,j: index; x: elem; begin for i:= 1 to n do begin x:= a[i]; a[0]:= x; j:= i-1; while x.key < a[j].key do begin a[j+1]:= a[j]; j:= j-1; end; a[j+1]:= x; end; end;
Также как и в сортировке выбором, в процессе сортировки элементы слева от указателя i находятся уже в сортированном порядке, но они не обязательно находятся в своей последней позиции, поскольку их еще могут передвинуть направо чтобы вставить более маленькие элементы встреченные позже.. Однако массив становится полностью сортированным когда указатель достигает правого края.
Пузырьковая Сортировка
Следующий метод - это пузырьковая сортировка. Проходить через массив, обменивая если нужно элементы; когда на каком-то шаге обменов не потребуется - сортировка окончена. Реализация этого метода дана ниже.
procedure bubble; var i, j, t : byte; begin for i :=2 to N do for j:=N down to i do if x[i-1]>x[j] then begin t:=x[j-1];x[j-1]:=x[j];x[j]:=t; end; end; end;
Чтобы поверить в то, что она на самом деле работает, может потребоваться некоторое время. Для этого заметьте, что когда во время первого прохода встречаем максимальный элемент, обмениваем его с каждым элементом справа от него пока он не окажется в крайне правой позиции. На втором проходе помещаем второй максимальный элемент в предпоследнюю позицию и так далее. Пузырьковая сортировка работает также как и сортировка выбором, хотя она и делает гораздо больше работы на то, чтобы переместить элемент в его конечную позицию.