[Home]Insertion sort

HomePage | Recent Changes | Preferences

Difference (from prior major revision) (author diff)

Changed: 1c1
Insertion sort is a sort algorithm very similar to bubble sort; the two even compare and exchange exactly the same pairs of elements, although in a different chronological order.
Insertion sort is a simple sort algorithm where the result is built up one entry at a time.

Changed: 3c3,11
The algorithm is as follows:
In abstract terms, each iteration of an insertion sort removes an element from the input data, inserting it into the correct sequence in the result, until no elements are left in the input.
The choice of which element to remove from the input is arbitrary.

The implementation of the result has the greatest impact on the time taken, so an ordered tree data structure with efficient inserts and in-order traversal will give good results. Specific implementations of insertion sort using these data structures may have their own names.

Straight insertion sort




Straight insertion sort is a very simple implementation of insertion sort.
Sorting is done in-place. The result array after n iterations is the first n entries of the input array, where the first remaining entry of the input is removed each time, and the result extends into the input when this entry is inserted:

Changed: 6c14,26
def insertionsort(array):
_____ result ______ ______ input ______
| < x | > x | x | ... |
</pre>
becomes:

________ result _______ ____ input ____
| < x | x | > x | ... |


The algorithm can be written as follows:

<pre>
def straightinsertionsort(array):

Added: 19a40
Straight insertion sort is very similar to bubble sort.

Changed: 22,24c43,45
Insertion sort (and bubble sort) take O(n2) time in the average, best, and worst cases, which makes them impractical for sorting large numbers of elements; however, their inner loops are very fast, which often makes them the fastest algorithms around for sorting small numbers of elements, typically less than 10 or so. Quicksort works by dividing the array to be sorted into smaller runs to be sorted separately; highly optimized implementations of Quicksort often use insertion or bubble sort to sort these runs once they get small enough.

More sophisticated versions of insertion sort can be smart enough to figure out how much of their data is already in order, and can therefore grow their sorted region by more than one item on each pass; these versions of insertion sort will finish in one pass if the whole array is already sorted.
In the best case of an already sorted array, this implementation of straight insertion sort takes O(n) time: each iteration, the first remaining element of the input is only compared with the last element of the result.
It takes O(n2) time in the average and worst cases, which makes it impractical for sorting large numbers of elements; however, the inner loop is very fast, which often makes it one of the fastest algorithms around for sorting small numbers of elements, typically less than 10 or so.
Quicksort works by dividing the array to be sorted into smaller runs to be sorted separately; highly optimized implementations of Quicksort often use insertion or bubble sort to sort these runs once they get small enough.

Added: 25a47
---

Removed: 27d48


Insertion sort is a simple sort algorithm where the result is built up one entry at a time.

In abstract terms, each iteration of an insertion sort removes an element from the input data, inserting it into the correct sequence in the result, until no elements are left in the input. The choice of which element to remove from the input is arbitrary.

The implementation of the result has the greatest impact on the time taken, so an ordered tree data structure with efficient inserts and in-order traversal will give good results. Specific implementations of insertion sort using these data structures may have their own names.

Straight insertion sort

Straight insertion sort is a very simple implementation of insertion sort. Sorting is done in-place. The result array after n iterations is the first n entries of the input array, where the first remaining entry of the input is removed each time, and the result extends into the input when this entry is inserted:

   _____ result ______ ______ input ______
  |   < x   |   > x   | x |      ...      |
becomes:
   ________ result _______ ____ input ____
  |   < x   | x |   > x   |      ...      |

The algorithm can be written as follows:

def straightinsertionsort(array):
    # Remove elements from start, extending result part of array.
    for removed_index in range(1, len(array)):
        removed_value = array[removed_index]
        # Search result part of array from top for index at which to insert.
        insert_index = removed_index
        while insert_index > 0 and array[insert_index - 1] > removed_value:
            # Move entry up to make room to insert value below.
            array[insert_index] = array[insert_index - 1]
            insert_index = insert_index - 1
        # Insert removed value at correct location in sorted result.
        array[insert_index] = removed_value

Straight insertion sort is very similar to bubble sort. In bubble sort, after N passes through the array, the N largest elements have bubbled to the top. (Or the N smallest elements have bubbled to the bottom, depending on which way you do it.) In insertion sort, after N passes through the array, you have a run of N sorted elements at the bottom of the array. Each pass inserts another element into the sorted run. So with bubble sort, each pass takes less time than the previous one, but with insertion sort, each pass takes more time than the previous one.

In the best case of an already sorted array, this implementation of straight insertion sort takes O(n) time: each iteration, the first remaining element of the input is only compared with the last element of the result. It takes O(n2) time in the average and worst cases, which makes it impractical for sorting large numbers of elements; however, the inner loop is very fast, which often makes it one of the fastest algorithms around for sorting small numbers of elements, typically less than 10 or so. Quicksort works by dividing the array to be sorted into smaller runs to be sorted separately; highly optimized implementations of Quicksort often use insertion or bubble sort to sort these runs once they get small enough.

--- /Talk


HomePage | Recent Changes | Preferences
This page is read-only | View other revisions
Last edited December 16, 2001 11:52 am by Carey Evans (diff)
Search: