Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
simple implementation
efficient for (quite) small data sets
efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
more efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort: the average running time is n2/4, and the running time is linear in the best case
stable (i.e., does not change the relative order of elements with equal keys)
in-place (i.e., only requires a constant amount O(1) of additional memory space)
online (i.e., can sort a list as it receives it)
Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.
http://en.wikipedia.org/wiki/Heapsort
No comments:
Post a Comment