`{"id":"3f6333af-f2dd-49c8-9652-9786343e31df","name":"Insertion Sort","description":"1. You are given an array(arr) of integers.\r\n2. You have to sort the given array in increasing order using insertion sort.","inputFormat":"An Integer n \r\narr1\r\narr2..\r\nn integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 10000\r\n-10^9 &lt;= arr[i] &lt;= 10^9","sampleCode":{"cpp":{"code":"#include<iostream>\nusing namespace std;\n\n\nbool isGreater(int arr[],int j,int i ){\n cout<<\"Comparing \"<<arr[i]<<\" and \"<<arr[j]<<endl;\n if(arr[i]<arr[j]){\n return true;\n }else{\n return false;\n }\n}\n\nvoid swap(int arr[],int i,int j){\n cout<<\"Swapping \"<<arr[i]<<\" and \"<<arr[j]<<endl;\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n \n}\n\n\nvoid insertionSort(int arr[],int n){\n \n // write your code\n \n}\n\nvoid print(int arr[],int n){\n for(int i=0;i<n;i++){\n cout<<arr[i]<<endl;\n }\n}\n\n\n\nint main(){\n int n;\n cin>>n;\n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n \n insertionSort(arr,n);\n print(arr,n);\n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void insertionSort(int[] arr) {\r\n //write your code here\r\n \r\n }\r\n\r\n // used for swapping ith and jth elements of array\r\n public static void swap(int[] arr, int i, int j) {\r\n System.out.println(\"Swapping \" + arr[i] + \" and \" + arr[j]);\r\n int temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\r\n }\r\n\r\n // return true if jth element is greater than ith element\r\n public static boolean isGreater(int[] arr, int j, int i) {\r\n System.out.println(\"Comparing \" + arr[i] + \" and \" + arr[j]);\r\n if (arr[i] < arr[j]) {\r\n return true;\r\n } else {\r\n return false;\r\n }\r\n }\r\n\r\n public static void print(int[] arr) {\r\n for (int i = 0; i < arr.length; i++) {\r\n System.out.println(arr[i]);\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n insertionSort(arr);\r\n print(arr);\r\n }\r\n\r\n}"},"python":{"code":"def swap(arr,i,j):\n print(\"Swapping\",arr[i],\"and\",arr[j])\n temp=arr[i]\n arr[i]=arr[j]\n arr[j]=temp\n\ndef isGreater(arr,j,i):\n print(\"Comparing\",arr[i],\"and\",arr[j])\n\n if arr[i]<arr[j]:\n return True\n else :\n return False;\n\ndef insertionSort(arr):\n #write your code\n\n\ndef printList(arr):\n\tfor i in range(len(arr)):\n\t\tprint(arr[i], end=\"\\n\")\n\tprint()\n\n\n\narr = []\n\nn = int(input())\n\nfor i in range(0, n):\n\tele = int(input())\n\n\tarr.append(ele) # adding the element\ninsertionSort(arr);\nprintList(arr);"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \r\n3","sampleOutput":"Comparing -2 and 7\r\nSwapping 7 and -2\r\nComparing 4 and 7\r\nSwapping 7 and 4\r\nComparing 4 and -2\r\nComparing 1 and 7\r\nSwapping 7 and 1\r\nComparing 1 and 4\r\nSwapping 4 and 1\r\nComparing 1 and -2\r\nComparing 3 and 7\r\nSwapping 7 and 3\r\nComparing 3 and 4\r\nSwapping 4 and 3\r\nComparing 3 and 1\r\n-2\r\n1\r\n3\r\n4\r\n7","questionVideo":"https://www.youtube.com/embed/MMt2x6an_i8","hints":[],"associated":[{"id":"639c7d2c-72d2-48ca-a19a-9ab589a26fca","name":"Worst case time complexity of insertion sort?","slug":"worst-case-time-complexity-of-insertion-sort","type":4},{"id":"962b46bd-b953-4616-9065-50b4b368f397","name":"How many passes does an insertion sort algorithm consist of?","slug":"how-many-passes-does-an-insertion-sort-algorithm-consist-of","type":4},{"id":"9c430656-0dde-4067-82d3-2fb948c1b3d8","name":"what is best case time complexity of insertion sort?","slug":"what-is-best-case-time-complexity-of-insertion-sort","type":4},{"id":"c1e88c29-47c6-4fa0-b2ab-692812408d51","name":"Space complexity of insertion sort?","slug":"space-complexity-of-insertion-sort","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"8e3abac7-a5ab-4090-abd1-b26ef8b53d70","name":"Time and Space Complexity","slug":"time-and-space-complexity","type":0},{"id":"a3bd81cf-b5e2-4a88-927c-57be9eff8751","name":"Insertion Sort","slug":"insertion-sort","type":1}],"next":{"id":"59db3665-b776-4b08-937c-3201108b635a","name":"Insertion Sort","type":3,"slug":"insertion-sort"},"prev":{"id":"fc227825-8e2d-4d89-9c5c-148e37c9a9ec","name":"Selection Sort","type":3,"slug":"selection-sort"}}}`

# Insertion Sort

1. You are given an array(arr) of integers. 2. You have to sort the given array in increasing order using insertion sort.

`{"id":"3f6333af-f2dd-49c8-9652-9786343e31df","name":"Insertion Sort","description":"1. You are given an array(arr) of integers.\r\n2. You have to sort the given array in increasing order using insertion sort.","inputFormat":"An Integer n \r\narr1\r\narr2..\r\nn integers","outputFormat":"Check the sample output and question video.","constraints":"1 &lt;= N &lt;= 10000\r\n-10^9 &lt;= arr[i] &lt;= 10^9","sampleCode":{"cpp":{"code":"#include<iostream>\nusing namespace std;\n\n\nbool isGreater(int arr[],int j,int i ){\n cout<<\"Comparing \"<<arr[i]<<\" and \"<<arr[j]<<endl;\n if(arr[i]<arr[j]){\n return true;\n }else{\n return false;\n }\n}\n\nvoid swap(int arr[],int i,int j){\n cout<<\"Swapping \"<<arr[i]<<\" and \"<<arr[j]<<endl;\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n \n}\n\n\nvoid insertionSort(int arr[],int n){\n \n // write your code\n \n}\n\nvoid print(int arr[],int n){\n for(int i=0;i<n;i++){\n cout<<arr[i]<<endl;\n }\n}\n\n\n\nint main(){\n int n;\n cin>>n;\n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n \n insertionSort(arr,n);\n print(arr,n);\n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void insertionSort(int[] arr) {\r\n //write your code here\r\n \r\n }\r\n\r\n // used for swapping ith and jth elements of array\r\n public static void swap(int[] arr, int i, int j) {\r\n System.out.println(\"Swapping \" + arr[i] + \" and \" + arr[j]);\r\n int temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\r\n }\r\n\r\n // return true if jth element is greater than ith element\r\n public static boolean isGreater(int[] arr, int j, int i) {\r\n System.out.println(\"Comparing \" + arr[i] + \" and \" + arr[j]);\r\n if (arr[i] < arr[j]) {\r\n return true;\r\n } else {\r\n return false;\r\n }\r\n }\r\n\r\n public static void print(int[] arr) {\r\n for (int i = 0; i < arr.length; i++) {\r\n System.out.println(arr[i]);\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n Scanner scn = new Scanner(System.in);\r\n int n = scn.nextInt();\r\n int[] arr = new int[n];\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = scn.nextInt();\r\n }\r\n insertionSort(arr);\r\n print(arr);\r\n }\r\n\r\n}"},"python":{"code":"def swap(arr,i,j):\n print(\"Swapping\",arr[i],\"and\",arr[j])\n temp=arr[i]\n arr[i]=arr[j]\n arr[j]=temp\n\ndef isGreater(arr,j,i):\n print(\"Comparing\",arr[i],\"and\",arr[j])\n\n if arr[i]<arr[j]:\n return True\n else :\n return False;\n\ndef insertionSort(arr):\n #write your code\n\n\ndef printList(arr):\n\tfor i in range(len(arr)):\n\t\tprint(arr[i], end=\"\\n\")\n\tprint()\n\n\n\narr = []\n\nn = int(input())\n\nfor i in range(0, n):\n\tele = int(input())\n\n\tarr.append(ele) # adding the element\ninsertionSort(arr);\nprintList(arr);"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \r\n3","sampleOutput":"Comparing -2 and 7\r\nSwapping 7 and -2\r\nComparing 4 and 7\r\nSwapping 7 and 4\r\nComparing 4 and -2\r\nComparing 1 and 7\r\nSwapping 7 and 1\r\nComparing 1 and 4\r\nSwapping 4 and 1\r\nComparing 1 and -2\r\nComparing 3 and 7\r\nSwapping 7 and 3\r\nComparing 3 and 4\r\nSwapping 4 and 3\r\nComparing 3 and 1\r\n-2\r\n1\r\n3\r\n4\r\n7","questionVideo":"https://www.youtube.com/embed/MMt2x6an_i8","hints":[],"associated":[{"id":"639c7d2c-72d2-48ca-a19a-9ab589a26fca","name":"Worst case time complexity of insertion sort?","slug":"worst-case-time-complexity-of-insertion-sort","type":4},{"id":"962b46bd-b953-4616-9065-50b4b368f397","name":"How many passes does an insertion sort algorithm consist of?","slug":"how-many-passes-does-an-insertion-sort-algorithm-consist-of","type":4},{"id":"9c430656-0dde-4067-82d3-2fb948c1b3d8","name":"what is best case time complexity of insertion sort?","slug":"what-is-best-case-time-complexity-of-insertion-sort","type":4},{"id":"c1e88c29-47c6-4fa0-b2ab-692812408d51","name":"Space complexity of insertion sort?","slug":"space-complexity-of-insertion-sort","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"8e3abac7-a5ab-4090-abd1-b26ef8b53d70","name":"Time and Space Complexity","slug":"time-and-space-complexity","type":0},{"id":"a3bd81cf-b5e2-4a88-927c-57be9eff8751","name":"Insertion Sort","slug":"insertion-sort","type":1}],"next":{"id":"59db3665-b776-4b08-937c-3201108b635a","name":"Insertion Sort","type":3,"slug":"insertion-sort"},"prev":{"id":"fc227825-8e2d-4d89-9c5c-148e37c9a9ec","name":"Selection Sort","type":3,"slug":"selection-sort"}}}`

Editor

# Insertion Sort

easy

1. You are given an array(arr) of integers. 2. You have to sort the given array in increasing order using insertion sort.

## Constraints

1 <= N <= 10000 -10^9 <= arr[i] <= 10^9

## Format

### Input

An Integer n arr1 arr2.. n integers

### Output

Check the sample output and question video.

## Example

Sample Input

```.css-23h8hz{color:inherit;font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;}5 7 -2 4 1 3```

### Sample Output

```.css-3oaykw{color:var(--chakra-colors-active-primary);font-size:0.875rem;line-height:1.125rem;letter-spacing:0.016rem;font-weight:var(--chakra-fontWeights-normal);white-space:pre-wrap;font-family:Monospace;}Comparing -2 and 7 Swapping 7 and -2 Comparing 4 and 7 Swapping 7 and 4 Comparing 4 and -2 Comparing 1 and 7 Swapping 7 and 1 Comparing 1 and 4 Swapping 4 and 1 Comparing 1 and -2 Comparing 3 and 7 Swapping 7 and 3 Comparing 3 and 4 Swapping 4 and 3 Comparing 3 and 1 -2 1 3 4 7```

Question Video

Discussions

Show Discussion

Related Resources