witam
algorytm quicksort wbrew pozorom można zrealizować na różne sposoby i ma to wpływ na wydajność. przetestowałem kilka i okazuje się że każdy sposób prowadzi do wykonywania wielu zbędnych zamian elementów tablicy o tej samej wartości. próbowałem z tym walczyć ale jak wyeliminowałem te niepotrzebne zmiany to odbywało się to kosztem wydajności. na przykład taki:
procedure gsort (var t: array of longint; l, r : longint);
var pivot, g, i, j, p1, p2 : longint;
begin
pivot := (t[((r - l) shr 2) + l + 1] + t[r - ((r - l) shr 2)]) shr 1;
p1 := ((r - l) shr 2) + l + 1;
p2 := r - ((r - l) shr 2);
pokaz(p1,p2,l,r, pivot,1);
i := l; j := r;
repeat
while pivot > t[i] do inc(i);
while pivot < t[j] do dec(j);
if i <= j then
begin
g := t[i]; t[i] := t[j]; t[j] := g;
pokaz(i,j,l,r, pivot, 0);
inc(i); dec(j);
end;
until i > j;
if (l < j) then gsort(t, l, j);
if (i < r) then gsort(t, i, r);
end;
zachowuje się tak:
czerwony wiersz to wywołanie procedury w odpowiadającym jej zakresie, zielony każda zamiana, żółty zamieniane elementy, jasnoczerwony z boku pivot
czy jest jakiś logiczny i podwyższający wydajność albo chociaż ją zachowujący sposób na wyeliminowanie tych niepotrzebnych zamian.