Блог инженера-программиста / шапку скоро поменяю /

QuickSort на pascal и delphi

Часто нужно выполнить быструю сортировку массива, а по памяти пишется только классический пузырек? Тогда эта заметка может понадобиться. Рабочая реализация быстрой сортировки (QuickSort) на Pascal или Delphi (синтаксис полностью совпадает).

Процедура qSort сортирует массив v:array[?..?] of real;. Если нужно сортировать массив другого типа, нужно сменить тип у w,q:real; — он должен совпадать с типом элементов массива.

Сортировка происходит от элемента с номером l до элемента с номером r. Если нужно сортировать весь массив с количеством элементов n, нужно пользоваться таким вызовом функции: qSort(1,n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
procedure qSort(l,r:longint);
var i,j:longint;
    w,q:real;
begin
  i := l; j := r;
  q := v[(l+r) div 2];
  repeat
    while (v[i] < q) do inc(i);
    while (q < v[j]) do dec(j);
    if (i <= j) then
    begin
      w:=v[i]; v[i]:=v[j]; v[j]:=w;
      inc(i); dec(j);
    end;
  until (i > j);
  if (l < j) then qSort(l,j);
  if (i < r) then qSort(i,r);
end;

Комментарии на: "QuickSort на pascal и delphi" (5)

  1. Спасибо !

    • Инженер said:

      Не за что :) Сам когда-то искал нормальную реализацию qSort на паскале и не находил.

  2. вовочка said:

    а не проще для q брать рандомный элемент?
    если брать строго середину, то такой алгоритм можно и в квадрат положить

    • Инженер said:

      Не проще, но правильней. Есть даже специальные «сложные» тесты, которые приводят QuickSort к O(n2). Но для большинства случаев такого варианта хватает. Очень часто алгоритм нужен студентам — усложнять его еще random-ом я бы не стал.

  3. Автору, огромное спасибо!!!!!!!!!!!! Сам долго парился, всегда чего-то нехватало