Partition Sort<\/em>). This challenge is a modified version of the algorithm that only addresses partitioning. It is implemented as follows:<\/p>\n\n\n\nStep 1: Divide<\/strong>
Choose some pivot element,\u00a0p<\/strong><\/em>, and partition your unsorted array,\u00a0arr<\/strong><\/em>, into three smaller arrays:\u00a0left<\/strong><\/em>,\u00a0right<\/strong><\/em>, and\u00a0equal<\/strong><\/em>, where each element in\u00a0left<\/em> < p<\/em><\/strong>, each element in\u00a0right > p<\/strong><\/em>, and each element in\u00a0equal<\/em> = p<\/strong>.<\/p>\n\n\n\nExample<\/strong><\/p>\n\n\n\narr<\/em> = [5, 7, 4, 3, 8]<\/strong><\/p>\n\n\n\nIn this challenge, the pivot will always be at\u00a0arr<\/em>[0]<\/strong>, so the pivot is\u00a05<\/strong>.<\/p>\n\n\n\narr<\/strong><\/em>\u00a0is divided into\u00a0left<\/em> = {4, 3}<\/strong>,\u00a0equal<\/em> = {5}<\/strong>, and\u00a0right<\/em> = {7, 8}<\/strong>.
Putting them all together, you get\u00a0{4, 3, 5, 7, 8}<\/strong>. There is a flexible checker that allows the elements of\u00a0left<\/strong><\/em>\u00a0and\u00a0right<\/strong><\/em>\u00a0to be in any order. For example,\u00a0{3, 4, 5, 8, 7}<\/strong>\u00a0is valid as well.<\/p>\n\n\n\nGiven\u00a0arr<\/strong><\/em>\u00a0and\u00a0p = arr<\/em>[0]<\/strong>, partition\u00a0arr<\/strong><\/em>\u00a0into\u00a0left<\/strong><\/em>,\u00a0right<\/strong><\/em>, and\u00a0equal<\/strong><\/em>\u00a0using the\u00a0Divide<\/em>\u00a0instructions above. Return a 1-dimensional array containing each element in\u00a0left<\/strong><\/em>\u00a0first, followed by each element in\u00a0equal<\/strong><\/em>, followed by each element in\u00a0right<\/strong><\/em>.<\/p>\n\n\n\nFunction Description<\/strong><\/p>\n\n\n\nComplete the quickSort<\/em> function in the editor below.<\/p>\n\n\n\nquickSort has the following parameter(s):<\/p>\n\n\n\n
- int arr[n]:<\/em>\u00a0arr<\/em>[0]<\/strong>\u00a0is the pivot element<\/li><\/ul>\n\n\n\n
Returns<\/strong><\/p>\n\n\n\n- int[n]:<\/em>\u00a0an array of integers as described above<\/li><\/ul>\n\n\n\n
<\/span>Input Format<\/strong><\/span><\/h2>\n\n\n\nThe first line contains\u00a0n<\/strong><\/em>, the size of\u00a0arr<\/strong><\/em>.
The second line contains\u00a0n<\/strong><\/em>\u00a0space-separated integers\u00a0arr<\/em>[i<\/em>]<\/strong>\u00a0(the unsorted array). The first integer,\u00a0arr<\/em>[0]<\/strong>, is the pivot element,\u00a0p<\/strong><\/em>.<\/p>\n\n\n\n<\/span>Constraints<\/strong><\/span><\/h2>\n\n\n\n- 1 <= n<\/em> <= 1000<\/strong><\/li>
- -1000 <= arr<\/em>[i<\/em>] <= 1000 <\/strong>where 0 <= i<\/em> < n<\/em><\/strong><\/li>
- All elements are distinct. <\/strong><\/li><\/ul>\n\n\n\n
Sample Input<\/strong><\/p>\n\n\n\nSTDIN Function\r\n----- --------\r\n5 arr[] size n =5\r\n4 5 3 7 2 arr =[4, 5, 3, 7, 2]<\/code><\/pre>\n\n\n\nSample Output<\/strong><\/p>\n\n\n\n3 2 4 5 7<\/code><\/pre>\n\n\n\nExplanation<\/strong><\/p>\n\n\n\narr<\/em> = [4, 5, 3, 7, 2]<\/strong>\u00a0Pivot<\/em>:\u00a0p<\/em> = arr<\/em>[0] = 4<\/strong>.
left<\/em> = {}<\/strong>;\u00a0equal<\/strong><\/em> = {4}<\/strong>; right<\/em> = {}<\/strong>\u00a0<\/p>\n\n\n\narr<\/em>[1] = 5 > p<\/em><\/strong>, so it is added to right<\/strong><\/em>.
left<\/em> = {}; equal<\/em> = {4}; right<\/em> = {5}<\/strong><\/p>\n\n\n\narr<\/em>[2] = 3 < p<\/em><\/strong>, so it is added to\u00a0left<\/strong><\/em>.
left<\/em> = {3}<\/strong>;\u00a0equal<\/em> = {4}<\/strong>;\u00a0right<\/em> = {5}<\/strong><\/p>\n\n\n\narr<\/em>[3] = 7 > p<\/em><\/strong>, so it is added to\u00a0right<\/strong><\/em>.
left<\/em> = {3}<\/strong>;\u00a0equal<\/em> = {4}<\/strong>;\u00a0right<\/em> = {5, 7}<\/strong><\/p>\n\n\n\narr<\/em>[4] = 2 < p<\/em><\/strong>, so it is added to\u00a0left<\/strong><\/em>.
left<\/em> = {3, 2}<\/strong>;\u00a0equal<\/em> = {4}<\/strong>;\u00a0right<\/em> = {5, 7}<\/strong><\/p>\n\n\n\nReturn the array\u00a0{32457}<\/strong>.<\/p>\n\n\n\nThe order of the elements to the left and right of\u00a04<\/strong>\u00a0does not need to match this answer. It is only required that\u00a03<\/strong>\u00a0and\u00a02<\/strong>\u00a0are to the left of\u00a04<\/strong>, and\u00a05<\/strong>\u00a0and\u00a07<\/strong>\u00a0are to the right.<\/p>\n\n\n\n<\/span>Solution – Quicksort 1 – Partition – HackerRank Solution<\/strong><\/span><\/h2>\n\n\n\n<\/span>C++<\/strong><\/span><\/h3>\n\n\n\n#include <vector>\n#include <iostream>\n#include <algorithm>\n\nusing namespace std;\n\nvoid partition(vector<int> arr) {\n \n int length = arr.size() - 1; \/\/ store length modded to be without p in next steps\n int p = arr.front(); \/\/ declare pivot\n arr.erase(arr.begin()); \/\/ erases pivot from array\n \n vector<int> left;\n vector<int> right;\n \n int i, n;\n \n for (i = 0; i < length; i++) { \n (arr[i] > p) ? right.push_back(arr[i]) : left.push_back(arr[i]); \n }\n \n for (i = 0, n = left.size(); i < n; i++)\n cout << left[i] << \" \";\n \n cout << p << \" \";\n \n for (i = 0, n = right.size(); i < n; i++)\n cout << right[i] << \" \";\n cout << \"\\n\";\n \n}\nint main(void) {\n vector <int> _ar;\n int _ar_size;\ncin >> _ar_size;\nfor(int _ar_i=0; _ar_i<_ar_size; _ar_i++) {\n int _ar_tmp;\n cin >> _ar_tmp;\n _ar.push_back(_ar_tmp); \n}\n\npartition(_ar);\n \n return 0;\n}\n<\/pre>\n\n\n\n<\/span>Python<\/strong><\/span><\/h3>\n\n\n\nimport sys\n\ndef quickSort(arr):\n left = []\n equal = []\n right = []\n pivot = arr[0]\n \n for el in arr:\n if el < pivot:\n left.append(el)\n elif el == pivot:\n equal.append(el)\n elif el > pivot:\n right.append(el)\n \n return left + equal + right\n\nif __name__ == \"__main__\":\n n = int(input().strip())\n arr = list(map(int, input().strip().split(' ')))\n result = quickSort(arr)\n print (\" \".join(map(str, result)))\n<\/pre>\n\n\n\n<\/span>Java<\/strong><\/span><\/h3>\n\n\n\nimport java.util.Scanner;\n\npublic class Solution {\n public static void main(String[] args) {\n Scanner scan = new Scanner(System.in);\n int s = scan.nextInt();\n int[] array = new int[s];\n for (int i = 0; i < s; i++) {\n array[i] = scan.nextInt(); \n }\n scan.close();\n partition(array);\n printArray(array);\n }\n \n \/* Partitions array into 2 parts. \n * 1) Left side has values smaller than pivotValue\n * 2) Right side has values larger than pivotValue\n * Returns pivotIndex\n *\/\n public static int partition(int [] array) {\n int pivotIndex = 0; \/\/ not a great choice of pivot.\n int pivotValue = array[pivotIndex];\n \n swap(array, pivotIndex, array.length - 1); \/\/ put pivot at end for now.\n \n \/* Linear search, comparing all elements to pivotValue and swapping as necessary *\/\n int indexToReturn = 0;\n for (int i = 0; i < array.length; i++){\n if (array[i] < pivotValue){\n swap(array, i, indexToReturn);\n indexToReturn++;\n }\n }\n \n swap(array, indexToReturn, array.length - 1); \/\/ puts pivot where it belongs\n return indexToReturn;\n }\n \n private static void swap(int [] array, int i, int j) {\n int temp = array[i];\n array[i] = array[j];\n array[j] = temp;\n }\n \n private static void printArray(int[] array) {\n for (int num: array) {\n System.out.print(num + \" \");\n }\n System.out.println();\n }\n}\n<\/pre>\n\n\n\nNote:<\/strong> This problem