Sortowanie

0

Przepraszam za glupie pytanie z najbardziej podstawowych podstaw informatyki, ale studiowalem mocno inne zagadnienia:

Czy ktos moglby mi podeslac algorytm sortowania szybszego niz babelki (wolniejszego zreszta pewnie nie ma...). Albo w Delphi, albo w jakims pseudokodzie, albo opisowo w ludzkim jezyku. Moze byc Basic tylko blagam bez C!!!

--Pawel

Delphi6

0

Mailnij do mnie .....

0

Do mnie tesh mozesh..
--Delphi 4

Skysh The God, Your Slave

0

K2, chetnie mailne ale daj swoj email albo sie zarejestruj na forum, pls.--Pawel

Delphi6

0

K2 [mailto:[email protected]] w dniu 6.3.2002 15:41 napisal:
Mailnij do mnie .....

Wal na forum - inny tez pewnie chcieli by wiedziec :)
Albo ja przesle cos zaraz...--Pozdrawiam!
Adam Boduch
www.4programmers.net

0

ja wymyslilem cos takiego (pascal);

uses crt;

var pomieszane,posortowane:array[1..100]of integer; { np.}
x,y,z:integer;

begin
randomize;
x:=0;
repeat
x:=x+1;
pomieszane[x]:=1+random(100); {no, musialem jakos pomieszac}
until x=100;
y:=0;
z:=0;
repeat
z:=z+1;
for x:=1 to 100 do
begin
if pomieszane[x]=z then
begin
y:=y+1;
posortowane[y]:=pomieszane[x];
end;
end;
x:=0;
until z=100;
for x:=1 to 100 do {Sprawdzenie (jak ktos nie wierzy)}
begin
write(x,'=',posortowane[x],' ');
end;
end.

ten program bedzie sortowal elementy tablicy o nazwaie 'pomieszane' w sposob rosnacy czyli
posortowane[1]:=najmniejszy element tablicy pomieszane

                         K_asm_il
0

Co do algorytmu wyzej, to ja moze sie myle, ale jak bede sortowal tablice [1..10] typu integer, to przez proste bombelki wykonam tylko 100 operacjii, a tamtym algorytmem okolo 64000 od kwadratu. Nie tak??
Chyba cos podobnego fachowo nazywa sie sortowaniem przez zliczanie, ale z zastrzezeniem, ze to dziala tylko jak jest maly zakres w porownaniu do ilsci liczb do posortowania.--Delphi 4

Skysh The God, Your Slave

0

A moze by tak quicksort?

var tab : array [1..30000] of Integer;
li : Integer;

Function Podziel(l,p : Integer):Integer;
var x,i,j,tmp : Integer;
Begin
x:=Random(p-l+1)+l;
tmp:=tab[l];
tab[l]:=tab[x];
tab[x]:=tmp;
x:=tab[l];
i:=l-1;
j:=p+1;
while TRUE do
begin
repeat
inc(i);
until tab[i]&gt=x;
repeat
dec(j);
until tab[j]&lt=x;
if i&ltj then
begin
tmp:=tab[i];
tab[i]:=tab[j];
tab[j]:=tmp;
end else
begin Podziel:=j; Exit; end;
end;
End;

Procedure QSort (l,p : Integer);
var q : Integer;
Begin
if l&ltp then
begin
q:=podziel(l,p);
QSort(l,q);
QSort(q+1,p);
end;
End;

BEGIN
for li:=1 to 30000 do
tab[li]:=30001-li;

QSort (1,30000);
END.

sorrki za objetosc...
pozdroowka dla forumowiczow - &y

0

Czy nazwa QuickSort oznacza ze jest to najszybszy znany sposob sortowania?--Pawel

Delphi6

0

Czy nazwa QuickSort oznacza ze jest to najszybszy znany sposob sortowania?
&gt
&gt--

Tak, jeden z najszybszych.--Pozdrawiam!
Adam Boduch
www.4programmers.net

0

Oj skyhs! Widac ze nie piszesz w pascalu. Po pierwsze operacja bedzie wtedy gdy element tablicy
pomieszanej bedzie odpowiadal 'z'. Sama petla hmm... Nie sprawdzalem ile to trwa.
Na moim kompie posortowanie tej 100 elementowej tablicy trwalo ulamek setnej sekundy.
A w ogóle sprawdziles jak dziala. Zrob lepszy i szybszy w pascalu.

A tak w ogole do ktorej chodzisz klasy?

                          K_asm_il
0

Hej sprawdziles jak dziala, to moze teraz zwieksz rozmiar tablicy do 10000 np. i pozostale zmienne,
chyba wiesz ze sortowanie zaczyna sie od drugiego repeat w tym programie a koncy na until z=100
jak zmienisz to until z=10000, oblicz ile to trwa dla 10000 elementowej tablicy.

                   K_asm_il
0

co do sortowania to Qsort jest szybkim algorytmem (nawet bardzo) ale ma jedno ALE

wielkie ALE polecam sprobowac posortowac tablice np. miliona elementow
ja jakies pol roku temu sortowalem liste o zawartosci ok 3 milionow rekordow
no i rekurencyjny Qsort nawet nie wchodzil w gre .

Wg mnie najlepszym algorytmem do duzych danych jest sortowanie przez kopcowanie
a jezeli dane do sortowanie dadza sie zaindeksowac to rewelacyjnie poradzi sobie
sortowanie binarne .

Polecam strone www.algorytm.cad.pl tam znajdziecie przyklady i fajne opisy
ale algorytmy te stanowia juz wyzszy pulap programistycznego fachu

milego kursu algorytmiki
wojta$--Lets make linux better :-)

0

Dopra, pomylilem sie w interpretacjii tego algorytmu, ale jestem 100% pewien, ze nie jest on optymalny w zadnym znaczeniu. Zgoda, najszybszy jest quicksort, ale ja wole heapsorta, bo quicksort jest szybki w srednim przypadku, ale moze dzialac dla niektorych danych jak zwykly nn, natomiast heapsort dziala nln(n) dla najgorszych danych. Poza tym jest to swietna kolejka priorytetowa. A co do mojego wieku, to nie uwazam, zeby ta informacja byla komus na forum potrzebna. Jakos nie widzialem zeby ktos sie tym chwalil, a ja nie zamierzam byc pierwszy.--Delphi 4

Skysh The God, Your Slave

0

Jak kogos to interesuje, to napisalem koponent pod Delphi 4 do sortowania HeapSortem. Do sciongniecia na skysh.prv.pl--Delphi 4

Skysh The God, Your Slave

0

OK, to jeszcze prosze o oswiecenie w nastepujacej kwestii: czy heapsort jest rekurencyjny? Bo moge miec sporo danych i troche sie obawiam co by mi sie stos od tej rekurencji nie rozpekl.

--Pawel

Delphi6

0

Heapsort jest rekurencyjny, ale rekurencja log(n) to nie jest tak duzo...Looknij do mojego komponentu...--Delphi 4

Skysh The God, Your Slave

0

Czy ja dobrze widze ze funkcja Parent niczemu nie sluzy?--Pawel

Delphi6

0

Ok, Skysh, wzialem Twoj kod i uzylem (nie komponent, bo ja sortuje tablice rekordow wg jednego z pol, wiec musialem troche poprzerabiac). Dziala pieknie, musze go tylko jeszcze przerobic zeby dzialal z tablicami indeksowanymi od zera (taka mam). Na razie jest rozwiazanie prowizoryczne... Move do chwilowej tablicy z przesunieciem o jeden rekord przed sortem i z powrotem po... Az mi wstyd przyznawac sie publicznie do takich brutalnych rozwiazan :-))))

WIELKIE DZIEKI SKYSH!--Pawel

Delphi6

0

Jasne ze kod jest prowizoryczny, to tylko schemat. Rzadko sie zdarza sortowanie Integerow. A co do tablicy od zer, to HeapSort ma tom niedogodnosc, ze korzen kopca musi miec index 1. Inaczej walom sie procedurki Parent itp. Mozna je zmienic, ale to komplikuje sam algorytm. Jesli chcesh to zrobic, to jeszcze zmien lokowanie pamieci na tablice z Size+1 na Size. Nio i powodzenia...--Delphi 4

Skysh The God, Your Slave

0

No widze wlasnie ze przerobka bylaby skomplikowano. Jestem przywiazany do tablicy indeksowanej od zera wiec chyba zostane przy rozwiazaniu przez Move...--Pawel

Delphi6

0

Jeszcze troche o sortowaniu. Jezeli ktos chce to kompletny kod do
QuickSorta:

procedure TMainForm.Sort(var iArray: array of Integer);

procedure QuickSort(iLow, iHigh : Integer);
var
iLo, iHi : Integer;
x, Temp : Integer;
begin
iLo := iLow;
iHi := iHigh;
X := iArray[(iLow + iHigh) div 2];
repeat
while iArray[iLo] &lt X do Inc(iLo);
while iArray[iHi] &gt X do Dec(iHi);
if (iLo &lt= iHi) then
begin
Temp := iArray[iLo];
iArray[iLo] := iArray[iHi];
iArray[iHi] := Temp;
Inc(iLo);
Dec(iHi);
end;
until iLo &gt iHi;
if (iHi &gt iLow) then QuickSort(iLow, iHi);
if (iLo &lt iHigh) then QuickSort(iLo, iHigh);
end;

begin
QuickSort(Low(iArray), High(iArray));
end;--Pozdrawiam!
Adam Boduch
www.4programmers.net

0

Proponuje umiescic QuickSorta i HeapSorta w dziale Algorytmy - obok BubbleSorta, ktory tam juz jest.--Pawel

Delphi6

0

Dopry pomysl, dzial algorytmy jest lekko zaniedbany. Przeciez sortowanie mozna wykonywac na niezliczonom ilosc sposobow, nie tylko bubble i quick. A co do parent, to sluzy ona do implementacji kolejki priorytetowej. Na stronce bedzie jutro poprawiona wersja mojego komponentu, z implementacjom kolejki priorytetowej. A co do algorytmow, to nalezy wspomniec, ze istniejom algorytmy shybshe od qoucksorta, ale dostosowane do okreslonych danych. Mozna sortowac nawet w czasie liniowym. Takie sortowanie kubelkowe czy przez zliczanie jest dosc proste do implementacji, a moze sie przydac. Moze doloncze do mojego komponentu. Pozdroofka @LL :)--Delphi 4

Skysh The God, Your Slave

0

Podsumowujac:
Skoro nie istnieje algorytm sortujacy za pomoca porownan o zlozonosci mniejszej niz (n lg n), to algorytmy sortowania przez kopcowanie, scalanie oraz quick-sort sa asymptotycznie optymalnymi algorytmami.

Natomiast, jesli wyjdziemy poza obszar sortowania za pomoca porownan istnieja algorytmy sortowania o mniejszej zlozonosci, chociazby juz wspomniane sortowanie przez zliczanie, ktore w uzywane w praktyce dla sortowania n elementow z przedzialu od 1 do k ma zlozonosc (k+n). Mozna wiec przyjac, ze jest to sortowanie w czasie liniowym :))) Kolejna zaleta tego algotrytmu jest jego "stabilnosc" tzn. liczby o tej samej wartosci w tablicy wynikowej wystepuja w tej samej kolejnosci co w tablicy poczadkowej, co jest istotne, gdy z sortowanymi elementami zwiazane sa dodatkowe dane.
Sredni czas sortowania kubelkowego rowniez jest liniowy, wiec tak samo jak w sortowaniu przez zliczanie otrzymujemy "szybkie" sortowanie przyjmujac pewne zalozenia o danych wejsciowych. Gdy w sortowaniu przez zliczanie zakladalismy, ze elementy sa malymi liczbami calkowitymi, to w sortowaniu kubelkowym zaklada sie, ze dane wejsciowe sa liczbami rzeczywistymi wybieranymi losowo z przedzialu [0, 1), zgodnie z rozkladem jednostajnym.
Jesli ktos doczytal do tego miejsca i bylby zainteresowany konkretnym algorytmem, to moge go zamiesc.

Pozdrawiam-- ---| p00f |---

Delphi (3, 4 ...) & Kylix r0x

  ---| p00f |---

1 użytkowników online, w tym zalogowanych: 0, gości: 1