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

# Head ends here
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();
        
        right.Add(p);
        right.AddRange(left);
    
        Console.WriteLine(String.Concat(right.Select(x => x.ToString() + " ")));
    }
    
    static void Main(String[] args)
    {   
        Console.ReadLine();
    
        Partition(Console.ReadLine().Trim().Split(' ').Select(x => Int32.Parse(x)).ToArray());
    }  
}

 

Attempt Quicksort 1 – Partition HackerRank Challenge

Link – https://www.hackerrank.com/challenges/quicksort1/

Next HackerRank Challenge Solution 

Link – https://exploringbits.com/pangrams-hackerrank-solution/