Procedura sortująca QSort przeniesiona pod Delphi z C z małą modyfikacją.

Tao

Chciałbym podzielić się pewną procedurką mającą na celu posortowanie wszelkich elementów dowolnego typu, np.niech będzie to zmienna rekordowa:

type
_tab = record
a: integer;
b: real;
c: string;
d: char;
{itd...}
end;

var
tab: array [1..50] of _tab;

I mamy naszą tablicę;) Może to być również tablica na wskaźnikach, nie ma ku temu żadnych przeszkód, wazne jest by dokładnie zrozumieć sens działania tej procedury. W zalezności z jakimi argumentami ją wykonamy zostanie posortowana nasza tablica na wiele sposobów, ale zawsze będą brane pełne ciagi tablicy jaką podamy i tyle tych ciągów - z ilu składa się nasza tablica (rekordy), oczywiście możemy podać argumenty tak, by zostało posortowane tylko 10 pierwszych elementów, czy ewentualnie tak, by został wycięty z niej dowolny kawałek i na nim wszystko zostało wykonane nie naruszając całej reszty! Ja zaprezentuję tylko jedna możliwość. Otóż - mamy naszą tablicę, któa składa się z 50 elementów, a w której każdy element posiada dodatkowe wartości (a,b,c,d...itd), wybierzmy sobie teraz, któa wartość ma być brana pod uwagę przy sortowaniu - niech będzie to "b" typu real, przekonacie się, że zadziała to przy każdym typie;) Sztuczka polega na wykorzystaniu kodu asci gdzie każdy znak, czy cyfra w kolejności jest większa od poprzednika, oczywiście wszystko sortowane jest od końca, więc w prosty sposób nie popełnimy błędów gdy np. liczby reprezentowane są odwrotnie, to znaczy najpierw bajt młodszy a potem starszy (jeśli się pomyliłem to poprawcie - każdy chyba wie dokładnie o co idzie).

Ok, jeśli będę chciał posortować całą tablicę biorąc pod uwagę tylko wartość zmiennej "b" wykonałbym coś takiego:

b>QSort(@tab,sizeof(tab),@tab.b,sizeof(tab.b),50);</b
lub:
b>QSort(@tab,sizeof(_tab),@tab.b,sizeof(real),50);</b

Wszystko;) Teraz tylko należało by wyświetlić zawartość tabeli i okaże się, że jest ona posortowana tak jak to zostało zaplanowane wyżej. Jednocześnie zawartość cząstkowych pól rekordów została zachowana, sprawdźcie sami.

Co zaś do samej metody sortowania, to wykorzystana tu została metoda bąbelkowa, bo najprostrza, ale to już chyba nie problem, by rozwinąć ten algorytm i zastosować tu coś szybszego;)

I jeszcze małe wyjaśnienie: Procedurkę napisałem, podczas tłumaczenia jednego programu z C do Pascala, troszkę jest ona przerobiona, zautomatyzowana, w C były to dwie procedury, Qsort i druga, którą należało napisać samodzielnie odpowiedzialną za samo sortowanie. Mi jednak zależało, by wszystko było realizowane w jednej procedurce, po czym mozna ja było wykorzystać na poczekaniu.

I jeszcze małe wyjaśnienie odnośnie parametrów:
a) adr i size_elementu to dane całej tablicy,
b) adres i ile to dane elementu pierwszego żądanego wiersza tablicy,
c) ilosc_elementow to ilosc elementow w tablicy do posortowania;)

Argumenty (a) i (c) pozwalają procedurze na poprawne przesortowanie, a argumenty (b) to tylko informacje wskazujące na wartość, która ma zostać porównywana w czasie sortowania;)

Poniżej źródło samej procedurki, pozdrawiam wszystkich,
Jacek Leszczyński.

procedure QSort(adr:pointer;size_elementu:longint;adres:pointer;ile,ilosc_elementow:longint);
var
ii,i,j,k,l: integer;
p1,p2,p11,p22: ^byte;
b: byte;
q: integer;
begin
for ii:=1 to ilosc_elementow {ilosc_elementow} do for i:=0 to ilosc_elementow-2 do
begin
j:=i+1;
p1:=adres;
inc(p1,i
size_elementu);
p2:=adres;
inc(p2,jsize_elementu);
for k:=ile-1 downto 0 do
begin
{ przeprowadzam porównanie }
p11:=p1; inc(p11,k);
p22:=p2; inc(p22,k);
q:=0;
if p11<p22 then q:=1;
if p11>p22 then q:=2;
if q=0 then continue;
if q=1 then break;
{ zamieniam strony }
for l:=0 to size_elementu-1 do
begin
p11:=adr; inc(p11,i
size_elementu+l);
p22:=adr; inc(p22,(i+1)*size_elementu+l);
b:=p11^;
p11:=p22;
p22^:=b;
end;
break;
end;
end;
end;

2 komentarzy

ciekawe jak to będzie działać przy danych typu zmienno-przecinkowego ;)

if p11 if p11>p22^ then q:=2; ciekawe jak to będzie działać :)