m |
|||
| (4 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
==Description== | ==Description== | ||
| − | Insertion sort is an [[algorithm]] that orders a list of elements. | + | Insertion sort is an [[in place algorithm]] that orders a list of elements. |
==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> | ||
| Line 33: | Line 33: | ||
==LISP implementation== | ==LISP implementation== | ||
| − | < | + | <source lang="lisp"> |
;Stephen Rudolph | ;Stephen Rudolph | ||
;1/12/09 | ;1/12/09 | ||
| Line 71: | Line 71: | ||
(defun insertion-sort(l) | (defun insertion-sort(l) | ||
(insertion-sort-loop l 1)) | (insertion-sort-loop l 1)) | ||
| − | </ | + | </source> |
[[Category:ECE608]] | [[Category:ECE608]] | ||
[[Category:Sorting algorithms]] | [[Category:Sorting algorithms]] | ||
Latest revision as of 12:01, 14 January 2009
Description
Insertion sort is an in place 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))
