{"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"}}}
plane

Editor

Loading...

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

10 1 0 2 2 1 0 2 1 0 2

Sample Output

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

related resources

Turning Off Zen Mode