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 =...
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...
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...
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...
Załóżmy, że odczytujemy ciąg nnn liczb, jeden po drugim. Jak znaleźć kkk najmniejszy element za pomocą pamięci komórkowej O(k)O(k)O(k) oraz w czasie liniowym ( O(n)O(n)O(n) ). Myślę, że powinniśmy zapisać pierwsze kkk wyrażeń w sekwencji, a kiedy otrzymamy k+1k+1k+1 -ty termin, usuń go, który z...
Ten dowód jest dowodem indukcyjnym i wygląda następująco: P (n) jest twierdzeniem, że „Quicksort poprawnie sortuje każdą tablicę wejściową o długości n”. Przypadek podstawowy: każda tablica wejściowa o długości 1 jest już posortowana (blokada P (1)) Krok indukcyjny: fix n => 2. Napraw...