Insertion sort code in Java code example
Example 1: java insertion sort
/**
* Insertion sort algorithm, O(n^2) time complexity.
*/
public static void insertionSort(int[] arr) {
int n = arr.length;
for(int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
//shift until you find the position to place the element 'key'
while(j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j--;
}
//place element 'key' in the correct position in the sorted part of the array
arr[j+1] = key;
}
}
Example 2: Insertion sort code in Java
// Java program for implementation of Insertion Sort
public class InsertionSort
{
/*Function to sort array using insertion sort*/
void sort(int arr[])
{
int n = arr.length;
for (int i=1; i<n; ++i)
{
int key = arr[i];
int j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}
/* A utility function to print array of size n*/
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver method
public static void main(String args[])
{
int arr[] = {12, 11, 13, 5, 6};
InsertionSort ob = new InsertionSort();
ob.sort(arr);
printArray(arr);
}
}