{"id":"2255b761-4cdf-4620-a2b4-3c34b5fdd0b1","name":"Quick Select","description":"1. You are given an array(arr) of integers.\r\n2. You have to find the k-th smallest element in the given array using the quick-select algorithm.","inputFormat":"An Integer n \r\narr1\r\narr2..\r\nn integers\r\nAn integer k","outputFormat":"Check the sample output and question video.","constraints":"1 <= N <= 100000\r\n-10^9 <= arr[i] <= 10^9\r\n1 <= k <= N","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<vector>\n\nusing namespace std;\n\n\nvoid swap(vector<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\nint partition(vector<int> &arr, int pivot, int lo, int hi){\n cout << \"pivot -> \" << pivot << endl;\n int curr = lo;\n int prev = lo - 1;\n while(curr <= hi){\n if(arr[curr] <= pivot){\n prev++;\n swap(arr, curr, prev);\n }\n curr++;\n }\n cout << \"pivot index -> \" << prev << endl;\n return prev;\n}\n\n\nint quickselect(vector<int>& arr, int lo, int hi, int k) {\n // write your code here\n return 0;\n}\n\nint main() {\n int n;\n cin >> n;\n vector<int> arr(n, 0);\n for (int i = 0; i < n; i++) {\n cin >> arr[i];\n }\n int k;\n cin >> k;\n\n int ans = quickselect(arr, 0, n - 1, k-1);\n cout << ans << endl;\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static int quickSelect(int[] arr, int lo, int hi, int k) {\r\n //write your code here\r\n\r\n return null;\r\n }\r\n\r\n public static int partition(int[] arr, int pivot, int lo, int hi) {\r\n System.out.println(\"pivot -> \" + pivot);\r\n int i = lo, j = lo;\r\n while (i <= hi) {\r\n if (arr[i] <= pivot) {\r\n swap(arr, i, j);\r\n i++;\r\n j++;\r\n } else {\r\n i++;\r\n }\r\n }\r\n System.out.println(\"pivot index -> \" + (j - 1));\r\n return (j - 1);\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 public static void print(int[] arr) {\r\n for (int i = 0; i < arr.length; i++) {\r\n System.out.print(arr[i] + \" \");\r\n }\r\n System.out.println();\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 int k = scn.nextInt();\r\n System.out.println(quickSelect(arr,0,arr.length - 1,k - 1));\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 partition(arr, pivot, lo, hi):\n print(\"pivot ->\" , pivot);\n curr = lo;\n prev = lo - 1;\n while(curr <= hi):\n if(arr[curr] <= pivot):\n prev += 1;\n swap(arr, curr, prev);\n curr += 1;\n print(\"pivot index ->\" , prev);\n return prev;\n\n\ndef quickselect(arr, lo, hi, k):\n #write your code here\n\ndef main():\n n = int(input());\n arr = []\n for i in range(0, n):\n ele = int(input());\n arr.append(ele);\n k = int(input());\n \n ans = quickselect(arr, 0, n - 1, k-1);\n print(ans);\n \nif __name__ == \"__main__\":\n main();"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \r\n3\r\n3","sampleOutput":"pivot -> 3\r\nSwapping -2 and 7\r\nSwapping 1 and 7\r\nSwapping 3 and 4\r\npivot index -> 2\r\n3","questionVideo":"https://www.youtube.com/embed/fnbImb8lo88?end=295","hints":[],"associated":[{"id":"245441ea-43be-4265-b667-90cd52aba144","name":"Where will we find our required element if the value of the partition index pi is greater than k-1?","slug":"where-will-we-find-our-required-element-if-the-value-of-the-partition-index-pi-is-greater-than-k-1","type":4},{"id":"4c5345b1-bafe-40a7-b5c6-2095655897f1","name":"What is a quick select algorithm's worst-case time complexity?","slug":"what-is-a-quick-select-algorithm-s-worst-case-time-complexity","type":4},{"id":"53f90c12-312e-4e42-980a-98c050fdd795","name":"What is a quick select algorithm's best-case time complexity?","slug":"what-is-a-quick-select-algorithm-s-best-case-time-complexity","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":"02714421-52a0-4387-9a91-269ca2bda90a","name":"Quick Select","slug":"quick-select","type":1}],"next":{"id":"04d7a99b-91f3-4530-94b3-ebef8499df60","name":"Quick Select","type":3,"slug":"quick-select"},"prev":{"id":"33c07236-c741-49a0-b3ac-e8819b247a84","name":"Quick Sort","type":3,"slug":"quick-sort"}}}1. You are given an array(arr) of integers. 2. You have to find the k-th smallest element in the given array using the quick-select algorithm.
{"id":"2255b761-4cdf-4620-a2b4-3c34b5fdd0b1","name":"Quick Select","description":"1. You are given an array(arr) of integers.\r\n2. You have to find the k-th smallest element in the given array using the quick-select algorithm.","inputFormat":"An Integer n \r\narr1\r\narr2..\r\nn integers\r\nAn integer k","outputFormat":"Check the sample output and question video.","constraints":"1 <= N <= 100000\r\n-10^9 <= arr[i] <= 10^9\r\n1 <= k <= N","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<vector>\n\nusing namespace std;\n\n\nvoid swap(vector<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\nint partition(vector<int> &arr, int pivot, int lo, int hi){\n cout << \"pivot -> \" << pivot << endl;\n int curr = lo;\n int prev = lo - 1;\n while(curr <= hi){\n if(arr[curr] <= pivot){\n prev++;\n swap(arr, curr, prev);\n }\n curr++;\n }\n cout << \"pivot index -> \" << prev << endl;\n return prev;\n}\n\n\nint quickselect(vector<int>& arr, int lo, int hi, int k) {\n // write your code here\n return 0;\n}\n\nint main() {\n int n;\n cin >> n;\n vector<int> arr(n, 0);\n for (int i = 0; i < n; i++) {\n cin >> arr[i];\n }\n int k;\n cin >> k;\n\n int ans = quickselect(arr, 0, n - 1, k-1);\n cout << ans << endl;\n return 0;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static int quickSelect(int[] arr, int lo, int hi, int k) {\r\n //write your code here\r\n\r\n return null;\r\n }\r\n\r\n public static int partition(int[] arr, int pivot, int lo, int hi) {\r\n System.out.println(\"pivot -> \" + pivot);\r\n int i = lo, j = lo;\r\n while (i <= hi) {\r\n if (arr[i] <= pivot) {\r\n swap(arr, i, j);\r\n i++;\r\n j++;\r\n } else {\r\n i++;\r\n }\r\n }\r\n System.out.println(\"pivot index -> \" + (j - 1));\r\n return (j - 1);\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 public static void print(int[] arr) {\r\n for (int i = 0; i < arr.length; i++) {\r\n System.out.print(arr[i] + \" \");\r\n }\r\n System.out.println();\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 int k = scn.nextInt();\r\n System.out.println(quickSelect(arr,0,arr.length - 1,k - 1));\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 partition(arr, pivot, lo, hi):\n print(\"pivot ->\" , pivot);\n curr = lo;\n prev = lo - 1;\n while(curr <= hi):\n if(arr[curr] <= pivot):\n prev += 1;\n swap(arr, curr, prev);\n curr += 1;\n print(\"pivot index ->\" , prev);\n return prev;\n\n\ndef quickselect(arr, lo, hi, k):\n #write your code here\n\ndef main():\n n = int(input());\n arr = []\n for i in range(0, n):\n ele = int(input());\n arr.append(ele);\n k = int(input());\n \n ans = quickselect(arr, 0, n - 1, k-1);\n print(ans);\n \nif __name__ == \"__main__\":\n main();"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \r\n3\r\n3","sampleOutput":"pivot -> 3\r\nSwapping -2 and 7\r\nSwapping 1 and 7\r\nSwapping 3 and 4\r\npivot index -> 2\r\n3","questionVideo":"https://www.youtube.com/embed/fnbImb8lo88?end=295","hints":[],"associated":[{"id":"245441ea-43be-4265-b667-90cd52aba144","name":"Where will we find our required element if the value of the partition index pi is greater than k-1?","slug":"where-will-we-find-our-required-element-if-the-value-of-the-partition-index-pi-is-greater-than-k-1","type":4},{"id":"4c5345b1-bafe-40a7-b5c6-2095655897f1","name":"What is a quick select algorithm's worst-case time complexity?","slug":"what-is-a-quick-select-algorithm-s-worst-case-time-complexity","type":4},{"id":"53f90c12-312e-4e42-980a-98c050fdd795","name":"What is a quick select algorithm's best-case time complexity?","slug":"what-is-a-quick-select-algorithm-s-best-case-time-complexity","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":"02714421-52a0-4387-9a91-269ca2bda90a","name":"Quick Select","slug":"quick-select","type":1}],"next":{"id":"04d7a99b-91f3-4530-94b3-ebef8499df60","name":"Quick Select","type":3,"slug":"quick-select"},"prev":{"id":"33c07236-c741-49a0-b3ac-e8819b247a84","name":"Quick Sort","type":3,"slug":"quick-sort"}}}
Editor
Discussions
Show Discussion
Related Resources
