Insertion Sort

Let's begin!

Insertion sort is a Sorting Algorithm which have average time complexity as polynomial square and best case as linear.

It has two function:

1. Function which linearly proceeds through array.
   
   
2. Helper Function to compare and swap the element if required within the given range.

If the function finds that right element is smaller then left element then it will call the helper function to compare and swap the elements if necessary.

	#include <iostream>
	void print(int *arr, int length)
	{
	for(int i=0; i<length; i++)
	{
	std::cout<<arr[i]<<" ";
	}
	std::cout<<"\n";
	}
	int *insertion_sort(int *arr, int high)
	{
	for(int i=high; i>0; i--)
	{
	if (arr[i] < arr[i-1])
	{
	int temp = arr[i];
	arr[i] = arr[i-1];
	arr[i-1] = temp;
	}
	}
	return arr;
	}
	int *insertion_sort(int *arr)
	{
	for(int i=0; i<sizeof(arr); i++)
	{
	if(arr[i+1] < arr[i])
	{
	arr = insertion_sort(arr,i+1);
	}
	}
	return arr;
	}
	int main()
	{
	int length;
	std::cout<<"Length of Array: ";
	std::cin>>length;
	std::cout<<"Enter Elements:\n";
	int arr[length];
	for(int i=0; i<length; i++)
	{
	std::cin>>arr[i];
	}
	print(insertion_sort(arr),length);
	return 0;
	}

view raw insertion_sort.cpp hosted with ❤ by GitHub

	package Algorithms.Sort;
	import java.util.Scanner;
	public class InsertionSort {
	// To print the sorted array
	public static void print(int arr[], int length)
	{
	System.out.print("Sorted Array: ");
	for(int i=0; i<length; i++)
	{
	System.out.print(arr[i]+" ");
	}
	System.out.println("");
	}
	// To verify if the array is sorted
	public static boolean isSorted(int arr[], int length)
	{
	for(int i=0; (i+1)<length; i++)
	{
	if (arr[i] > arr[i+1])
	{
	return false;
	}
	}
	return true;
	}
	// To sort from given range
	public static void sort(int arr[], int high)
	{
	for(int i=high; (i-1)>=0; i--)
	{
	if(arr[i] < arr[i-1])
	{
	int temp = arr[i];
	arr[i] = arr[i-1];
	arr[i-1] = temp;
	}
	}
	}
	// Insertion Sort
	public static int insertionSort (int arr[], int length) []
	{
	// Returns if array is sorted
	if (isSorted(arr, length) == true)
	{
	return arr;
	}
	// Sort by given range
	for(int i=1; i<length; i++)
	{
	sort(arr, i);
	}
	// Recursion till function is sorted
	return insertionSort(arr, length);
	}
	public static void main(String arg[])
	{
	Scanner scan = new Scanner (System.in);
	System.out.print("Enter the length of the Array: ");
	int length = scan.nextInt();
	int arr [] = new int [length];
	for(int i=0; i<length; i++)
	{
	System.out.print("Enter element "+(i+1)+" : ");
	arr[i] = scan.nextInt();
	}
	scan.close();
	insertionSort(arr, length);
	print(arr, length);
	}
	}

view raw InsertionSort.java hosted with ❤ by GitHub

	def swap(arr, end):
	for index in range(end, 0, -1):
	if arr[index] < arr[index-1]:
	arr[index], arr[index-1] = arr[index - 1], arr[index]
	return
	def insertionSort(arr, length):
	for index in range(1,length):
	swap(arr, index)
	return
	if __name__ == "__main__":
	user_input = input("Eneter Length of the List: ")
	length = int(user_input)
	arr = []
	for num in range(length):
	user_input = input("Enter Element {} : ".format(num+1))
	arr.append(int(user_input))
	print("Given List: ", arr)
	insertionSort(arr, length)
	print("Sorted List: ", arr)

view raw insertion_sort.py hosted with ❤ by GitHub