algorytmiczny problem porządkowania zbioru elementów w odniesieniu do jakiejś relacji porządkowania.
W standardowym kursie z algorytmów uczymy się, że quicksort wynosi średnio a O ( n 2 ) w najgorszym przypadku. Jednocześnie badane są inne algorytmy sortowania, które w najgorszym przypadku to O ( n log n ) (np. Scalesort i heapsort ), a nawet czas liniowy w najlepszym przypadku (np. Bąbelkowy ),...
Istnieją dwie metody partycji Quicksort wymienione w Cormen: Hoare-Partition(A, p, r) x = A[p] i = p - 1 j = r + 1 while true repeat j = j - 1 until A[j] <= x repeat i = i + 1 until A[i] >= x if i < j swap( A[i], A[j] ) else return j i: Lomuto-Partition(A, p, r) x = A[r] i =...
Podczas nauki w szkole średniej natknąłem się na wiele algorytmów sortowania. Jednak nigdy nie wiem, która jest najszybsza (dla losowej liczby całkowitej). Więc moje pytania to: Który jest najszybszym obecnie znanym algorytmem sortowania? Teoretycznie jest możliwe, że są jeszcze szybsze? Jaka...
Mam problem ze znalezieniem dobrych zasobów, które dają najgorszy przypadek w miejscu stabilnego algorytmu sortowania. Czy ktoś wie o dobrych zasobach?O ( n lnn )O(nlnn)O(n \ln n) Tylko przypomnienie, w miejscu oznacza, że wykorzystuje przekazaną tablicę, a algorytm sortujący może używać tylko...
Zastanawiam się, czy istnieje standardowy sposób pomiaru „sortowania” tablicy? Czy tablicę z medianą liczby możliwych inwersji można uznać za maksymalnie nieposortowaną? Rozumiem przez to, że jest to w zasadzie tak daleko, jak to możliwe, od sortowania lub odwrotnego...
Jaki byłby najszybszy sposób na zrobienie tego (z punktu widzenia algorytmu, a także ze względów praktycznych)? Myślałem o czymś następującym. Mógłbym dodać na końcu tablicy, a następnie użyć bąbelkowego sortowania, ponieważ ma najlepszy przypadek (tablica całkowicie posortowana na początku),...
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita nie była...
Na Wikipedii napisano, że „... sortowanie selekcji prawie zawsze przewyższa sortowanie bąbelkowe i sortowanie gnomów”. Czy ktoś może mi wyjaśnić, dlaczego sortowanie jest uważane za szybsze niż sortowanie bąbelkowe, mimo że oba mają: Złożoność najgorszego przypadku :O(n2)\mathcal O(n^2) Liczba...
Szukam algorytmu do dystrybucji wartości z listy, aby powstała lista była jak najbardziej „zrównoważona” lub „równomiernie rozłożona” (w cudzysłowie, ponieważ nie jestem pewien, czy są to najlepsze sposoby na opisanie jej ... później przedstawię sposób pomiaru, czy wynik jest lepszy niż inny). Tak...
Zaskakująca liczba problemów ma dość naturalne ograniczenia w programowaniu liniowym (LP). Przykłady, takie jak przepływy sieciowe, dopasowanie dwustronne, gry o sumie zerowej, najkrótsze ścieżki, forma regresji liniowej, a nawet ocena obwodu, patrz rozdział 7 w [1]! Ponieważ ocena obwodu...
W sortowaniu radix najpierw sortujemy według najmniej znaczącej cyfry, a następnie sortujemy według drugiej najmniej znaczącej cyfry itd. I kończymy na posortowanej liście. Teraz, jeśli mamy listę liczb, potrzebujemy bitów, aby odróżnić te liczby. Tak więc liczba wykonanych przez nas przejść...
Na stronie internetowej Sorting Algorytmy wysunięto następujące oświadczenie: Idealny algorytm sortowania miałby następujące właściwości: Stabilny: nie zmienia się kolejności klawiszy równych. Działa w miejscu, wymagając dodatkowej przestrzeni.O ( 1 )O(1)O(1) Porównania klawiszy w...
Znajdź najmniejszą liczbę porównań potrzebną do posortowania (uporządkowania) pięciu elementów i opracuj algorytm, który sortuje te elementy przy użyciu tej liczby porównań. Rozwiązanie : Jest ich 5! = 120 możliwych wyników. Dlatego drzewo binarne do procedury sortowania będzie miało co najmniej...
Ogólne algorytmy sortowania zazwyczaj wymagają zestawu danych do sortowania i funkcji komparatora, która może porównywać dwa pojedyncze elementy. Jeśli komparator jest relacją rzędu¹, to wynikiem działania algorytmu jest posortowana lista / tablica. Zastanawiam się jednak, które algorytmy...
Sortowanie Radix jest teoretycznie bardzo szybkie, gdy wiesz, że klucze znajdują się w pewnym ograniczonym zakresie, np. wartości z zakresu [ 0 … n k - 1 ] . Jeśli k < lg n po prostu przekonwertujesz wartości na bazę n, co zajmuje Θ ( n ) czasu, wykonaj sortowanie podstawy n radix, a następnie...
Szukam algorytmu sortowania dla tablic int, który nie przydziela żadnych bajtów innych niż rozmiar tablicy i jest ograniczony do dwóch instrukcji: SWAP: zamień następny indeks na bieżący; MOVE: przesuwa kursor do indeksu +1 lub -1; Oznacza to, że nie można zamieniać niesąsiadujących indeksów...
Rozważ następujący problem: Dane wejściowe: dwie tablice i o długości , gdzie jest posortowane.B n BAAABBBnnnBBB Pytanie: czy i zawierają te same elementy (z ich wielokrotnością)?B.AAABBB Jaki jest najszybszy algorytm deterministyczny dla tego problemu? Czy można to rozwiązać szybciej niż ich...
Jak mogę posortować listę 5 liczb całkowitych tak, że w najgorszym przypadku potrzeba 7 porównań? Nie obchodzi mnie, ile innych operacji zostanie wykonanych. Nie wiem nic szczególnego o liczbach całkowitych. Wypróbowałem kilka różnych metod dzielenia i podbijania, które obniżają mnie do 8...
W książce algorytmy randomizowane , Motwani i Raghavan otworzyć zapoznaniu się z opisem ich funkcji RandQS - randomizowane Quicksort - przy czym czop, służy do podziału zbioru na dwie części, jest wybierana losowo. Przez jakiś czas dręczyłem nad tym (co prawda trochę słabe) mózgi, ale nie byłem w...
Randomized Quick Sort to rozszerzenie szybkiego sortowania, w którym element przestawny jest wybierany losowo. Jaka może być najgorsza złożoność tego algorytmu. Według mnie powinno to być O ( n2))O(n2)O(n^2) , ponieważ najgorszy przypadek ma miejsce, gdy losowo wybrany element przestawny jest...