sortowanie wskaznikow quicksort

Witam, mam problem ze wskaznikami, dokładniej z sortowaniem, wyskakuje "invalid pointer operation" jest to dziwne bo czasem działa a czasem nie i nie mam pojęcia czemu tak jest.
Błąd pojawia sie w procedurze sortuj tutaj:

while tmp <> nil do begin
      i := i + 1;
      tmp.liczba := tab[i];
      tmp := tmp.nast;
    end;

Oto cały kod tej procedury:

type
  wsk = ^rec;
  rec = record
    liczba : integer;
    nast : wsk;
    pop : wsk;
  end;

procedure quicksort(var tab : array of integer; pocz, kon : integer);
var
  tpocz, tkon, tmp, sr : integer;
begin
  tpocz := pocz;
  tkon := kon;
  sr := tab[(tpocz + tkon) div 2];
  repeat
    while tab[tpocz] < sr do
      inc(tpocz);
    while tab[tkon] > sr do
      dec(tkon);
    if tpocz <= tkon then begin
      tmp := tab[tpocz];
      tab[tpocz] := tab[tkon];
      tab[tkon] := tmp;
      inc(tpocz);
      dec(tkon);
    end;
  until tpocz > tkon;
  if tkon > pocz then
    quicksort(tab,pocz,tkon);
  if tpocz < kon then
    quicksort(tab,tpocz,kon);
end;

procedure sortuj(var pocz, kon : wsk);
var
tab : array of integer;
a, i : integer;
tmp : wsk;
begin
  new(tmp);
  if pocz = nil then
    Writeln('nie ma zadnych elementow')
  else
    a := 0;
    tmp := pocz;
    while tmp <> nil do begin
      tmp := tmp.nast;
      a := a + 1;
    end;
      tmp := pocz;
      setlength(tab,a);
    for i := 1 to a do begin
      tab[i] := tmp.liczba;
      tmp := tmp.nast;
    end;
    quicksort(tab,1,a);
    tmp := pocz;
    i := 0;
    while tmp <> nil do begin
      i := i + 1;
      tmp.liczba := tab[i];
      tmp := tmp.nast;
    end;
end;

Prosze o pomoc

Chyba powinna byc dereferencja wskaznika ? Cos w stylu:

tmp^.liczba := ...;

Tak, powinna być.
Chociaż to zależy czym kompiluje, Delphi pozwala na niejawną dereferencję (czyli tmp.liczba jest tym samym co tmp^.liczba) ale Free Pascal wymaga jawnego daszka, chyba że podano {$MODE DELPHI}.

Typ danych wskazuje na potrzebę zastosowania sortowania stogowego. Nie wiem czemu tu jest zastosowane sortowanie szybkie i na początku po prostu przepisuje się dane z tych zmiennych dynamicznych do tablicy. To nie stanowi idei problemu. Teoria mówi, że sortowanie stogowe zawsze daje wynik nie gorszy niż n*log(n) podczas gdy sortowanie szybkie może być nawet n do kwadratu.

quicksort z O(n^2)? gdzie to wyczytałeś, geniuszu?

QS jest klasy O(n^2) (w przypadku pesymistycznym).

z daszkiem czy bez jest to samo, chce tu zastosować quicksort, właściwie to powinno działać ale nie mam pojęcia co sie dzieje, czasem dodam 10 liczb i nie ma problemu, a czasem 5 i sie wysypuje :/

ŁF napisał(a)

quicksort z O(n^2)? gdzie to wyczytałeś, geniuszu?

Quicksort jest O(n^2). To że w praktyce jest szybki nie zmienia faktu, że w teorii jest powolny ;-)

n^{2 - ale w przypadku pesymistycznym. niemniej zdziwiłem się, zawsze uważałem quicksorta za jeden z najszybszych algorytmów sortujących i praktyka to potwierdzała, a tu teoria mówi o "nawet n}2/2". zewe - wybacz.

jafet napisał(a)

Witam, mam problem ze wskaznikami, dokładniej z sortowaniem, wyskakuje "invalid pointer operation" jest to dziwne bo czasem działa a czasem nie i nie mam pojęcia czemu tak jest.
Błąd pojawia sie w procedurze sortuj tutaj:

while tmp <> nil do begin
i := i + 1;
tmp.liczba := tab[i];
tmp := tmp.nast;
end;

tab jest dynamiczna więc indeksuje się ją od 0 do Length(tab)-1. a w kodzie jest indeksacja od 1 do Length(tab). Może to to.