Jaką miarę zaburzeń należy zastosować podczas analizy Quicksort

Próbuję zrozumieć, dlaczego quicksort z użyciem partycji Lomuto i ustalonego elementu przestawnego działa nieprawidłowo, ale ogólnie słabo, na losowo generowanych danych wejściowych. Myślę, że chociaż dane wejściowe są generowane losowo, sekwencje mogą być uporządkowane, ale nie jestem pewien, jak zmierzyć poziom nieporządku w sekwencjach. Myślałem o użyciu liczby inwersji, ale na podstawie tego drugiego pytania zadałem , że nie jest to tak naprawdę dobry miernik w tym przypadku.

Powodem, dla którego podejrzewam, że moje losowe sekwencje mają dużo „porządku”, jest to, że losowe przestawianie rozwiązuje problem z wydajnością. Ale teoretycznie nie powinno być żadnego problemu z wydajnością tych rzekomo „losowych” sekwencji wejściowych.

Lomuto vs Hoare
Partycja Lomuto cierpi podczas sortowania równych kluczy, podczas gdy partycja Hoare nie.
Oba schematy podziału cierpią jednakowo, gdy stosuje się oś oddaloną od mediany.

Miara nieporządku
Miara nieporządku do wyboru na potrzeby szybkiego sortowania jest prosta.
Odp .: Jak daleko od mediany jest ustalony punkt obrotu w porównaniu do danych losowych?
Jeśli nalegasz na użycie partycji Lomuto i zakładasz, że dozwolone są zduplikowane wartości, musisz dodać następujący test na losowość:
B: Ile jest zduplikowanych elementów w porównaniu z losowym.

Oczywiście głupio jest zakładać, że duplikaty są dozwolone w twoim zestawie danych i nadal oceniać partycję Lomuto, więc prawdopodobnie powinieneś albo wcześniej wyeliminować duplikaty, albo przejść na partycję Hoare lub założyć, że duplikaty są rzadkie.

Oba miary są trywialne do oszacowania za pomocą statystyki.

Możemy wykluczyć dane patologiczne.
Wszelkie inne odchylenia od losowości nie będą miały znaczenia dla celów analizy szybkiego sortowania. Tak długo, jak oś jest blisko mediany, będzie dobrze działać na wszystkich danych, które nie są patologiczne.
Odległość od losowości musiałaby być naprawdę duża, aby mogła być patologicznie szybka, więc możemy to wykluczyć.

Nigdy nie używaj żadnych ustalonych elementów przestawnych w prawdziwym kodzie
Pamiętaj, że jeśli piszesz prawdziwy kod za pomocą ustalonego elementu przestawnego ^*) (cokolwiek to może być), narażasz się na atak typu „odmowa usługi”, ponieważ osoba atakująca może wstawić wartość patologiczna tylko w tym momencie, dlatego zawsze należy wybrać element losowy jako oś przestawną.

*) lub wiele osi przestawnych, jeśli wybierzesz najlepszą z x osi przestawnych.