- It performs sorting by repeatly putting the largest element in the unprocessed portion of the array to the end of the this unprocessed portion until the whole array is sorted.
- Is an easy-to-program, but very inefficient sorting algorithm.
Algorithm
- 1st iteration selects the smallest element in the array, and swaps it with the first element.
- 2nd iteration selects the 2nd smallest element (which is the smallest element of the remaining elements) and swaps it with the 2nd element.
- The algorithm continues until the last iteration selects the 2nd largest element and swaps it with the 2nd last index, leaving the largest element in the last index.
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
- Adaptive, i.e. 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 best case (nearly sorted input) is O(n)
- 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.
Source: Wikipedia, the free encyclopedia
Here are some links to follow to know more about insertion sort:
Algorithm
- Iterates thru every element of the array, starting with the first 2 elements.
- If left element is bigger than right element, swap them.
- Repeat step #1 and #2 until there are no more swaps.
Shell sort
The idea of Shell sort is the following:
- arrange the data sequence in a two-dimensional array
- sort the columns of the array
The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column. In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the presortedness of the sequence obtained in the preceding steps.
Example: Let 3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2 be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right):
|
|
|
Data elements 8 and 9 have now already come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted:
|
|
|
Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6, an 8 and a 9 that have to move a little bit to their correct position.
This are some links to know more about shell sort:
http://en.wikipedia.org/wiki/Shell_sort
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm
http://goanna.cs.rmit.edu.au/~stbird/Tutorials/ShellSort.html
