m
m
Line 5: Line 5:
  
 
==Performance==
 
==Performance==
<table class="wikitable" cellpadding="2px">
+
<table class="wikitable" style="border-spacing: 0px">
 
<tr bgcolor="#ddd">
 
<tr bgcolor="#ddd">
     <th width="33%">Best</th>
+
     <th width="33%" align="center" style="border: solid 1px">Best</th>
     <th width="33%">Average</th>
+
     <th width="33%" align="center" style="border: solid 1px">Average</th>
     <th width="33%">Worst</th>
+
     <th width="33%" align="center" style="border: solid 1px">Worst</th>
 
</tr>
 
</tr>
 
<tr>
 
<tr>
     <td align="center"><math>O(n)</math></td>
+
     <td align="center" style="border: solid 1px"><math>O(n)</math></td>
     <td align="center"><math>O(n^2)</math></td>
+
     <td align="center" style="border: solid 1px"><math>O(n^2)</math></td>
     <td align="center"><math>O(n^2)</math></td>
+
     <td align="center" style="border: solid 1px"><math>O(n^2)</math></td>
 
</tr>
 
</tr>
 
</table>
 
</table>

Revision as of 08:59, 13 January 2009


Description

Insertion sort is an algorithm that orders a list of elements.

Performance

Best Average Worst
$ O(n) $ $ O(n^2) $ $ O(n^2) $

Example

6 10 8 5 1 7

6 10 8 5 1 7

6 8 10 5 1 7

5 6 8 10 1 7

1 5 6 8 10 7

1 5 6 7 8 10

LISP implementation

;Stephen Rudolph
;1/12/09
;Insertion-Sort
 
;;Return a list without the nth item in l
(defun remove-nth(n l)
	(if (> (- n 1) (length l))
		l
		(if (= n 0)
			(cdr l)
			(cons (car l) (remove-nth (- n 1) (cdr l))))))
 
;;Return a list with x inserted after the nth element in l
(defun insert-after-nth(x n l)
	(if (>= n (length l))
		(append l (list x))
		(if (= n -1)
			(cons x l)
			(cons (car l) (insert-after-nth x (- n 1) (cdr l))))))
 
;;Loop through all indices (match-index) less than key-index and sort the element at key-index
(defun insertion-sort-body(l key-index match-index)
	(if (= match-index -1)
		(cons (nth key-index l) (remove-nth key-index l))
		(if (< (nth key-index l) (nth match-index l))
			(insertion-sort-body l key-index (- match-index 1))
			(insert-after-nth (nth key-index l) match-index (remove-nth key-index l)))))
 
;;Sort the first key-index items in l
(defun insertion-sort-loop(l key-index)
	(if (= key-index (length l))
		l
		(insertion-sort-loop (insertion-sort-body l key-index (- key-index 1)) (+ key-index 1))))
 
;;Sort list l with the insertion sort algorithm
(defun insertion-sort(l)
	(insertion-sort-loop l 1))

Alumni Liaison

Recent Math PhD now doing a post-doctorate at UC Riverside.

Kuei-Nuan Lin