Skip to content

Instantly share code, notes, and snippets.

@anil477
Last active November 17, 2017 11:21
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save anil477/4bc8d04d9ba62c568e6226ac260a8200 to your computer and use it in GitHub Desktop.
Insertion Sort
// Java program for implementation of Insertion Sort
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];
// now that we need to insert new element, we will have to shift element from sorted part
// i always points to the unsorted part. So go to sorted part we set j = i-1
// j points to the end of the sorted part
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment