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 list
jest 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 sort
uż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)
B
być początkowa już posortowane list
i A
i C
początkowo pustych list. Podziel B
na dwie części B1
, B2
o długości m
i m
lub m+1
i m
, i porównaj newelt
z pierwszym elementem B2
. Jeśli newelt
znaczy ≥
przedłużyć A
jego prawej z B1
i wymienić B
z B2
, jeszcze przedłużyć C
jego lewej B2
i wymienić B
z B1
. Po O(log n)
takich krokach nic nie zostaje B
. Następnie A
zawiera rzeczy ≤ newelt
i C
te > newelt
, a konkatenacja tworzy rozszerzoną posortowaną listę. Przepraszamy za niezbyt e-lisp
podobny język.