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)
1
Użyłbym binarnej sterty (np. Heap.el ), jeśli byłaby to częsta operacja w moim kodzie.
—
lunaryorn,
Pozwolić
—
jfbu
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.