Algorytm sortowania

[Karol Y]

Babelkowe to porownanie i ewentualna zamiana kazdej pary liczb w ciagu.
Wstawianie to ustawianie licz z ciagu od razu w odpowiedniej kolejnosci.

Jak dziala sortowanie przez wybieranie? Nie moge zrozumiec tych opsow na
stronach. Pisza raz, ze wstawiamy od razu na odpowiednie miejsce innym
razem, ze porownujemy jak w babelkowym.

[hue]

Post by Karol Y
Babelkowe to porownanie i ewentualna zamiana kazdej pary liczb w ciagu.
Wstawianie to ustawianie licz z ciagu od razu w odpowiedniej kolejnosci.
Jak dziala sortowanie przez wybieranie? Nie moge zrozumiec tych opsow na
stronach. Pisza raz, ze wstawiamy od razu na odpowiednie miejsce innym
razem, ze porownujemy jak w babelkowym.

w wybieraniu szukasz najmniejszego elementu z lista[1..n] i zamieniasz go
miejscami z pierwszym; nastepnie szukasz najmniejszego sposrod lista[2..n] i
zamieniasz z 2gim, itd...

pozdrowionka
M

[Wojtek Szweicer]

Post by hue

Post by Karol Y
Jak dziala sortowanie przez wybieranie?

w wybieraniu szukasz najmniejszego elementu z lista[1..n] i zamieniasz go
miejscami z pierwszym; nastepnie szukasz najmniejszego sposrod lista[2..n] i
zamieniasz z 2gim, itd...

Żeby przyspieszyć, szukasz jednocześnie najmniejszego i największego, a
potem zawężasz obszar do [2..n-1].
- Szwejk

PS. Czy to się nie nazywa sortowanie muszelkowe?

[Doodge]

Post by Wojtek Szweicer
PS. Czy to się nie nazywa sortowanie muszelkowe?

Nie, sortowanie "muszelkowe" czyli ShellSort, to zupelnie co innego...
tu jest opis: http://linux.wku.edu/~lamonml/algor/sort/shell.html
niestety po angielsku, ale w ramach potrzeb moge jeszcze o tym napisac...

Doodge

[Andrzej Gra¿yñski]

Post by Doodge
Nie, sortowanie "muszelkowe" czyli ShellSort, to zupelnie co innego...

Nazwa ShellSort pochodzi od nazwiska wynazlazcy, W .Shella, nie od muszelki.

AG

[z]

dodam że najczęściej stosuje się sortowanie "szybkie" i to także w
sosunku do plików, czyli nie stosuje się tych długich algorytmów
sortowania specjalnie dla plików które są nieco szybsze ale za to
wymagają dodatkowego miejsca na dysku równego wielokrotności wielkości
pliku, przy sortowaniu szybkim zmodyfikowanym dla plików stosuje się
możliwość dostępu swobodnego do plików definiowanych (ang. binary typed
files)

[Doodge]

Post by z
dodam że najczęściej stosuje się sortowanie "szybkie" i to także w
sosunku do plików, czyli nie stosuje się tych długich algorytmów
sortowania specjalnie dla plików które są nieco szybsze ale za to
wymagają dodatkowego miejsca na dysku równego wielokrotności wielkości
pliku, przy sortowaniu szybkim zmodyfikowanym dla plików stosuje się
możliwość dostępu swobodnego do plików definiowanych (ang. binary typed
files)

Tu tez nie do konca sie zgodze... Nie mozna ogolnie powiedziec, ze
QuickSort jest najlepszy... Szczegolnie, ze jego najczestsze
implementacje maja zazwyczaj zlozonosc pesymistyczna n^2...
Rownie popularny jest HeapSort... Czasem o wiele bardziej oplaca sie
zastosowanie PositionSorta...

Doodge

[hue]

Post by Doodge
Tu tez nie do konca sie zgodze... Nie mozna ogolnie powiedziec, ze
QuickSort jest najlepszy... Szczegolnie, ze jego najczestsze
implementacje maja zazwyczaj zlozonosc pesymistyczna n^2...

co za znaczenie implementacja? wazne sa dane wejsciowe do posortowania (w
pesymistycznym przypadku dajace brzydka zlozonosc). ale "w wiekszosci"
przypadkow (mowa o danych do posortowania) jest bardzo dobrze, dlatego
srednio jest n*log(n). dobra implementacja moze ew zmniejszyc ilosc
potrzebnej pamieci (przy rekurencji)

tak swoja droga, to bardzo dobra zlozonosc qsort ma na "bardzo
nieposortowanych" danych - tak wiec czasami lepiej jest je wymieszac przed
sortowaniem :)

pozdrowionka
Marcin

[Karol Y]

Post by Karol Y
Babelkowe to porownanie i ewentualna zamiana kazdej pary liczb w ciagu.
Wstawianie to ustawianie licz z ciagu od razu w odpowiedniej kolejnosci.
Jak dziala sortowanie przez wybieranie? Nie moge zrozumiec tych opsow na
stronach. Pisza raz, ze wstawiamy od razu na odpowiednie miejsce innym
razem, ze porownujemy jak w babelkowym.

A jakie znacie algorytmy sortowania jeszcze. Robie prace i mozliwie im
wiecej tym lepiej.

[Wojtek Szweicer]

Post by Karol Y
A jakie znacie algorytmy sortowania jeszcze. Robie prace i mozliwie im
wiecej tym lepiej.

To Pan robi czy my? Google na pewno zna sporo.
- Szwejk

[Charfa]

Post by Karol Y
A jakie znacie algorytmy sortowania jeszcze. Robie prace i mozliwie im
wiecej tym lepiej.

http://tinyurl.com/5t9gh
Opis wielu alg. i porównanie wydajności (188Kb zip)

[Doodge]

Post by Karol Y
A jakie znacie algorytmy sortowania jeszcze. Robie prace i mozliwie im
wiecej tym lepiej.

Kilka najpopularniejszych: www.programix.terramail.pl
W razie jakichkolwiek pytan zapraszam do kontaktu mailowego...


Doodge

[[e-mail]]

Post by Karol Y
Babelkowe to porownanie i ewentualna zamiana kazdej pary liczb w ciagu.
Wstawianie to ustawianie licz z ciagu od razu w odpowiedniej kolejnosci.
Jak dziala sortowanie przez wybieranie? Nie moge zrozumiec tych opsow na
stronach. Pisza raz, ze wstawiamy od razu na odpowiednie miejsce innym
razem, ze porownujemy jak w babelkowym.

generalnie jest tak:
algorytmy babelkowy i babelkowy dwukierunkowy (duuuzo lepszy, ale bez porownania
z alg. grupy insert itp) stosujemy do sortowania maksimum 50-100 danych,
algorytmy zamienianie, wstawianie, przestawianie itp stosuje sie dl ilosci
danych 50-500,
dalej sa algorytmy sortowania szybkiego i stogowe (quick i heap), dla ilosci
500-8, ktorych ze wzgledu na ich podejscie do danych (najpierw musza sobie je
przygotowac a wiec musza sie jakby przygotowac do wlasciwego sortowania) nie
stosuje sie do malej ilosci danych,
najszybsze sa algorytmy kubelkowe. te jednak potrzebuja bardzo duzo miejsca w
pamieci.
jest jeszcze moj algorytm zqSort najszybszy ze znanych mi. dziala niezaleznie od
ilosci danych, ale mozna go stosowac tylko do pewnego typu danych (liczby calkowite)
orientacyjne zlozonosci wybranych alg. w notacji duze O:
babelkowe : O(n^2)
quick, heap: O(nlogn)
kubelkowy, zqSort : O(n)

[hue]

Post by ***@tlen.pl
jest jeszcze moj algorytm zqSort najszybszy ze znanych mi. dziala niezaleznie od
ilosci danych, ale mozna go stosowac tylko do pewnego typu danych (liczby calkowite)

mozesz uchylic rabka tajemnicy, co to za cudo? ;)

Marcin

[Zeman]

Post by ***@tlen.pl

Post by ***@tlen.pl
jest jeszcze moj algorytm zqSort najszybszy ze znanych mi. dziala

niezaleznie od

Post by ***@tlen.pl
ilosci danych, ale mozna go stosowac tylko do pewnego typu danych

(liczby

Post by ***@tlen.pl
calkowite)
mozesz uchylic rabka tajemnicy, co to za cudo? ;)

sortowanie przez zliczanie ;) Nie jest to sortowanie metoda porownywania
kluczy czyli ze porownujemy 2 elementy ktory wiekszy a ktory mniejszy.
Sortowanie z porownywaniem kluczy nigdy nie osiagnie zlozonosci mniejszej
niz n log n.

VAR
a : array[0..100000] of byte;
b: array[0..255]of integer;

// wypelnij a losowymi wartosciami
// wypeln b zerami

for i:=0 to 100000 do
inc(b[a[i]]);

// w b masz ile razy jaka wartosc z a wystapila, wiec mozesz latwo przepisac
spowrotem do a ;)


Pozwiodronka,
Zeman

[zieliq]

Post by ***@tlen.pl

Post by ***@tlen.pl

Post by ***@tlen.pl
jest jeszcze moj algorytm zqSort najszybszy ze znanych mi. dziala

niezaleznie od

Post by ***@tlen.pl
ilosci danych, ale mozna go stosowac tylko do pewnego typu danych

(liczby

Post by ***@tlen.pl
calkowite)
mozesz uchylic rabka tajemnicy, co to za cudo? ;)

sortowanie przez zliczanie ;) Nie jest to sortowanie metoda porownywania
kluczy czyli ze porownujemy 2 elementy ktory wiekszy a ktory mniejszy.
Sortowanie z porownywaniem kluczy nigdy nie osiagnie zlozonosci mniejszej
niz n log n.
VAR
a : array[0..100000] of byte;
b: array[0..255]of integer;
// wypelnij a losowymi wartosciami
// wypeln b zerami
for i:=0 to 100000 do
  inc(b[a[i]]);
// w b masz ile razy jaka wartosc z a wystapila, wiec mozesz latwo przepisac
spowrotem do a ;)
Pozwiodronka,
Zeman

hmmm,
to chyba ja powiennem odpowiadac na prosbe opisu tego mojego algorytmu
w zasadzie to mozna go podpiac pod kubelkowy
mamy np do posortowania takie liczby:
2,1,5,7
deklarujemy tablice:integer od 1 do 7 (max wartosc z elementow)
i wypelniamy ja tak:
1,2,x,x,5,x,7
czyli sprowadzamy liczby wg ich wartosci do nowej tablicy w miejsca o
indeksach wartosci tych liczb
i pozniej usuwamy puste pola
czyli dostajemy posortowana tablice:
1,2,5,7

mam nadzieje ze nie zakrecilem z mocno

[Zeman]

Post by zieliq
hmmm,
to chyba ja powiennem odpowiadac na prosbe opisu tego mojego algorytmu

zgadzam sie... totez nie napisalem ze to Pan mial na mysli tylko podalem
swoj przyklad wlaczajac sie do dyskusji ;)

Post by zieliq
w zasadzie to mozna go podpiac pod kubelkowy
2,1,5,7
deklarujemy tablice:integer od 1 do 7 (max wartosc z elementow)
1,2,x,x,5,x,7
czyli sprowadzamy liczby wg ich wartosci do nowej tablicy w miejsca o
indeksach wartosci tych liczb
i pozniej usuwamy puste pola
1,2,5,7
mam nadzieje ze nie zakrecilem z mocno

Nie jestem pewiem czy dobrze rozumiem.
A = (2,1,5,7)
B : array[min(A) .. max(A)] // wypelnione zerami
P : array[min(A) .. max(A)] // pokazuje ktore pola sa puste ("x"), puste:
"x" wypelnione "w"
teraz "i wypelniamy ja tak" :
for i:=min(A) to max(A) do
begin
B[A[i]]= i;
P[A[i]]='w';
end;
teraz "usuwamy puste pola", czyli te B[i], ze P[i]='x' : if P[i]='x' then
delete(B[i])


Dolaczam do grona zaciekawionych :)

Pozwiodronka,
Zeman.

[hue]

Post by zieliq
hmmm,
to chyba ja powiennem odpowiadac na prosbe opisu tego mojego algorytmu
w zasadzie to mozna go podpiac pod kubelkowy
2,1,5,7
deklarujemy tablice:integer od 1 do 7 (max wartosc z elementow)
1,2,x,x,5,x,7
czyli sprowadzamy liczby wg ich wartosci do nowej tablicy w miejsca o
indeksach wartosci tych liczb
i pozniej usuwamy puste pola
1,2,5,7

chmm... w zasadzie, to jest kubelkowy :)
i do tego z bledem - co, gdy masz dwie takie same liczby?

...a myslalem, ze bedzie cos na prawde oryginalnego

pozdrowionka
Marcin

[zieliq]

Post by hue
chmm... w zasadzie, to jest kubelkowy :)
i do tego z bledem - co, gdy masz dwie takie same liczby?
...a myslalem, ze bedzie cos na prawde oryginalnego
pozdrowionka
Marcin

przepraszam, ze zawiodlem i nie jest oryginalnie...
Że z bledem to sie nie zgodze bo dobrze sortuje wielkie tablice integer zarowno
powtarzajace sie jak i z ujemnymi wartosciami. a przeciez podalem tylko glowna
mysl a nie implementacje. o ile pamietam to wystarcza 4 warunki aby bylo
poprawnie.
i jeszcze jedno: trudno tu sie chwalic wlasnym algorytmem. po prostu w testach
(dla odpowiednich danych (int > 10^6)) wypadl duzo lepiej niz qsort czy
heapsort. przy parolinijkowej implementacji az pieknie sie patrzy jak bije alg.
rekurencyjne. jest prosty do zrozumienia, chyba nawet prostrzy niz babelkowy,
ale jak pisalem wczesniej, nie widze dla niego zastosowania.

[hue]

Post by Zeman
sortowanie przez zliczanie ;) Nie jest to sortowanie metoda porownywania
kluczy czyli ze porownujemy 2 elementy ktory wiekszy a ktory mniejszy.
Sortowanie z porownywaniem kluczy nigdy nie osiagnie zlozonosci mniejszej
niz n log n.

dziekuje za wyklad, ale w tym sie akutar orientuje - chcialem zobaczyc
algotym kolegi, gdyz podobno jest jego i do tego najszybszy :)

pozdrawiam
Marcin