# Quicksort 1 – Partition HackerRank Solution in C, C++, Java, Python

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running time of O(n^2). 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.

For example: Assume arr=[5,7,4,3,8]

The pivot is at arr[0] = 5

is divided into left ,equal , and right .

Function Description

Complete the quickSort function in the editor below. It should return an array of integers as described above.

quickSort has the following parameter(s):

• arr: an array of integers where arr[0] is the pivot element

Input Format

The first line contains n, the size of the array arr.

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

Constraints

• 1<=n<=1000
• 1000<=arr[i]<=1000 where 0<=i<=n
• All elements will be unique.

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`

## Quicksort 1 – Partition HackerRank Solution in C

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

void partition(vector <int>  ar) {
if(ar.size() == 0)
return;
else if(ar.size() == 1){
cout << ar[0] << endl;
return;
}

int p = ar[0];
vector<int> less;
vector<int> more;

for(vector<int>::iterator itr = ar.begin() + 1; itr != ar.end(); itr++){
if(*itr < p)
less.push_back(*itr);
else
more.push_back(*itr);
}

for(vector<int>::iterator itr = less.begin(); itr != less.end(); itr++)
cout << *itr << " ";
cout << p << " ";
for(vector<int>::iterator itr = more.begin(); itr != more.end(); itr++)
cout << *itr << " ";
cout << endl;

}

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++;
}
}
}
}
```

## Quicksort 1 – Partition HackerRank Solution in Python

```#!/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)```

## Quicksort 1 – Partition HackerRank Solution in C#

```using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution
{
static void Partition(int[] array)
{
int p = array[0];
List<int> right = array.Where(x => x < p).ToList();
List<int> left = array.Where(x => x > p).ToList();

Console.WriteLine(String.Concat(right.Select(x => x.ToString() + " ")));
}

static void Main(String[] args)
{

}
}```

Attempt Quicksort 1 – Partition HackerRank Challenge

Next HackerRank Challenge Solution