Sorting algorithms/Insertion sort: Difference between revisions
(Created page from Help:Request a new programming task.) |
(Added Java example.) |
||
Line 10: | Line 10: | ||
j = j-1 |
j = j-1 |
||
A[j+1] = value |
A[j+1] = value |
||
Writing the algorithm for integers will suffice. |
|||
=={{header|Java}}== |
|||
public static void insertSort(int[] A){ |
|||
for(int i = 1; i < A.length; i++){ |
|||
int value = A[i]; |
|||
int j = i - 1; |
|||
while(j >= 0 && A[j] > value){ |
|||
A[j + 1] = A[j]; |
|||
j = j - 1; |
|||
} |
|||
A[j + 1] = value; |
|||
} |
|||
} |
Revision as of 20:39, 14 November 2007
You are encouraged to solve this task according to the task description, using any language you may know.
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
An O(n^2) sorting algorithm which moves elements one at a time into the correct position. The algorithm is as follows (from the wikipedia):
insertionSort(array A) for i = 1 to length[A]-1 do value = A[i] j = i-1 while j >= 0 and A[j] > value do A[j + 1] = A[j] j = j-1 A[j+1] = value
Writing the algorithm for integers will suffice.
Java
public static void insertSort(int[] A){ for(int i = 1; i < A.length; i++){ int value = A[i]; int j = i - 1; while(j >= 0 && A[j] > value){ A[j + 1] = A[j]; j = j - 1; } A[j + 1] = value; } }