Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

G - QuickSort
Idź do strony Poprzedni  1, 2
 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Stasiu
zielony żul



Dołączył: 16 Lis 2005
Posty: 919
Przeczytał: 0 tematów

Skąd: krk

PostWysłany: Wto 23:44, 28 Mar 2006    Temat postu:

tfu, mial byc random... juz sie gubie. poprawilem :p
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fidel
żul



Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Śro 0:07, 29 Mar 2006    Temat postu:

kg86 napisał:
mi przeszlo przy randomize-partittion, nie mialem zadnych optymilizacji, okazalo sie, ze wplyw na szybkosc mialo miejsce umieszczenia funkcji randomize... wczesniej mialem ja wywolywana przy kazdym zestawie raz... a kiedy zmienilem, aby wykonala sie tylko raz, zaraz za BEGIN, to poszlo bez problemu :) mzoe mialem szczescie... ;P


oj miales miales :twisted:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
h
pijak



Dołączył: 15 Lis 2005
Posty: 134
Przeczytał: 0 tematów


PostWysłany: Śro 18:35, 29 Mar 2006    Temat postu:

ja jeszcze raz. zrobiłem ten alg, dzielący na 3, tylko nie wiem czy o to chodzi (dalej TLE). w zwykłego quicksorta za elementami mniejszymi od piwotów wrzucam piwoty, później dopiero elementy większe i następnie odpalam to tylko dla tego co jest po lewej stronie pivotów i tego co jest po prawej. dalej TLE. randomize jest.
o co chodzi z flagą holenderską? nie było mnie na wykładzie.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
SZCZUR
żul



Dołączył: 09 Lis 2005
Posty: 603
Przeczytał: 0 tematów


PostWysłany: Śro 23:04, 29 Mar 2006    Temat postu:

jak zrobic to partition dzielace na 3 częsci?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 0:32, 30 Mar 2006    Temat postu:

Ustawiasz sobie dwa indeksy, nazwijmy je q1 i q2, na poczatku tablicy.
To beda granice pomiedzy tymi trzema sektorami. Bierzesz trzeci indeks i. Element podzialu wstawiasz do ostatniego elementu tablicy. I robisz fora po i od 1 do koniec tablicy - 1. W kazdym kroku sprawdzasz relacje pomiedzy a[i] i a [last]. Jesli a[i] > a[last] to nic nie robisz tylko zwiekszasz i. Jesli a[i] = a[last] to zamieniasz a[i] i a[q2] i zwiekszasz q2. Jesli zas a[i] < a[last] to musisz zrobic takiego swapa dla 3 elementow. Zwiekszasz q1 i q2, a[i] wstawiasz do a[q1], a[q1] do a[q2], a a[q2] do a[i]. I wszystko gra. na koncu q1 to pierwszy element z "sektora" rownych, a q2 pierwszy z sektora wiekszych... No i potem oczywiscie ten z ostaniego miejsca wstawiasz gdzie trzeba zwiekszajac co trzeba... Proponuje rozrysowac na kartce dla jakiejs malej tablicy - to jest naprawde proste do zobaczenia i zrozumienia...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Czw 3:11, 30 Mar 2006    Temat postu:

a ze sie tak zapytam, po co wy tak kombinujecie? przechodzi zwykly quicksort z cormena z partitionem hoare'a i randomizacja. nie trzeba niczego dzielic, odflagowywac czy nie wiem jeszcze czego....
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 14:00, 30 Mar 2006    Temat postu:

Nie no szczerze mowiac nie widze jak mozna zrobic quicksorta bez procedury partition... ;) Dzielic jednak trzeba, pytanie czy partitionem hoare'a czy lomuto. I o jakim odflagowywaniu Ty mowisz?? Ja tylko opisalem lekko udoskonalona wersje tego drugiego partitiona, bo niestety bez wylapywania rownych mialem TLE... I tyle, to nie jest zadne wydziwianie...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Sob 14:36, 01 Kwi 2006    Temat postu:

Jakie optymalizacje jeszcze moge dodac? ciagle mam TLE
Mam randomizacje w partition (wersja partition z wykladu) w quick sort sprawdzam czy R-L>20 jesli jest to wywoluje quicksort a pozniej na koniec insertionsort dla calej tablicy. Czy moze tu cos jest zle?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Sob 14:46, 01 Kwi 2006    Temat postu:

Ja zastosowałem mały trik - wczytując dane rozrzucałem je jak gnój po polu, ale nie randomem, tylko wykorzystując trzy liczby pierwsze ;]. Skorzystałem z tego, że jeśli n i k są względnie pierwsze, to przy wprowadzaniu n elementów i wpisywaniu i-tego elementu na pozycję i * k mod n każdy z nich trafia na inną pozycję (tablicę indeksujemy od 0 oczywiście), co dosyć solidnie niszczy wszelkie "wredne" dane, no chyba, że ktoś by pisał testy dokładnie pod mój algorytm :D. Jak znaleźć k względnie pierwsze z n? Ja zapamiętałem w programie 3 liczby: 421, 419 i 409, wszystkie trzy są pierwsze, więc żeby najmniejsza liczba, która nie jest względnie pierwsza z żadną z nich to 421*419*409 czyli koło 80 mld, więc gdyby przypadkiem n było wielokrotnością 421, to po prostu biorę 419 i ewentalnie 409. Dlaczego tylko 421? Bo to jest największa liczba pierwsza, która pomnożona przez 5 mld nie przekracza longinta ;]. No a po wykonaniu takiego manewru zwykły quicksort biorący pierwszą liczbę z lewej daje sobie radę.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
wuodi
pijak



Dołączył: 10 Lis 2005
Posty: 140
Przeczytał: 0 tematów


PostWysłany: Sob 15:57, 01 Kwi 2006    Temat postu:

zapomnialem jeszcze dodac ze na testrce gronostaju mam wszedzie ok
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
chlebek
alkoholik



Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów

Skąd: Siedlce\Kraków

PostWysłany: Sob 18:51, 01 Kwi 2006    Temat postu:

ostoj napisał:
a ze sie tak zapytam, po co wy tak kombinujecie? przechodzi zwykly quicksort z cormena z partitionem hoare'a i randomizacja. nie trzeba niczego dzielic, odflagowywac czy nie wiem jeszcze czego....

Chyba tylko Tobie tak przeszlo, ja przy takim zestawieniu mam TLE :?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
exeman
Mistrz grilla



Dołączył: 03 Lut 2006
Posty: 1601
Przeczytał: 0 tematów

Skąd: znienacka

PostWysłany: Sob 19:09, 01 Kwi 2006    Temat postu:

mi przeszedl zwykly quicksort z cormena (google: +cormen +quicksort +algorithm) z randomizacja.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Sob 19:43, 01 Kwi 2006    Temat postu:

Pamiętajcie, żeby _w miarę_ optymalnie pisać. Oczywiście najważniejszy jest czas asymptotyczny, ale jak dacie 10 zmiennych lokalnych albo parametrów funkcji, która jest wywoływana w każdej iteracji, to się może nagle okazać, że stała jest jednak za duża.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
chlebek
alkoholik



Dołączył: 04 Lut 2006
Posty: 556
Przeczytał: 0 tematów

Skąd: Siedlce\Kraków

PostWysłany: Sob 20:02, 01 Kwi 2006    Temat postu:

exeman napisał:
mi przeszedl zwykly quicksort z cormena (google: +cormen +quicksort +algorithm) z randomizacja.


Mi tez tylko musialem przezucic Randomize na poczatek programu i jest OK.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Nie 0:02, 02 Kwi 2006    Temat postu:

chlebek napisał:
Chyba tylko Tobie tak przeszlo, ja przy takim zestawieniu mam TLE :?

nie tylko mi. poczatkowo tez mialem tle. dopisalem uses buffering i poszlo.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Skrobocik
[SKROBORANGA]



Dołączył: 29 Lis 2005
Posty: 2958
Przeczytał: 0 tematów

Skąd: Skarżysko , Kraków

PostWysłany: Czw 18:40, 13 Kwi 2006    Temat postu:

Po pięciu bombach udało mi się zaliczyć, ale chuj idzie strzelić. Od zeszłego tygodnia się sypało. Okazało się, że TLE miałem, bo zamiast na żywca zamieniać, to miałem procedurkę exchange. Walnąłem partition do QuickSorta, zamiast oddzielnej procedury i poszło. Wielkie dzięki dla Hansa, gdyby nie On, to jeszcze bym siedział dłuuuuuuuuugo, walcząc z wiatrakami, bo miałem już kilka nastęnych wersji, też były TLE :?
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 2 i 3 semestr - Algorytmy i Struktury Danych Wszystkie czasy w strefie EET (Europa)
Idź do strony Poprzedni  1, 2
Strona 2 z 2

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin