Jakiego algorytmu używa sort?

24

Muszę dodać jedną liczbę całkowitą do listy, która jest już posortowana, tak aby trafiła we właściwe miejsce. Moja pierwsza myśl była podobna

(sort (cons newelt list) #'<)

Jednak biorąc pod uwagę, że listjest już posortowane, naprawdę potrzebne jest tylko jedno wstawienie, co oznacza, że ​​to rozwiązanie może być strasznie nieodpowiednie w zależności od używanego algorytmu sort.

Więc jakiego algorytmu sortużywa?

Czy lepiej byłoby zrobić coś takiego?

(let ((tail list))
  ;; The first element is never less-than
  (while (and tail (< newelt (cadr tail)))
    (setq tail (cdr tail)))
  (setcdr tail (cons newelt (cdr tail)))
  list)
elisp performance emacs-internals Malabarba
źródło
1
Użyłbym binarnej sterty (np. Heap.el ), jeśli byłaby to częsta operacja w moim kodzie.
lunaryorn,
Pozwolić Bbyć początkowa już posortowane listi Ai Cpoczątkowo pustych list. Podziel Bna dwie części B1, B2o długości mi mlub m+1i m, i porównaj neweltz pierwszym elementem B2. Jeśli neweltznaczy ≥przedłużyć Ajego prawej z B1i wymienić Bz B2, jeszcze przedłużyć Cjego lewej B2i wymienić Bz B1. Po O(log n)takich krokach nic nie zostaje B. Następnie Azawiera rzeczy ≤ newelti Cte > newelt, a konkatenacja tworzy rozszerzoną posortowaną listę. Przepraszamy za niezbyt e-lisppodobny język.
jfbu

Odpowiedzi:

26

Jeśli masz kod źródłowy Emacs zainstalowany, można znaleźć kod źródłowy sortz M-x find-function.

Tam możesz zobaczyć, że sortwykonuje sortowanie scalające. Sprawdza długość listy, dzieli listę na pół, sortuje części „przednią” i „tylną” osobno poprzez rekurencję, a następnie łączy je.

Jeśli chodzi o to, czy Twoja implementacja będzie szybsza - zmierz to! Teoretycznie jest bardziej wydajny (O (n) vs O (n log n)), ale sortma tę zaletę, że jest napisany w C, więc wynik może pójść w obie strony. (Oczywiście nie zapomnij skompilować bajtów swojej funkcji.)

legoscia
źródło
@Malabarba Dla przypomnienia, na jakiej długości testowałeś go?
T. Verron,
8
Przetestowano 1000 razy wstawiając liczbę losową na listę 1000 liczb losowych (wszystkie wstępnie wygenerowane). Metoda ręczna była 6 razy szybsza.
Malabarba