Implementacja algorytmu quick sort z usprawnieniami. Github link: github.com/KB-tutorials/Algor...
Пікірлер: 11
@piotrwojtaszek1 Жыл бұрын
przy Twoich przykładach wychodzi że quick sort jest x45 wolniejszy od merge sorta przy tablicy o wielkości miliona elementów
@holyshit9227 жыл бұрын
Jedno z wywołań rekurencyjnych można zastąpić iteracją Gdyby chciał zastąpić drugie wywołanie rekurencyjne iteracją trzeba by było użyć dodatkowej tablicy Z sortowań dla tablic tylko przez porównania to już chyba wszystkie z tych ważniejszych bo np Shell sort to taka nieudana próba przyspieszenia sortowania przez wstawianie Są też próby usunięcia przypadku pesymistycznego z quick sorta Większość ogranicza się do sortowania tablic ale co gdy dane do posortowania nie mieszczą się w dostępnej dla nas pamięci RAM Tak czy siak temat sortowania powoli się wyczerpuje i ciekaw jestem co dalej
@misterkoko-code51407 жыл бұрын
Trzymam kciuki za proste szyfrowanie i odszyfrowywanie.
@holyshit9227 жыл бұрын
Jak będziesz cierpliwy to pewnie się doczekasz Jest sporo tematów jeśli chodzi o algorytmy Dokończenie sortowania zostało mu tzw zewnętrzne a także przez zliczanie , pozycyjne czy kubełkowe Na algorytmach są też wspominane wyszukiwania liniowe i binarne (Binarne jest szybsze ale zakłada że ciąg danych jest posortowany Algorytmy z powrotami (na zaliczenie lubią dawać hetmany i skoczka) Otoczka wypukła (Jarvis , Graham) Struktury danych stosy, kolejki, listy O kopcu już mówił w kontekście sortowania , może warto do niego wrócić aby zrealizować kolejkę priorytetową drzewa,grafy Jakieś algorytmy grafowe np cykl Eulera, szukanie ścieżek problem komiwojażera , Algorytmy inne problem plecakowy Problem dla którego istnieje algorytm w działający w czasie wielomianowym jest łatwym problemem
@misterkoko-code51407 жыл бұрын
W takim razie sporo pracy przed autorem ;)
@holyshit9227 жыл бұрын
Z sortowań to na razie tylko te zewnętrzne związane z plikami mu zostały Jeżeli chodzi o listę to tylko na wskaźnikach W Javie jako takich wskaźników nie ma ale chyba referencja jest Skoro zdecydował się na Javę to nie pokaże jak zwalniać pamięć na węzły , między innymi dlatego uważam że Java nie nadaje się jako język do algorytmów Ostatnio spisałem funkcje i procedury do obsługi listy (*Funkcje do obsługi stosu i kolejki*) Funkcja sprawdzająca czy lista jest pusta Funkcja dodająca węzeł na początek listy Funkcja dodająca węzeł na koniec listy Funkcja zdejmująca pierwszy węzeł z listy (*Funkcje dodające i usuwające węzły*) Funkcja dodająca węzeł za węzłem o danym kluczu Funkcja dodająca węzeł przed węzłem o danym kluczu Funkcja dodająca węzeł w sposób uporządkowany Funkcja usuwająca węzeł o danym kluczu Funkcja usuwająca wszystkie węzły z listy (*Funkcje dodatkowe*) Funkcja zwracająca liczbę węzłów listy Funkcja odwracająca kolejność węzłów listy (tylko dla list jednokierunkowych) Funkcja wyszukująca węzeł o danym kluczu Funkcja zapisująca listę do pliku Funkcja wczytująca listę z pliku Funkcja sortująca listę przez scalanie Funkcja wypisująca dane zawarte w węzłach listy
@misterkoko-code51407 жыл бұрын
Jeśli uda mi się zrozumieć jak działa 70% tych rzeczy, któe są tu wypisane to będę z siebie bardzo zadowolony. Poza tym jeszcze mi się nie zdarzyło słyszeć że Java się nie nadaje do algorytmów, gdyba tak było to zwolennicy innych języków szybko by to wywlekli i wałkowali.