# Quicksort 1 – Partition – HackerRank Solution

In this post, we will solve Quicksort 1 – Partition HackerRank Solution. This problem (Quicksort 1 – Partition) is a part of HackerRank Problem Solving series.

The previous challenges coveredÂ Insertion Sort, which is a simple and intuitive sorting algorithm with a running time ofÂ O(n2). In these next few challenges, we’re covering aÂ divide-and-conquerÂ algorithm calledÂ QuicksortÂ (also known asÂ Partition Sort). This challenge is a modified version of the algorithm that only addresses partitioning. It is implemented as follows:

Step 1: Divide
Choose some pivot element,Â p, and partition your unsorted array,Â arr, into three smaller arrays:Â left,Â right, andÂ equal, where each element inÂ left < p, each element inÂ right > p, and each element inÂ equal = p.

Example

arr = [5, 7, 4, 3, 8]

In this challenge, the pivot will always be atÂ arr[0], so the pivot isÂ 5.

arrÂ is divided intoÂ left = {4, 3},Â equal = {5}, andÂ right = {7, 8}.
Putting them all together, you getÂ {4, 3, 5, 7, 8}. There is a flexible checker that allows the elements ofÂ leftÂ andÂ rightÂ to be in any order. For example,Â {3, 4, 5, 8, 7}Â is valid as well.

GivenÂ arrÂ andÂ p = arr[0], partitionÂ arrÂ intoÂ left,Â right, andÂ equalÂ using theÂ DivideÂ instructions above. Return a 1-dimensional array containing each element inÂ leftÂ first, followed by each element inÂ equal, followed by each element inÂ right.

Function Description

Complete the quickSort function in the editor below.

quickSort has the following parameter(s):

• int arr[n]:Â arr[0]Â is the pivot element

Returns

• int[n]:Â an array of integers as described above

## Input Format

The first line containsÂ n, the size ofÂ arr.
The second line containsÂ nÂ space-separated integersÂ arr[i]Â (the unsorted array). The first integer,Â arr[0], is the pivot element,Â p.

## Constraints

• 1 <= n <= 1000
• -1000 <= arr[i] <= 1000 where 0 <= i < n
• All elements are distinct.

Sample Input

``````STDIN       Function
-----       --------
5           arr[] size n =5
4 5 3 7 2   arr =[4, 5, 3, 7, 2]``````

Sample Output

``3 2 4 5 7``

Explanation

arr = [4, 5, 3, 7, 2]Â Pivot:Â p = arr[0] = 4.
left = {};Â equal = {4}; right = {}Â

arr[1] = 5 > p, so it is added to right.
left = {}; equal = {4}; right = {5}

arr[2] = 3 < p, so it is added toÂ left.
left = {3};Â equal = {4};Â right = {5}

arr[3] = 7 > p, so it is added toÂ right.
left = {3};Â equal = {4};Â right = {5, 7}

arr[4] = 2 < p, so it is added toÂ left.
left = {3, 2};Â equal = {4};Â right = {5, 7}

Return the arrayÂ {32457}.

The order of the elements to the left and right ofÂ 4Â does not need to match this answer. It is only required thatÂ 3Â andÂ 2Â are to the left ofÂ 4, andÂ 5Â andÂ 7Â are to the right.

## Solution – Quicksort 1 – Partition – HackerRank Solution

### C++

```#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void partition(vector<int> arr) {

int length = arr.size() - 1; // store length modded to be without p in next steps
int p = arr.front(); // declare pivot
arr.erase(arr.begin()); // erases pivot from array

vector<int> left;
vector<int> right;

int i, n;

for (i = 0; i < length; i++) {
(arr[i] > p) ? right.push_back(arr[i]) : left.push_back(arr[i]);
}

for (i = 0, n = left.size(); i < n; i++)
cout << left[i] << " ";

cout << p << " ";

for (i = 0, n = right.size(); i < n; i++)
cout << right[i] << " ";
cout << "\n";

}
int main(void) {
vector <int>  _ar;
int _ar_size;
cin >> _ar_size;
for(int _ar_i=0; _ar_i<_ar_size; _ar_i++) {
int _ar_tmp;
cin >> _ar_tmp;
_ar.push_back(_ar_tmp);
}

partition(_ar);

return 0;
}
```

### Python

```import sys

def quickSort(arr):
left = []
equal = []
right = []
pivot = arr[0]

for el in arr:
if el < pivot:
left.append(el)
elif el == pivot:
equal.append(el)
elif el > pivot:
right.append(el)

return left + equal + right

if __name__ == "__main__":
n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
result = quickSort(arr)
print (" ".join(map(str, result)))
```

### Java

```import java.util.Scanner;

public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int s = scan.nextInt();
int[] array = new int[s];
for (int i = 0; i < s; i++) {
array[i] = scan.nextInt();
}
scan.close();
partition(array);
printArray(array);
}

/* Partitions array into 2 parts.
*      1) Left side has values smaller than pivotValue
*      2) Right side has values larger than pivotValue
* Returns pivotIndex
*/
public static int partition(int [] array) {
int pivotIndex = 0; // not a great choice of pivot.
int pivotValue = array[pivotIndex];

swap(array, pivotIndex, array.length - 1); // put pivot at end for now.

/* Linear search, comparing all elements to pivotValue and swapping as necessary */
int indexToReturn = 0;
for (int i = 0; i < array.length; i++){
if (array[i] < pivotValue){
swap(array, i, indexToReturn);
indexToReturn++;
}
}

swap(array, indexToReturn, array.length - 1); // puts pivot where it belongs
return indexToReturn;
}

private static void swap(int [] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

private static void printArray(int[] array) {
for (int num: array) {
System.out.print(num + " ");
}
System.out.println();
}
}
```

Note: This problem (Quicksort 1 – Partition) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.