`{"id":"b5ed1765-0f09-49c3-8616-0e216bc229fc","name":"Sort 012","description":"1. You are given an array(arr) containing only 0's, 1's, and 2's.\r\n2. You have to sort the given array in increasing order and in linear time.","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\narr[i] = 0,1,2","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\n\r\nusing namespace std;\r\n\r\nvoid input(vector<int> &arr)\r\n{\r\n for (int i = 0; i < arr.size(); i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n}\r\n\r\nvoid print(vector<int> &arr)\r\n{\r\n for (int i = 0; i < arr.size(); i++)\r\n {\r\n cout << arr[i] << endl;\r\n }\r\n cout << endl;\r\n}\r\n\r\n// used for swapping ith and jth elements of array\r\nvoid swap(vector<int> &arr, int i, int j)\r\n{\r\n cout << (\"Swapping index \" + to_string(i) + \" and index \" + to_string(j)) << endl;\r\n int temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\r\n}\r\n\r\nvoid sort012(vector<int> &arr)\r\n{\r\n\r\n}\r\n\r\nint main()\r\n{\r\n int n, m;\r\n cin >> n;\r\n vector<int> A(n, 0);\r\n input(A);\r\n\r\n sort012(A);\r\n print(A);\r\n return 0;\r\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void sort012(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 index \" + i + \" and index \" + j);\r\n int temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\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 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 sort012(arr);\r\n print(arr);\r\n }\r\n\r\n}"},"python":{"code":"def printlist(arr):\n for i in arr:\n print(i)\n\n# used for swapping ith and jth elements of array\ndef swap(arr, i, j):\n print(\"Swapping index\" , i , \"and index\" ,j);\n temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n\ndef sort012(arr):\n #write your code here\n\n\nn = int(input());\nA= [];\nfor i in range(0, n):\n val = int(input());\n A.append(val) ;\nsort012(A);\nprintlist(A);"}},"points":10,"difficulty":"easy","sampleInput":"10\r\n1\r\n0\r\n2\r\n2\r\n1\r\n0\r\n2\r\n1\r\n0\r\n2","sampleOutput":"Swapping index 1 and index 0\r\nSwapping index 2 and index 9\r\nSwapping index 2 and index 8\r\nSwapping index 2 and index 1\r\nSwapping index 3 and index 7\r\nSwapping index 5 and index 2\r\nSwapping index 6 and index 6\r\n0\r\n0\r\n0\r\n1\r\n1\r\n1\r\n2\r\n2\r\n2\r\n2","questionVideo":"https://www.youtube.com/embed/MbV26HWqxrs?end=27","hints":[],"associated":[{"id":"24ad9b64-931a-40d9-a24d-e9f6ed7762aa","name":"How many segments we are maintaining in single pass algorithm?","slug":"how-many-segments-we-are-maintaining-in-single-pass-algorithm","type":4},{"id":"5289a414-3cb0-48ed-b81a-b762144477d7","name":"If the number of records to be sorted is small, then …… sorting can be efficient.","slug":"if-the-number-of-records-to-be-sorted-is-small-then-sorting-can-be-efficient","type":4},{"id":"cde895e0-5692-42da-a4d2-63ac17b9b80b","name":"If we use three pointer technique in Sort 012 then what will be the time complexity","slug":"if-we-use-three-pointer-technique-in-sort-012-then-what-will-be-the-time-complexity","type":4},{"id":"f7d2b57b-e648-493e-9454-704e738c080f","name":"A sorting technique is called stable if i","slug":"a-sorting-technique-is-called-stable-if-i","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":"32dd792b-e655-47f0-b03d-c3c2c0b355ee","name":"Sort 012","slug":"sort-012","type":1}],"next":{"id":"9807148e-86a0-4153-bbcd-a17622bff866","name":"Sort 012","type":3,"slug":"sort-012"},"prev":{"id":"0a2805ae-c8a1-4681-affa-904b12caf035","name":"Sort 01","type":3,"slug":"sort-01"}}}`

# Sort 012

1. You are given an array(arr) containing only 0's, 1's, and 2's. 2. You have to sort the given array in increasing order and in linear time.

`{"id":"b5ed1765-0f09-49c3-8616-0e216bc229fc","name":"Sort 012","description":"1. You are given an array(arr) containing only 0's, 1's, and 2's.\r\n2. You have to sort the given array in increasing order and in linear time.","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\narr[i] = 0,1,2","sampleCode":{"cpp":{"code":"#include <iostream>\r\n#include <vector>\r\n\r\nusing namespace std;\r\n\r\nvoid input(vector<int> &arr)\r\n{\r\n for (int i = 0; i < arr.size(); i++)\r\n {\r\n cin >> arr[i];\r\n }\r\n}\r\n\r\nvoid print(vector<int> &arr)\r\n{\r\n for (int i = 0; i < arr.size(); i++)\r\n {\r\n cout << arr[i] << endl;\r\n }\r\n cout << endl;\r\n}\r\n\r\n// used for swapping ith and jth elements of array\r\nvoid swap(vector<int> &arr, int i, int j)\r\n{\r\n cout << (\"Swapping index \" + to_string(i) + \" and index \" + to_string(j)) << endl;\r\n int temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\r\n}\r\n\r\nvoid sort012(vector<int> &arr)\r\n{\r\n\r\n}\r\n\r\nint main()\r\n{\r\n int n, m;\r\n cin >> n;\r\n vector<int> A(n, 0);\r\n input(A);\r\n\r\n sort012(A);\r\n print(A);\r\n return 0;\r\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void sort012(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 index \" + i + \" and index \" + j);\r\n int temp = arr[i];\r\n arr[i] = arr[j];\r\n arr[j] = temp;\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 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 sort012(arr);\r\n print(arr);\r\n }\r\n\r\n}"},"python":{"code":"def printlist(arr):\n for i in arr:\n print(i)\n\n# used for swapping ith and jth elements of array\ndef swap(arr, i, j):\n print(\"Swapping index\" , i , \"and index\" ,j);\n temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n\ndef sort012(arr):\n #write your code here\n\n\nn = int(input());\nA= [];\nfor i in range(0, n):\n val = int(input());\n A.append(val) ;\nsort012(A);\nprintlist(A);"}},"points":10,"difficulty":"easy","sampleInput":"10\r\n1\r\n0\r\n2\r\n2\r\n1\r\n0\r\n2\r\n1\r\n0\r\n2","sampleOutput":"Swapping index 1 and index 0\r\nSwapping index 2 and index 9\r\nSwapping index 2 and index 8\r\nSwapping index 2 and index 1\r\nSwapping index 3 and index 7\r\nSwapping index 5 and index 2\r\nSwapping index 6 and index 6\r\n0\r\n0\r\n0\r\n1\r\n1\r\n1\r\n2\r\n2\r\n2\r\n2","questionVideo":"https://www.youtube.com/embed/MbV26HWqxrs?end=27","hints":[],"associated":[{"id":"24ad9b64-931a-40d9-a24d-e9f6ed7762aa","name":"How many segments we are maintaining in single pass algorithm?","slug":"how-many-segments-we-are-maintaining-in-single-pass-algorithm","type":4},{"id":"5289a414-3cb0-48ed-b81a-b762144477d7","name":"If the number of records to be sorted is small, then …… sorting can be efficient.","slug":"if-the-number-of-records-to-be-sorted-is-small-then-sorting-can-be-efficient","type":4},{"id":"cde895e0-5692-42da-a4d2-63ac17b9b80b","name":"If we use three pointer technique in Sort 012 then what will be the time complexity","slug":"if-we-use-three-pointer-technique-in-sort-012-then-what-will-be-the-time-complexity","type":4},{"id":"f7d2b57b-e648-493e-9454-704e738c080f","name":"A sorting technique is called stable if i","slug":"a-sorting-technique-is-called-stable-if-i","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":"32dd792b-e655-47f0-b03d-c3c2c0b355ee","name":"Sort 012","slug":"sort-012","type":1}],"next":{"id":"9807148e-86a0-4153-bbcd-a17622bff866","name":"Sort 012","type":3,"slug":"sort-012"},"prev":{"id":"0a2805ae-c8a1-4681-affa-904b12caf035","name":"Sort 01","type":3,"slug":"sort-01"}}}` Editor

# Sort 012

easy

1. You are given an array(arr) containing only 0's, 1's, and 2's. 2. You have to sort the given array in increasing order and in linear time.

## Constraints

1 <= N <= 10000 arr[i] = 0,1,2

## 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;}10 1 0 2 2 1 0 2 1 0 2```

### 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;}Swapping index 1 and index 0 Swapping index 2 and index 9 Swapping index 2 and index 8 Swapping index 2 and index 1 Swapping index 3 and index 7 Swapping index 5 and index 2 Swapping index 6 and index 6 0 0 0 1 1 1 2 2 2 2```

Question Video

Discussions

Show Discussion

Related Resources 