Insertion sortInsertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Example :
.........
Algorithm insertionsort [A (0..n-1)]
// Sort a given array by Counting sort.
// Input : An array A(0,n-1) of orderable elements.
// Output : Array A [0,n-1] sorted in non- decreasing order .
// Sort an arr[] of size n
insertionSort(arr, n)
// Pick element arr[i] and insert it into sorted sequence arr[0i-1]
Loop from i =1 to n-1
do
j = I -1
while j >= 0 and A[j] >[j+1]
do
swap=A[j], A[j+1])
j = j -1
#include < stdio.h>
void insert(int a[], int n) /* function to sort an aay with insertion sort */
{
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
void printArr(int a[], int n) /* function to print the array */
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
Code
public class Insert
{
void insert(int a[]) /* function to sort an aay with insertion sort */
{
int i, j, temp;
int n = a.length;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position ahead from their current position*/
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
void printArr(int a[]) /* function to print the array */
{
int i;
int n = a.length;
for (i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
public static void main(String[] args) {
int a[] = { 92, 50, 5, 20, 11, 22 };
Insert i1 = new Insert();
System.out.println("\nBefore sorting array elements are - ");
i1.printArr(a);
i1.insert(a);
System.out.println("\n\nAfter sorting array elements are - ");
i1.printArr(a);
System.out.println();
}
}
Code
def insertionSort(a): # Function to implement insertion sort
for i in range(1, len(a)):
temp = a[i]
# Move the elements greater than temp to one position
#ahead from their current position
j = i-1
while j >= 0 and temp < a[j] :
a[j + 1] = a[j]
j = j-1
a[j + 1] = temp
def printArr(a): # function to print the array
for i in range(len(a)):
print (a[i], end = " ")
a = [70, 15, 2, 51, 60]
print("Before sorting array elements are - ")
printArr(a)
insertionSort(a)
print("\nAfter sorting array elements are - ")
printArr(a)
Code
60, 70, 15, 2, 51
2, 15, 51, 60, 70
Heap sort
Merge Sort