Быстрая сортировка ( Quick Sort ) массива Deplhi, Pascal.

Итак, сегодня мы разберем быструю сортировку массива и рассмотрим код. Эту тему я выложил в разделе статьи о Delphi, так как сам я предпочитаю Delphi Паскалю. Код практически идентичный, но в Delphi массив и его размерность мы передаем глобально. Итак, начнем.

Все вы наверное знаете сортировку пузырьком или какие-нибудь еще квадратичные сортировки. Такие сортировки выгодны, когда размерность массива мала, так как они работают за N^2 операций. Согласитесь, что для массива размерностью, например, в 100000 элементов такая сортировка не подходит, так как будет выполняться примерно 10000000000 операций.

Специально для таких ситуаций придумана быстрая сортировка(Quick Sort). Она работает за N log N. Что НАМНОГО быстрее квадратичной сортировки. Какова идея Qsort?

Qsort разбивает наш массив на участки, которые отделяются переменными l и r. Когда мы определили новый участок для обработки(изначально l = 1, r = N), мы выбираем рандомный элемент(X). Теперь просто нужно сделать так, чтобы все элементы массива до X были меньше X, а все элементы после X должны быть больше X. После этого мы выбираем новый участок для обработки.

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

Код:


Procedure QSort(l, r: integer);
Var i, j, x: integer;
begin
  i := l;
  j := r;
  x := a[l + random(r - l)];
  While i < j do
  begin
    While a[i] < x do inc(i);
    While a[j] > x do dec(j);
    if i <= j then
    begin
      swap(a[i], a[j]);
      inc(i); dec(j);
    end;
  end;
  if i < r then QSort(i, r);
  if l < j then QSort(l, j);
end;



Примечание: Процедуру Swap нужно писать отдельно перед Quick Sort.