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>

/* Head ends here */
void partition(int ar_size, int *  ar) {

int f,temp=ar[0],j=0,k=0,i;
    int ar1[ar_size],ar2[ar_size];
    for(i=0;i<ar_size;i++)
    {
        if(ar[i]<temp)
        {
            ar1[j]=ar[i];
            j++;
        }
        if(ar[i]>temp)
        {
            ar2[k]=ar[i];
            k++;
           //printf("k=%d\n",k);
        }
       
    }
  /*  ar1[j]=temp;
    j++;
        for(i=0;i<k;i++)
        {
         ar1[j]=ar2[i];
            j++;
        }*/
   // printf("j=%d\n",j);
    for(i=0;i<j;i++)
    printf("%d ",ar1[i]);
    printf("%d ",temp);
    for(i=0;i<k;i++)
        printf("%d ",ar2[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;
}

 

Quicksort 1 – Partition HackerRank Solution in C++

#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;

/* Head ends here */

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;

}


/* Tail starts here */
int main() {
   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;
}

 

Quicksort 1 – Partition HackerRank Solution in Java

/* 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++;
            }
        }
    }   
}

 

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/

 

Leave a Comment