¿Qué algoritmo utiliza el ordenamiento?

24

Necesito agregar un solo entero a una lista que ya está ordenada, de modo que vaya en el lugar correcto. Mi primer pensamiento fue algo como

(sort (cons newelt list) #'<)

Sin embargo, dado que listya está ordenado, solo se necesita una inserción, lo que significa que esta solución podría ser terriblemente inadecuada dependiendo del algoritmo utilizado sort.

Entonces, ¿ cuál es el algoritmo que sortusa?

¿Sería mejor hacer algo como lo siguiente?

(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
fuente
1
Usaría un montón binario (por ejemplo, heap.el ), si esa fuera una operación frecuente en mi código.
lunaryorn
Vamos a Bser ordenados inicial ya liste Ay Clistas inicialmente vacías. Dividir Ben dos partes B1, B2de longitudes my mo m+1y m, comparar neweltcon el primer elemento de B2. Si neweltse ≥extiende Aa la derecha con B1y reemplaza Bcon B2, de lo contrario, se extiende Ca la izquierda con B2y reemplaza Bcon B1. Después de O(log n)tales pasos no queda nada adentro B. Luego Acontiene las cosas ≤ newelt, y Cesas > newelt, y la concatenación produce la lista ordenada extendida. Disculpas por el e-lisplenguaje no muy parecido.
jfbu

Respuestas:

26

Si tiene instalado el código fuente de Emacs, puede encontrar el código fuente sortcon M-x find-function.

Allí puede ver que sortrealiza una ordenación por fusión. Comprueba la longitud de la lista, la divide por la mitad, clasifica las partes "frontal" y "posterior" por separado a través de la recursión, y luego combina las dos.

En cuanto a si su implementación sería más rápida, ¡mídala! Es más eficiente en teoría (O (n) frente a O (n log n)), pero sorttiene la ventaja de estar escrito en C, por lo que el resultado podría ser de cualquier manera. (Por supuesto, no olvide compilar en bytes su función).

legoscia
fuente
@Malabarba Para el registro, ¿en qué escala de longitudes lo probó?
T. Verron
8
Probado 1000 veces insertando un número aleatorio en una lista de 1000 números aleatorios (todos pregenerados). El método manual fue 6 veces más rápido.
Malabarba