Bubblesort

Från Unix.se, den fria unixresursen.

Innehåll

1 Förklaring av algoritmen 2 Implementationer 2.1 Prolog 2.2 Common Lisp 2.3 O'Caml 2.4 C++

Förklaring av algoritmen

Bubbelsortering är som namnet antyder en sorteringsalgoritm (och en mycket ineffektiv sådan). Algoritmen går ut på att man jämför två värden i taget och flyttar om dem så att deras inbördes ordning stämmer. Därefter går man igenom hela listan upprepade gånger, så att elementen liksom "bubblar" upp till sina rätta platser.

Implementationer

Prolog

bubblesort(O,S) :- append(X,[A,B|Y],O),
  A > B,
  append(X,[B,A|Y],N),
  bubblesort(N,S).
bubblesort(L,L).

Common Lisp

(defun bubble-sort (list)
  (loop for swapped = nil doing
        (loop for pair on list
              when (and (rest pair) (> (first pair) (second pair))) do
              (rotatef (first pair) (second pair))
              (setf swapped t))
        while swapped
        finally (return list)))

O'Caml

let bubble l =
  let rec foo = function
      [] -> []
    | (x :: []) as l -> l
    | (x :: y :: l) ->
        if x > y then x :: bubble (y :: l)
        else y :: bubble (x :: l)
  in
  let rec loop f l = let l2 = f l in if l = l2 then l else loop f l2 in
  loop foo l
;;

Den här varianten är svansrekursiv, vilket innebär att O'Caml internt kan optimera bort de multipla funktionsanropen som rekursiviteten medför.

C++

template<class Iterator>
void bubblesort(Iterator begin, Iterator end) {
  bool changed;
  do {
    changed = false;
    Iterator i = begin();
    
    while(i < end) {
      Iterator next = i+1;
      if(*i > *next) {
        std::swap(*i, *next);
        changed = true;
      i = next;
    }
    
  } while(changed);
}