Informatyka UJ forum

Stasiu · Wysłany: Wto 23:44, 28 Mar 2006 Temat postu:

tfu, mial byc random... juz sie gubie. poprawilem :p

Fidel · Wysłany: Śro 0:07, 29 Mar 2006 Temat postu:

h · Wysł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.

SZCZUR · Wysłany: Śro 23:04, 29 Mar 2006 Temat postu:

jak zrobic to partition dzielace na 3 częsci?

hansu · Wysł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...

ostoj · Wysł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....

hansu · Wysł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...

wuodi

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?

Madras

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ę.

wuodi

zapomnialem jeszcze dodac ze na testrce gronostaju mam wszedzie ok

chlebek

exeman

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

Madras

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.

chlebek

ostoj

Skrobocik

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 :?