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 1, 2  Następny
 
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ść
Pandunia
Gość






PostWysłany: Nie 22:16, 19 Mar 2006    Temat postu: G - QuickSort

[deleted]

Ostatnio zmieniony przez Pandunia dnia Pią 5:31, 10 Lis 2006, w całości zmieniany 1 raz
Powrót do góry
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: Nie 22:24, 19 Mar 2006    Temat postu:

Nie byles, ale doszlismy z jagmem do wniosku ze nie bedziemy ludzi dolowac i taktownie przemilczymy pojawienie sie nowych zadan :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
jagm
zielony żul



Dołączył: 01 Lut 2006
Posty: 1421
Przeczytał: 0 tematów


PostWysłany: Nie 23:02, 19 Mar 2006    Temat postu:

cóż może być bardziej wymownego od ciszy :D
no chyba że HKD :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Pon 0:37, 20 Mar 2006    Temat postu:

kurcze... w tym tygodniu się postarali, dali nam te zadanka już w niedzielę... tym razem zadania sponsorują literki F i G :) na szczeście R7 już mam z głowy, ale mam jeszcze zaległości a zadaniu A ;/ coś czuję, że nie wyśpię się w tym tygodniu ;/

życzę powodzenia! :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Pon 1:09, 20 Mar 2006    Temat postu:

Jak komuś przeszło to niech się pochwali :wink: i powie jakim to sposobem zrobił. Ja próbowałem, wrzuciłem wszystkie optymalizacje o jakich była mowa w wykładzie, nie przekazuję do procedur żadnych parametrów, żadnych zmiennych lokalnych, quicksort iteracyjny, partition próbowana zarówno wersja z medianą jak i losowa, insertion z wartownikiem....

i ciągle TLE :evil:
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
tikan
[świeżak]



Dołączył: 20 Mar 2006
Posty: 1
Przeczytał: 0 tematów


PostWysłany: Pon 1:30, 20 Mar 2006    Temat postu: G - QuickSort

A ktorej wersji partitiona uzywasz?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Rogal
Zjeb z kaszanką



Dołączył: 13 Mar 2006
Posty: 1745
Przeczytał: 0 tematów

Skąd: koło podbiegunowe

PostWysłany: Pon 1:44, 20 Mar 2006    Temat postu:

Teraz wogóle znalazłem jakiś algorytm Żenczykowskiego w C++ z zeszłego roku. Tam partition jest wstawiony w quicksorta i ogólnnie trochę lepiej to wygląda. Ale dalej TLE.

btw. tamten partition wybiera środkowy element, próbowałem też z losowym i medianą

Edited ok. 2:15:
Po 5 godzinach siedzenia nad kodem i 31 nieudanych próbach w końcu przeszło. Nie chcę więcej nawet słyszeć o tym zadaniu. :?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
mateo
pijak



Dołączył: 08 Mar 2006
Posty: 296
Przeczytał: 0 tematów

Skąd: Krk - Biały Prądnik

PostWysłany: Pon 18:57, 20 Mar 2006    Temat postu:

Rogal napisał:
Po 5 godzinach siedzenia nad kodem i 31 nieudanych próbach w końcu przeszło. Nie chcę więcej nawet słyszeć o tym zadaniu.


No coz :D tak to bywa... nie wszystko chce za pierwszym razem przechodzic:) Mi jakos przeszlo chociaz jedyna optymalizacja jaka zrobilem to randomized_partition.. no ale wystarczylo.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kap00ch
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów

Skąd: ja sie tu wzialem?

PostWysłany: Pon 19:03, 20 Mar 2006    Temat postu:

no co ty mowisz:O tylko randomized??
to ja juz 2h sie z TLE mecze i mam wszystkie optymalizacje z wykladu, a teraz lece juz 4 metode po laczonym randomizie z mediana :D :P
ewidentnie mnie nie lubi ta sprawdzara:P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
mateo
pijak



Dołączył: 08 Mar 2006
Posty: 296
Przeczytał: 0 tematów

Skąd: Krk - Biały Prądnik

PostWysłany: Pon 19:09, 20 Mar 2006    Temat postu:

Kap00ch napisał:
to ja juz 2h sie z TLE mecze i mam wszystkie optymalizacje z wykladu, a teraz lece juz 4 metode po laczonym randomizie z mediana


Ja tam nie wiem co za optymalizacje byly na wykladzie bo poki co jeszcze nie czytalem zadnych notatek z wykladow :).... a tych optymalizacji co znam nie chcialo mi sie wklepywac.. bo cale zrobienie G to polegalo u mnie na przepisaniu kodu z C++ na Pascala. Przewaznie randomized_sort mi wystarczal wiec sie nie staralem bardziej. Moze po prostu sprawdzaczka wylosowala mi lepsze elementy podzialu?:D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kap00ch
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 1840
Przeczytał: 0 tematów

Skąd: ja sie tu wzialem?

PostWysłany: Pon 19:12, 20 Mar 2006    Temat postu:

najwyrazniej ma swoje sympate i antypatie :P teraz wyplula mi TLE po 4 :O minutach queued :P

ad: 18:33
MeGa LOL :O ta sprawdzara jest powalona...stosowalem miedzy innymi metode z insertionsortem...ja wiadomo insertion optymalnie dziala dla grup 8-20 elementow...jednak testy mowia co innego:P
otoz od 2h odpalalme to na testerce z roznymi warintami randomizacji ,analiz danych, liczenia median i randomizacji z medianami i analiza, w efkecie na pesymistycznym tescie mialem u siebie na kompie 5,6s i...tcs mowi TLE...w akcie desperacji zaczalem jak szlaony zemieniac liczbe od ktorej wlacza sie insert...pomimo ze u mnie czasy dramnatycznie wzrosly bo na pesymistycznym mialem juz 11s to sprawdzarka nagle powiedziala OK :O to jest wrecz nienormalne...zycze powodzenia tym ktorzy maja mniejszego farta:P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Pon 22:19, 20 Mar 2006    Temat postu:

Po 8 wnerwiających mocno submitach i po wpadnieciu na przyczyne moich TLE zamieszczam, taką mala podpowiedź(pewnie i tak ćwiczeniowcy to omowia jutro...no ale moze ktos chce dzisiaj miec to z glowy :) ):
do rozwiazania tego zadania wystarczą dwie optymalizacje:
1) Losowanie elementu dzielacego
2) Modyfikacja algorytmu żeby dzielił tablice na mniejsze, rowne i wieksze i zapuszczanie rekurencji(iteracji) tylko dla tych el. mniejszych i większych.

Pewnie nawet rekurencja przejdzie, chociaż lepiej na stosie - bezpieczniej ;)
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: Wto 0:30, 21 Mar 2006    Temat postu:

Wielkie dzieki, Robson!!!! Jestes wielki :D (wiem, ostatnio to wyrazenie jest mocno naduzywane :D). Ale faktem jest ze bez tego co powiedziales jeszcze dluuuuuuugo bym sie meczyl.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Spectro
Mistrz grilla



Dołączył: 09 Mar 2006
Posty: 2306
Przeczytał: 0 tematów

Skąd: Kurdwanów

PostWysłany: Wto 21:51, 21 Mar 2006    Temat postu:

Ja miałem algorytm Żenczykowskiego w C++ z drobną modyfikacją przy wczytywaniu danych (losowy początkowy indeks) - taki, jaki miałem omówiony na ćwiczeniach. Przeszło w pierwszej próbie ;) .
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Pawel Str.
pijak



Dołączył: 06 Lut 2006
Posty: 429
Przeczytał: 0 tematów

Skąd: Ze starszego roku / Z Gorlic

PostWysłany: Wto 22:54, 21 Mar 2006    Temat postu:

Ja miałem algorytm, który tak, jak w medianie, dzielił na 3 zbiory. Środkowy nie był już dalej sortowany. Dzięki temu w jednym kroku rozwiązywałem przypadek ciągu stałego.
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: Śro 2:04, 22 Mar 2006    Temat postu:

jesli ktos jeszcze nie zrobil G, to zapraszam na gronostaja, przed chwila dodalem testy (same skrajne i chamskie przypadki :P)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
shell
pijak



Dołączył: 14 Lis 2005
Posty: 35
Przeczytał: 0 tematów


PostWysłany: Pią 5:46, 24 Mar 2006    Temat postu:

jak do tej pory nie potrafilem napisac najprostrzej wersji quicka to po dzisiejszych 5h umie na pamiec kilkanascie jego wariacji!!! moze i to G mialo jakis sens...:) Poszlo z mediana trzech + random i prostym wstawianiem dla n<10
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fen
zielony żul



Dołączył: 22 Lut 2006
Posty: 946
Przeczytał: 0 tematów

Skąd: Bochnia

PostWysłany: Pon 19:10, 27 Mar 2006    Temat postu:

a ja zrobiłem: medianę z trzech, obcinanie dla małych danych (użyłem insertion sort dla < 10), randomizacja... na gronostaju mi śmiga pięknie, ale niestety sprawdzarka wywali mi TLE. No nic trzeba to jeszcze bardziej przeanalizować... ale zrobiłem wersję rekurencyjną... hmmm... może tutaj kryje się gdzieś wąskie gardło..
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: Pon 19:20, 27 Mar 2006    Temat postu:

Sama mediana z trzech nie pomoze poniewaz sa na nia pesymistyczne przypadki w testach... Musisz zrobic randomizacje i jakos sensownie obslugiwac ciagi stale... I powinno byc git :)
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: Pon 19:33, 27 Mar 2006    Temat postu:

hmmm randomizacja + partition hoare'a + uses buffering i ok
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: Wto 17:17, 28 Mar 2006    Temat postu:

ale jak omijać ciągi stałe? przez pivota? można to jakoś w algorytmie hoare'a zaimplementować? ( z dwóch stron wskaźniki idą )
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: Wto 21:58, 28 Mar 2006    Temat postu:

Wedlug mnie najlepiej jest to zrobic algorytmem partition w wersji lomuto ale rozszerzonym do trzech a nie dwoch "sektorow"... Tak jak ten problem flagi holenderskiej bodajze o ktorym bylo wspomniane na wykladzie...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
kg86
zielony żul



Dołączył: 22 Gru 2005
Posty: 1194
Przeczytał: 0 tematów

Skąd: pochodze?

PostWysłany: Wto 22:37, 28 Mar 2006    Temat postu:

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
Powrót do góry
Zobacz profil autora
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:27, 28 Mar 2006    Temat postu:

i takim o to sposobem, po 12 bombach dolaczam do grupy ludzi ktora to przepuscila :D :

random, insetrtion ponizej 20 elementow i podzial na 3 czesci (holenderska flaga) (thx hansu ;) )
chcialem z tym podzialem na 3 czesci zrobic wczesniej ale "zgubilem" jedna instrukcje przez co quick zle porzadkowal zbior a TLE dostawalem jak na koncu wlaczal sie insertion :/


Ostatnio zmieniony przez Stasiu dnia Wto 23:44, 28 Mar 2006, w całości zmieniany 2 razy
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: Wto 23:30, 28 Mar 2006    Temat postu:

przekombinowales :P
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 1, 2  Następny
Strona 1 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