- Algorithms Lesson 2: Insertion Sort
worst case: n^2
http://www.youtube.com/watch?v=c4BRHC7kTaQ&feature=fvwrel
- Insertion sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort
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)
Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain
When humans manually sort something (for example, a deck of playing cards), most use a method that is similar to insertion sort
for i ? 1 to i ? length(A)-1
{
// A[ i ] is added in the sorted sequence A[0, .. i-1]
// save A[i] to make a hole at index iHole
item ? A[i]
iHole ? i
// keep moving the hole to next smaller index until A[iHole - 1] is <= item
while iHole > 0 and A[iHole - 1] > item
{
// move hole to next smaller index
A[iHole] ? A[iHole - 1]
iHole ? iHole - 1
}
// put item in the hole
A[iHole] ? item
}
http://en.wikipedia.org/wiki/Insertion_sort
- The ideas of insertion
The main operation of the algorithm is insertion. The task is to insert a value into the sorted part of the array.
Java implementation
void insertionSort(int[] arr) {
int i, j, newValue;
for (i = 1; i < arr.length; i++) {
newValue = arr[i];
j = i;
while (j > 0 && arr[j - 1] > newValue) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = newValue;
}
}
http://www.algolist.net/Algorithms/Sorting/Insertion_sort
No comments:
Post a Comment