Sortowanie

W poprzednim wpisie rozwiązywałem zadanie 1.3 z Wizard Booka. Polegało ono na napisaniu funkcji o trzech argumentach, która zwraca sumę kwadratów dwóch większych z nich. Zastanawiałem się również nad zadaniem uogólnionym, tzn. o funkcji przyjmującą dowolną ilość argumentów, która zwraca sumę kwadratów n największych z nich. Nie potrafiłem jednak wówczas wyobrazić sobie implementacji sortowania listy. Okazało się jednak, że znowu nie myślałem rekurencyjnie.

Przyjąłem bowiem, że jeżeli mam zaimplementować sortowanie, to powinienem zacząć od jednej z prostszych metod, jak np. sortowanie bąbelkowe (ang. bubble sort). Mimo usilnych prób nie potrafiłem jednak stworzyć niczego, co byłoby przejrzyste i proste. Zagnieżdżone iteracje, indeksowanie tablic i zamiana elementów - elementy idealnie pasujące do programowania imperatywnego w świecie zamkniętych nawiasów wyglądają co najmniej dziwnie.

Wreszcie dzisiaj, w trakcie podróży pociągiem, przypomniałem sobie o rekurencyjnych metodach sortowania. W przeciągu godziny na stronach notesu udało mi się zapisać w Scheme implementację algorytmu sortowania przez scalanie (ang. merge sort). Do szczęścia potrzebne były mi w zasadzie dwie rzeczy. Pierwsza to łączenie dwóch posortowanych list w jedną posortowaną. Implementacja okazała się całkiem prosta. Przede wszystkim, jeżeli któraś z list jest pusta, to wynik równy jest drugiej liście. W przeciwnym wypadku budujemy nową listę. Na jej szczyt wkładamy mniejszy z pierwszych elementów obu list, a resztę budujemy rekurencyjnie wywołując siebie. Lista, z której zdjęto pierwszy element zostaje oczywiście go w tym wywołaniu pozbawiona.

(define (merge L1 L2)
(cond ((null? L1) L2)
((null? L2) L1)
((< (car L1) (car L2)) (cons (car L1)
(merge L2
(cdr L1))))
(else (cons (car L2)
(merge L1
(cdr L2))))))

Operator cons tworzy parę z dwóch zadanych obiektów. Jego zagnieżdżone wywołania mogą służyć do tworzenia list. Np. lista (1 2 3) może być skonstruowana za pomocą wywołania (cons 1 (cons 2 (cons 3 ()))).

Należy się też słowo sprostowania. Ostatnim razem do sprawdzania, czy lista jest pusta zdefiniowałem własną funkcję empty?. Dzisiaj w otchłaniach dokumentacji dowiedziałem się o funkcji null?, która robi dokładnie to samo.

Poprawność działania funkcji merge możemy łatwo sprawdzić.

(merge '(1 2 3 4 5) '(2 4 6))
(1 2 2 3 4 4 5 6)

Przy pomocy apostrofu w zapisie '(1 2 3 4 5) informujemy interpreter, by nie wykonywał następującej po nim kombinacji. W tym przypadku jest to zwięźlejszy sposób na zapisanie (list 1 2 3 4).

Drugą rzeczą kluczową przy implementacji merge sort jest podział listy na dwie części. To zadanie uogólniłem do funkcji zwracającej dowolny kawałek listy zawarty pomiędzy zadanymi indeksami (czyli coś na wzór pythonowej metody slice).

; (head L): zwroc liste bez ostatniego elementu
(define (head L)
(if (= (length L) 1)
()
(cons (car L)
(head (cdr L)))))

(define (slice L start end)
(if (= start 0)
(if (> end (- (length L) 1))
L
(slice (head L) start end))
(slice (cdr L) (- start 1) (- end 1))))

Przykładowo więc dla listy (7 11 13 17 19 23) użycie

(slice L 0 2)

zwróci (7 11) (czyli element pierwszy i drugi), zaś

(slice L 2 5)

zwróci (13 17 19) (elementy od trzeciego do szóstego).

Na podstawie tej funkcji z łatwością możemy już podzielić listę na dwie części.

(define (split L index)
(list (slice L 0 index)
(slice L index (length L))))

Funkcja split dzieli listę w miejscu wskazanym przez indeks i zwraca listę, której pierwszym elementem jest lewa część zadanej listy, a drugim elementem prawa część. W merge sort będziemy dzielić listę dokładnie w połowie, dlatego warto zdefiniować do tego oddzielną funkcję:

(define (split-half L)
(split L (quotient (length L) 2)))

Lewą i prawą część listy uzyskujemy więc w ten sposób:

(define (left-half L)
(car (split-half L)))

(define (right-half L)
(cadr (split-half L)))

(cadr L) jest skrótowym zapisem dla kombinacji (car (cdr L)).
I to już wszystko, co jest potrzebne do zapisania algorytmu merge sort.

(define (merge-sort L)
(if (< (length L) 2)
L
(merge (merge-sort (left-half L))
(merge-sort (right-half L)))))

Czy to nie było proste? ;-)

Ostateczne rozwiązanie uogólnionego zadania 1.3 wygląda więc następująco:

; (max L n): zwroc n najwiekszych elementow z listy L
(define (max L n)
(slice (reverse (merge-sort L)) 0 n))

(define (square x)
(* x x))

(define (sum-of-squares L)
(if (null? L)
0
(+ (square (car L))
(sum-of-squares (cdr L)))))

(define (fun L n)
(sum-of-squares (max L n)))

Komentuj wpis