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:

user image

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.