Three Quadratic Sorts

October 27, 2009

Since we will be sorting arrays in-place, and since Scheme has awkward syntax for imperative operations on vectors, we will use Awk to implement our sorting algorithms. By choosing Awk, we continue in the fine tradition of Chapter 7 of The Awk Programming Language by Alfred V. Aho, Brian W. Kernighan and Peter J. Weinberger and several of the Columns in Jon L. Bentley’s books Programming Pearls and More Programming Pearls.

We begin with the test program, which sorts arrays of identical, sorted, reversed and random integers for all sizes of array from 0 to 20, and also for an array of size 1000, to give an idea of the efficiency of the sort:

BEGIN { for (i=0; i<=20; i++) tester(i) tester(1000) }

function tester(i) { genid(x,i); sort(x,i); check(x,i); clear(x) gensort(x,i); sort(x,i); check(x,i); clear(x) genrev(x,i); sort(x,i); check(x,i); clear(x) genrand(x,i); sort(x,i); check(x,i); clear(x) }

function genid(x,n, i) { for (i=1; i<=n; i++) x[i] = 1 }

function gensort(x,n, i) { for (i=1; i<=n; i++) x[i] = i }

function genrev(x,n, i) { for (i=1; i<=n; i++) x[i] = n + 1 - i }

function genrand(x,n, i) { for (i=1; i<=n; i++) x[i] = int(n * rand()) }

function check(x,n, i) { for (i=1; i<n; i++) if (x[i+1]+0 < x[i]+0) { printf "error in sort" exit } }

function clear(x, i) { for (i in x) delete x[i] }

Our first sorting algorithm is bubble sort; we use a do/while loop so that the body is executed at least once:

function sort(A,n, i,switched,t) { do { switched = 0 for (i=2; i<=n; i++) if (A[i] < A[i-1]) { t = A[i-1]; A[i-1] = A[i]; A[i] = t switched = 1 } } while (switched) }

I can remember learning bubble sort over thirty years ago in my first programming class, in Fortran. I remember being amazed. Now, I am equally amazed by bubble sort, though for rather different reasons. Here is selection sort:

function sort(A,n, i,j,min,t) { for (i=1; i<=n; i++) { min = i for (j=i+1; j<=n; j++) if (A[j] < A[min]) min = j t = A[min]; A[min] = A[i]; A[i] = t } }

And here is insertion sort; we split the swap into pieces, and move the invariant parts of the swap out of the inner loop, which makes the function much faster:

function sort(A,n, i,j,t) { for (i=2; i<=n; i++) { t = A[i] for (j=i; j>1 && t < A[j-1]; j--) A[j] = A[j-1] A[j] = t } }

All three of these sorts have time-complexity O(n²). Of the three, bubble sort is generally the worst, and insertion sort is generally the best. Insertion sort is stable, meaning that equal elements will appear in the output in the same order as the input, which is sometimes important; insertion sort also has the property that if the input is nearly sorted, it runs very quickly, even more quickly than some more sophisticated sorting algorithms.

The code is collected at http://programmingpraxis.codepad.org/vuYNXRdL, though you can’t run it, because codepad doesn’t provide an Awk interpreter.

Posted by programmingpraxis

Filed in Exercises

4 Comments »

4 Responses to “Three Quadratic Sorts”

Michel S. said

October 27, 2009 at 10:48 PM

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))))

Dharkael said

October 28, 2009 at 10:37 PM

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)

Jebb said

August 13, 2010 at 4:37 PM

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] = buffer

and 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;
}

Vikas Tandi said

April 27, 2011 at 8:17 AM

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);
	}
}

S	M	T	W	T	F	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Programming Praxis