m |
m |
||
| Line 5: | Line 5: | ||
==Performance== | ==Performance== | ||
| − | <table class="wikitable" | + | <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))
