# Quicksort 1 Partition Hackerrank problem solution

##### Quicksort 1 Partition Hackerrank

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with an average case performance of O(n2). In these next few challenges, we’re covering a divide-and-conquer algorithm called Quicksort (also known as Partition Sort).

Step 1: Divide
Choose some pivot element, p, and partition your unsorted array, ar, 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.

Challenge
Given ar and p=ar[0], partition ar into left, right, and equal using the Divide instructions above. Then print each element in left followed by each element in equal, followed by each element in right on a single line. Your output should be space-separated.

Note: There is no need to sort the elements in-place; you can create two lists and stitch them together at the end.

Input Format

The first line contains n (the size of ar).
The second line contains n space-separated integers describing ar (the unsorted array). The first integer (corresponding to ar[0]) is your pivot element, p.

Constraints

1<=n<=1000
-10000<=x<=10000 x{ar}
All elements will be unique.
Multiple answers can exist for the given test case. Print any one of them.

Output Format

On a single line, print the partitioned numbers (i.e.: the elements in left, then the elements in equal, and then the elements in right). Each integer should be separated by a single space.
Sample Input

5
4 5 3 7 2

Sample Output

3 2 4 5 7

##### Solution
``````#!/bin/python

def partition(ar):
pivot = ar[0]
l = len(ar)

start_index = 0
end_index = l-1
new_ar = []

for i in range(1,l):
if ar[i] <= pivot:
new_ar.append(ar[i])
new_ar.append(pivot)
for i in range(1,l):
if ar[i] > pivot:
new_ar.append(ar[i])

print '%s' % ' '.join(map(str, new_ar))
return ""

# Tail starts here

m = input()
ar = [int(i) for i in raw_input().strip().split()]
partition(ar)``````
```#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
void partition(vector <int>  ar) {
int p=ar[0];
vector <int> l, r;
for(int i=0; i<ar.size(); i++) {
int x=ar[i];
if (p>ar[i])
l.push_back(x);
else if(p<ar[i])
r.push_back(x);
}
if(!l.empty()){
for (int x = 0; x != l.size(); x++)
cout<<l[x]<<" ";}
cout<<p<<" ";
for (int x = 0; x != r.size(); x++)
cout<<r[x]<<" ";

}
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;
}
```
``````#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

void partition(int ar_size, int *  ar)
{
int left[ar_size];
int right[ar_size];
int pivot=ar[0];
int j,k=0;
for(int i=1;i<ar_size;i++)
{
if(ar[i]<pivot)
{
left[j]=ar[i];
j++;
}
else
{
right[k]=ar[i];
k++;
}
}
//j=0;k=0;
for(int i=0;i<j;i++)
{
ar[i]=left[i];
}
ar[j]=pivot;
for(int i=0;i<k;i++)
{
ar[i+j+1]=right[i];
}
for(int i=1;i<=ar_size;i++)
{
printf("%d ",ar[i]);
}
}

/* Tail starts here */
int main() {

int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) {
scanf("%d", &_ar[_ar_i]);
}

partition(_ar_size, _ar);

return 0;
}``````
``````/* Head ends here */
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] ar = new int[n];
for(int i=0;i<n;i++){
ar[i]=in.nextInt();
}
partition(ar);
printArray(ar);
}
static void printArray(int[] ar) {
for(int n: ar){
System.out.print(n+" ");
}
System.out.println("");
}
static void partition(int[] ar) {
int p=ar[0];
int[] copy=Arrays.copyOf(ar, ar.length);
int c=0;
for(int i=1;i<ar.length;i++){
if(copy[i]<=p){
ar[c]=copy[i];
c++;
}
}
ar[c]=p;
c++;
for(int j=0;j<ar.length;j++){
if(copy[j]>p){
ar[c]=copy[j];
c++;
}
}
}
}

``````

### hasectic

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

### 2 comments: On Quicksort 1 Partition Hackerrank problem solution

• naturally like your web-site but you have to check the spelling on quite a few of your posts. A number of them are rife with spelling problems and I find it very bothersome to tell the truth nevertheless I will surely come back again.

• we will definitely take care of that! Thank you .