{"id":"f155fbb1-34d3-4b78-838b-c4a8c78bc439","name":"Quick Sort","description":"1. You are given an array(arr) of integers.\r\n2. You have to sort the given array in increasing order using quick-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;= 100000\r\n-10^9 &lt;= arr[i] &lt;= 10^9","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\nvoid quicksort(vector<int> &arr, int lo, int hi){\n // write your code here\n}\n\nvoid Display(vector<int>& arr){\n for(int ele : arr){\n cout<< ele << \" \";\n }\n}\n\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n, 0);\n for(int i = 0; i < arr.size(); i++){\n cin >> arr[i];\n }\n quicksort(arr, 0, n - 1);\n Display(arr);\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 void quickSort(int[] arr, int lo, int hi) {\r\n //write your code here\r\n \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 quickSort(arr, 0, arr.length - 1);\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 \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 = prev + 1;\n swap(arr, curr, prev);\n curr = curr + 1;\n \n print(\"pivot index ->\" , prev);\n return prev;\n \ndef quicksort(arr, lo, hi):\n # write your code here\n \ndef Display(arr):\n for i in range(0, len(arr)):\n print(arr[i] ,end = \" \");\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\n quicksort(arr, 0, n-1);\n Display(arr);\n\n\nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \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\npivot -> 1\r\nSwapping -2 and -2\r\nSwapping 1 and 1\r\npivot index -> 1\r\npivot -> -2\r\nSwapping -2 and -2\r\npivot index -> 0\r\npivot -> 4\r\nSwapping 4 and 7\r\npivot index -> 3\r\npivot -> 7\r\nSwapping 7 and 7\r\npivot index -> 4\r\n-2 1 3 4 7","questionVideo":"https://www.youtube.com/embed/kdO5Q0nmPjU?end=173","hints":[],"associated":[{"id":"9c97d675-3308-4266-b30d-defc71d0701b","name":"Which of the sorting algorithms below is the quickest?","slug":"which-of-the-sorting-algorithms-below-is-the-quickest","type":4},{"id":"b4eb7f15-a40a-4246-80d7-42356cc85d3e","name":"What is a quick sort algorithm's worst-case time complexity?","slug":"what-is-a-quick-sort-algorithm-s-worst-case-time-complexity","type":4},{"id":"cef52e93-32c4-45d2-8a72-22e091f2c680","name":"The Divide-and-Conquer approach is used in the quick sort.","slug":"the-divide-and-conquer-approach-is-used-in-the-quick-sort","type":4},{"id":"d9086ffe-09a3-40d4-a6fc-bd1018d8b611","name":"Which of the following strategies for selecting the pivot element is the most effective?","slug":"which-of-the-following-strategies-for-selecting-the-pivot-element-is-the-most-effective","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":"4e13f761-16b1-46a0-b689-0d65ae8bfaa7","name":"Quick Sort","slug":"quick-sort","type":1}],"next":{"id":"33c07236-c741-49a0-b3ac-e8819b247a84","name":"Quick Sort","type":3,"slug":"quick-sort"},"prev":{"id":"15c569d6-e2ea-49fd-8c25-0571145cacbe","name":"Partition An Array","type":3,"slug":"partition-an-array"}}}

Quick Sort

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

{"id":"f155fbb1-34d3-4b78-838b-c4a8c78bc439","name":"Quick Sort","description":"1. You are given an array(arr) of integers.\r\n2. You have to sort the given array in increasing order using quick-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;= 100000\r\n-10^9 &lt;= arr[i] &lt;= 10^9","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\nvoid quicksort(vector<int> &arr, int lo, int hi){\n // write your code here\n}\n\nvoid Display(vector<int>& arr){\n for(int ele : arr){\n cout<< ele << \" \";\n }\n}\n\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n, 0);\n for(int i = 0; i < arr.size(); i++){\n cin >> arr[i];\n }\n quicksort(arr, 0, n - 1);\n Display(arr);\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 void quickSort(int[] arr, int lo, int hi) {\r\n //write your code here\r\n \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 quickSort(arr, 0, arr.length - 1);\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 \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 = prev + 1;\n swap(arr, curr, prev);\n curr = curr + 1;\n \n print(\"pivot index ->\" , prev);\n return prev;\n \ndef quicksort(arr, lo, hi):\n # write your code here\n \ndef Display(arr):\n for i in range(0, len(arr)):\n print(arr[i] ,end = \" \");\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\n quicksort(arr, 0, n-1);\n Display(arr);\n\n\nif __name__ == \"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n7 \r\n-2 \r\n4 \r\n1 \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\npivot -> 1\r\nSwapping -2 and -2\r\nSwapping 1 and 1\r\npivot index -> 1\r\npivot -> -2\r\nSwapping -2 and -2\r\npivot index -> 0\r\npivot -> 4\r\nSwapping 4 and 7\r\npivot index -> 3\r\npivot -> 7\r\nSwapping 7 and 7\r\npivot index -> 4\r\n-2 1 3 4 7","questionVideo":"https://www.youtube.com/embed/kdO5Q0nmPjU?end=173","hints":[],"associated":[{"id":"9c97d675-3308-4266-b30d-defc71d0701b","name":"Which of the sorting algorithms below is the quickest?","slug":"which-of-the-sorting-algorithms-below-is-the-quickest","type":4},{"id":"b4eb7f15-a40a-4246-80d7-42356cc85d3e","name":"What is a quick sort algorithm's worst-case time complexity?","slug":"what-is-a-quick-sort-algorithm-s-worst-case-time-complexity","type":4},{"id":"cef52e93-32c4-45d2-8a72-22e091f2c680","name":"The Divide-and-Conquer approach is used in the quick sort.","slug":"the-divide-and-conquer-approach-is-used-in-the-quick-sort","type":4},{"id":"d9086ffe-09a3-40d4-a6fc-bd1018d8b611","name":"Which of the following strategies for selecting the pivot element is the most effective?","slug":"which-of-the-following-strategies-for-selecting-the-pivot-element-is-the-most-effective","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":"4e13f761-16b1-46a0-b689-0d65ae8bfaa7","name":"Quick Sort","slug":"quick-sort","type":1}],"next":{"id":"33c07236-c741-49a0-b3ac-e8819b247a84","name":"Quick Sort","type":3,"slug":"quick-sort"},"prev":{"id":"15c569d6-e2ea-49fd-8c25-0571145cacbe","name":"Partition An Array","type":3,"slug":"partition-an-array"}}}
plane

Editor

Loading...

Quick Sort

easy

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

Constraints

1 <= N <= 100000 -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

5 7 -2 4 1 3

Sample Output

pivot -> 3 Swapping -2 and 7 Swapping 1 and 7 Swapping 3 and 4 pivot index -> 2 pivot -> 1 Swapping -2 and -2 Swapping 1 and 1 pivot index -> 1 pivot -> -2 Swapping -2 and -2 pivot index -> 0 pivot -> 4 Swapping 4 and 7 pivot index -> 3 pivot -> 7 Swapping 7 and 7 pivot index -> 4 -2 1 3 4 7

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode