Welchen Algorithmus verwendet die Sortierung?

24

Ich muss einer Liste, die bereits sortiert ist, eine einzelne Ganzzahl hinzufügen, damit sie an der richtigen Stelle abgelegt wird. Mein erster Unterricht war so etwas wie

(sort (cons newelt list) #'<)

Da dies listjedoch bereits sortiert ist, wird nur eine Einfügung wirklich benötigt, was bedeutet, dass diese Lösung je nach dem von verwendeten Algorithmus fürchterlich ungeeignet sein kann sort.

Welcher Algorithmus wird sortverwendet?

Wäre ich besser dran, wenn ich Folgendes täte?

(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
quelle
1
Ich würde einen binären Heap (z. B. heap.el ) verwenden, wenn dies in meinem Code häufig vorkommt.
Lunaryorn
Lassen Sie Binitial sein bereits sortiert listund Aund Czunächst leere Listen. Split Bin zwei Teile B1, B2von Längen mund moder m+1und m, zu vergleichen , neweltum erste Element B2. Wenn neweltheißt ≥verlängern Amit seiner rechten B1und ersetzen Bmit B2, sonst zu verlängern , Cum seine linke mit B2und ersetzen Bmit B1. Nach O(log n)solchen Schritten ist nichts mehr drin B. Dann Aenthält die Dinge ≤ newelt, und Cdiejenigen > newelt, und Verkettung erzeugt die erweiterte sortierte Liste. Entschuldigung für nicht sehr e-lispähnliche Sprache.
jfbu

Antworten:

26

Wenn Sie den Emacs-Quellcode installiert haben, können Sie den Quellcode für sortmit finden M-x find-function.

Dort können Sie sehen, dass sorteine Zusammenführungssortierung durchgeführt wird. Es überprüft die Länge der Liste, zerlegt die Liste in zwei Hälften, sortiert die "vorderen" und "hinteren" Teile durch Rekursion getrennt und führt dann die beiden zusammen.

Ob Ihre Implementierung schneller wäre - messen Sie es! Es ist theoretisch effizienter (O (n) vs O (n log n)), sorthat jedoch den Vorteil, dass es in C geschrieben wird, sodass das Ergebnis in beide Richtungen gehen kann. (Vergessen Sie natürlich nicht, Ihre Funktion byteweise zu kompilieren.)

Legoscia
quelle
@Malabarba An welcher Längenskala haben Sie es getestet?
T. Verron
8
1000-mal getestet, indem eine Zufallszahl in eine Liste von 1000 Zufallszahlen eingefügt wurde (alle vorgeneriert). Die manuelle Methode war 6-mal schneller.
Malabarba