Czy powinienem przetasować listę przed quicksort w OCaml? - ocaml

Zaleca się przetasowanie tablicy przed jej szybkim posortowaniem.

Jeśli jednak chcemy szybko posortować listę, najpierw zajmie się tasowanie listy O(nlogn), na przykład przypisujemy losowy klucz do każdego elementu na liście, a następnie scalamy listę (klucz, element).

Następnie moje pytanie jest:

Jeśli musimy wydać O(nlogn) najpierw przetasować listę, a jaki jest sens implementowania szybkiego sortowania dla listy w OCaml?

Powinniśmy po prostu użyć funkcji Fuzjort bezpośrednio, prawda?

Odpowiedzi:

W pytaniu OP:

Jeśli jednak chcemy szybko posortować listę, najpierw zmieni się tasowanie listy weź O (nlogn)

Myślę, że losowe tasowanie kosztuje tylko O(n) czas, jeśli najpierw przekonwertujesz listę na tablicę, a następnie użyjesz Tasuj Fisher-Yates, który jest również algorytmem używanym w losowym pliku shuffle Pythona.

Użyłbym scalesort, jak sugerujesz. Mergesort pasuje nawet do funkcjonalnego języka lepiej niż quicksort.