Pytania otagowane jako sorting

algorytmiczny problem porządkowania zbioru elementów w odniesieniu do jakiejś relacji porządkowania.

3
Praktyczne zastosowania Radix Sort
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 …
3
Deterministyczny algorytm czasu liniowego do sprawdzania, czy jedna tablica jest posortowaną wersją drugiej
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 sortowanie? Czy ten problem można rozwiązać w deterministycznym czasie …
2
Sortuj tablicę 5 liczb całkowitych z maksymalnie 7 porównaniami
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 porównań, takich jak stosowanie podejścia scalesort lub łączenie …
4
Dlaczego Randomized Quicksort ma O (n log n) najgorszy koszt czasu wykonania
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 wybierany w sortowanej lub odwrotnej kolejności. Ale w niektórych …
2
Jakie są zalety Randomized Quicksort?
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 stanie zobaczyć, …
4
Dlaczego nie używamy szybkiego sortowania na połączonej liście?
Algorytm szybkiego sortowania można podzielić na następujące kroki Zidentyfikuj oś przestawną. Podziel listę połączoną na partycje na podstawie przestawnej. Podziel listę połączoną rekurencyjnie na 2 części. Teraz, jeśli zawsze wybieram ostatni element jako oś przestawną, wówczas identyfikacja elementu przestawnego (1. krok) zajmuje czas.O ( n )O(n)\mathcal O(n) Po zidentyfikowaniu elementu …
4
Quicksort wyjaśnił dzieciom
W ubiegłym roku czytałem fantastyczny artykuł na temat „Mechaniki kwantowej dla przedszkola” . To nie był łatwy papier. Zastanawiam się teraz, jak wytłumaczyć quicksort w najprostszych możliwych słowach. Jak mogę udowodnić (lub przynajmniej falę ręczną), że średnia złożoność wynosi i jakie są najlepsze i najgorsze przypadki dla klasy przedszkolnej? A …
2
Skuteczne wstawianie do listy przy minimalnej liczbie inwersji
Załóżmy dwie listy porównywalnych pozycji: u i s. Niech INV (u) będzie liczbą inwersji wu. Szukam wydajnego algorytmu do wstawiania elementów s do u przy minimalnym wzroście INV (u). Zasadniczo chciałbym wstawić obiekty do listy, zachowując ją „tak posortowaną, jak to możliwe”, zachowując kolejność pierwszej listy. Przykład: u = [4,6,2,9,7] …
1
Czy można zweryfikować sortowanie listy bez porównywania sąsiadów?
punkt A lista może być zweryfikowany jako klasyfikowane porównując każdy element do swojego sąsiada. W mojej aplikacji nie będę w stanie porównać każdego elementu z jego sąsiadem: zamiast tego porównania będą czasami dokonywane między odległymi elementami. Biorąc pod uwagę, że lista zawiera więcej niż trzy elementy, a także porównanie jest …
14 sorting 
4
Czy wymagana jest przechodnie algorytm sortowania
Czy można zastosować algorytm sortowania z nieprzechodnim porównaniem, a jeśli tak, dlaczego wymienność przechodni jest wymieniona jako wymóg dla sortujących komparatorów? Tło: Algorytm sortowania ogólnie sortuje elementy listy według funkcji komparatora C (x, y), przy pomocy C(x,y)=⎧⎩⎨−10+1if x≺yif x∼ygdyby x≻yC(x,y)={−1if x≺y0if x∼y+1gdyby x≻y\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\prec …
1
Ciekawy problem z sortowaniem
Biorąc pod uwagę tubę z ponumerowanymi kulkami (losowa). Rurka ma otwory do usuwania kulki. Rozważ następujące kroki dla jednej operacji: Możesz wybrać jedną lub więcej piłek z dołków i zapamiętać kolejność, w jakiej je wybrałeś. Musisz przechylić rurę w lewą stronę, aby pozostałe kulki w rurze przesunęły się w lewo …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.