Three Quadratic Sorts
October 27, 2009
Sorting is one of the most common computing tasks. In the days of large mainframes, sorting would often account for ten percent of a computer’s workload, and there were complicated procedures involving large free-standing tape machines for sorting more records than could fit in the computer’s memory; the programmer who could shave a few percentage points of time or core memory space off the standard system sort was a hero. Nowadays, most programmers simply call their local sort library, and never worry about how it works.
We are going to explore classical sorting algorithms in the next several exercises. The rules of the game: We will be sorting arrays of integers with elements stored in locations zero through n−1, where n is the number of elements in the array. We will always sort into ascending order, and will use <, never ≤, to compare array elements. All sorting functions will be called with two parameters, the name of the array and its length.
Today, we will look at three simple sorting algorithms. Bubble sort works by repeatedly stepping through the array to be sorted, comparing each pair of adjacent elements and interchanging them if they are in the wrong order, until the array is sorted. Selection sort works by repeatedly passing through the array, at each pass finding the minimum element of the array, interchanging it with the first element of the array, then repeating on the sub-array that excludes the first element of the array. Insertion sort works the same way that card players generally sort their hands; starting from an empty hand, they pick up a card, insert it into the correct position, then repeat with each new card until no cards remain.
Your task is to write functions that sort an array using bubble sort, selection sort, and insertion sort; you should also write a test program that can be used for any of the sorting algorithms. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Clojure solution. Bubble and selection sorts are implemented over Java ArrayLists, as they really make no sense to implement in a functional manner. I’ve generalized from the requirement and allow any ordered datatype to be sorted, either using the built-in compare or using a supplied custom comparator.
The insertion sort is done functionally, and can sort over anything Clojure can turn into a sequence (any Clojure collection, ArrayLists, etc.). So as not to clutter the code further, in this case I chose to use numbers only, allowing the use of Clojure’s built-in min function.
(import 'java.util.ArrayList) (defn arr-swap! [#^ArrayList arr i j] (let [t (.get arr i)] (doto arr (.set i (.get arr j)) (.set j t)))) (defn bubble-sort! ([arr] (bubble-sort! compare arr)) ([cmp #^ArrayList arr] (letfn [(sorter [stop-i] (let [changed (atom false)] (doseq [i (range stop-i)] (if (> (cmp (.get arr i) (.get arr (inc i))) 0) (do (arr-swap! arr i (inc i)) (reset! changed true)))) @changed))] (doseq [stop-i (range (dec (.size a)) -1 -1) :while (sorter stop-i)]) arr))) (defn sel-sort! ([arr] (sel-sort! compare arr)) ([cmp #^ArrayList arr] (let [n (.size arr)] (letfn [(move-min! [start-i] (loop [i start-i] (when (< i n) (when (< (cmp (.get arr i) (.get arr start-i)) 0) (arr-swap! arr start-i i)) (recur (inc i)))))] (doseq [start-i (range (dec n))] (move-min! start-i)) arr)))) (defn ins-sort [xs] (letfn [(remove-first [x xs] (if (= x (first xs)) (next xs) (cons (first xs) (remove-first x (next xs))))) (sorter [xs] (if (or (empty? xs) (empty? (next xs))) xs (let [x (apply min xs) xs1 (remove-first x xs)] (cons x (sorter xs1)))))] (sorter (seq xs))))I’m just learning to think in a functional language so this code is probably not as neat or efficient as it could be.
The functions are called with any of Clojure’s sequence data types, b-sort! and sel-sort! return sorted vectors and in-sort!
returns a sorted Lazy sequence.
By using compare we can also sort sequences containing nil items
Here goes..
(defn in-sort! [data] (letfn [(insert ([raw x](insert [] raw x)) ([sorted [y & ys :as raw] x] (if (empty? raw) (conj sorted x) (if (neg? (compare x y )) (concat sorted [x,y] ys ) (recur (conj sorted y) ys x )))))] (reduce insert [] data))) (defn sel-sort! [coll] (let [len (count coll)] (letfn [(min-index [coll start] (if (= start len) start (reduce #(if (neg? (compare (nth coll %1) (nth coll %2))) %1 %2) (range start len)))) (vswap! [a-vec x y] (assoc a-vec x (nth a-vec y) y (nth a-vec x)))] (loop [cur 0 data (vec coll) min (min-index data cur)] (if (>= cur len) data (let [data (vswap! data min cur) cur (inc cur)] (recur cur data (min-index data cur)))))))) (defn b-sort! [coll] (let [cnt (dec (count coll)) swap (fn [n m data] (assoc data n (nth data m) m (nth data n)))] (loop [changed false, n 0,data (vec coll)] (cond (>= n cnt) (if changed (recur false 0 data) data) (neg? (compare (nth data n) (nth data (inc n)))) (recur changed (inc n) data) :else (recur true (inc n) (swap n (inc n) data)))))) (def data '(6 8 5 9 3 2 1 4 7)) (println "b-sort!:" (b-sort! data)) (println "sel-sort!:" (sel-sort! data)) (println "in-sort!:" (in-sort! data)) ;Should print ;b-sort!: [1 2 3 4 5 6 7 8 9] ;sel-sort!: [1 2 3 4 5 6 7 8 9] ;in-sort!: (1 2 3 4 5 6 7 8 9)I’ve done the C versions a long time ago, and I just revisited this exercise while teaching myself python. Thought I’d post these here.
def bsort(tab): for i in range(len(tab) - 1): for j in range(i + 1, len(tab)): if tab[j] < tab[i]: tab[i], tab[j] = tab[j], tab[i] def ssort(tab): for i in range(len(tab) - 1): min = tab[i] indexmin = i for j in range(i + 1, len(tab)): if tab[j] < min: min = tab[j] indexmin = j if indexmin != i: tab[i], tab[indexmin] = tab[indexmin], tab[i] def isort(tab): for i in range(1, len(tab)): buffer = tab[i] j = i - 1 while j >= 0 and tab[j] > buffer: tab[j + 1] = tab[j] j -= 1 tab[j + 1] = bufferand the C versions:
int insert_sort(int *tab, int l) { int *ip, *jp; int value; printf("insert sorting!\n"); for (ip = tab + 1; ip < tab + l; ip++) { value = *ip; jp = ip - 1; while((jp >= tab) && (value < *jp)) { *(jp + 1) = *jp; --jp; } *(jp + 1) = value; } return 0; } int bubble_sort(int *tab, int l) { int *ip, *jp; printf("bubble sorting!\n"); for (jp = tab + l - 2; jp >= tab; jp--) { for (ip = tab; ip <= jp; ip++) { if (*ip > *(ip + 1)) swap (ip, ip + 1); } } return 0; } int select_sort(int *tab, int l) { int *ip, *jp; int min; printf("select sorting!\n"); for (jp = tab; jp < tab + l - 1; jp++) { min = *jp; for (ip = jp + 1; ip < tab + l; ip++) if (*ip < min) swap(ip, &min); *jp = min; } return 0; }My c version
void straight_insertion_sort(int arr[], int left, int right) { int i; /* move smallest key to left end */ for(i = left+1; i <= right; i++) if(arr[0] > arr[i]) swap(arr, 0, i); for(i = left+1; i <= right; i++) { int j, key; for(j = i-1, key = arr[i]; arr[j] > key; j--) arr[j+1] = arr[j]; arr[j+1] = key; } } void bubble_sort(int arr[], int left, int right) { int i, j; for(i = right; i > left; i--) { for(j = left; j < i; j++) if(arr[j] > arr[j+1]) swap(arr, j, j+1); } } void straight_selection_sort(int arr[], int left, int right) { int i, j, min; for(i = left; i < right; i++) { min = i; for(j = i+1; j <= right; j++) { if(arr[j] < arr[min]) min = j; } swap(arr, i, min); } }