HackerRank Quicksort 1 – Partition problem solution

HackerRank Quicksort 1 – Partition problem solution – In this HackerRank Quicksort 1 – Partition, we have 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.

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.

HackerRank Quicksort 1 – Partition problem solution in Python.

def partition(elements):
    pivot = elements[0]
    left = []
    right = []
    for element in elements:
        if element<pivot:
            left.append(element)
        else:
            right.append(element)
    return left+right

n = [int(i) for i in input().strip().split()]
elements = [int(j) for j in input().strip().split()]
print(*partition(elements))

Quicksort 1 – Partition problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] ar = new int[N];
        int[] result = new int[N];
        int p = sc.nextInt();
        int pcount = 1, j = 0;
        for (int i = 1; i < N; i++) {
            ar[i] = sc.nextInt();
            if (ar[i] < p)
                result[j++] = ar[i];
            else if (ar[i] == p)
                pcount++;   
        }
        for (int i = 0; i < pcount; i++)
            result[j++] = p;
        
        for (int i = 1; i < N; i++) {
            if (ar[i] > p)
                result[j++] = ar[i];
        }
        
        for (int i : result)
            System.out.print(i + " ");
    }
}

Problem solution in C++ programming.

#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 swap(vector<int> &arr, int i, int j){
    if(i==j) return;
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

/* Head ends here */
void partition(vector <int>  ar) {
    int boundary =0, i=1, number_of_ele= ar.size(), tmp=0;
    while(i<number_of_ele){
        if(ar[i] < ar[0]) {
            tmp = ar[i];
            for(int j = i;j>boundary+1;j--){
                ar[j] = ar[j-1];
            }
            boundary++;
            ar[boundary] = tmp;
        }
        i++;
    }
    int pivot = ar[0];
    for(i=0;i<boundary;i++)
        ar[i] = ar[i+1];
    ar[boundary] = pivot;
    for(i =0; i < number_of_ele;i++){
        if(i < number_of_ele -1) cout<<ar[i]<<" ";
        else cout<<ar[i]<<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;
}

Problem solution in C programming.

#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 p = ar[0];
    int bi = 1;
    int pc = 1;
    for (int i = 1; i < ar_size; ++i) {
        int a = ar[i];
        if (a < p) printf("%d ", a);
        else if (a > p) ar[bi++] = ar[i];
        else pc++;
    }
    while (pc > 1) {
        printf("%d ", p);
        pc--;
    }
    printf("%d", p);
    for (int i = 1; i < bi; ++i) {
        printf(" %d", ar[i]);
    }
    printf("n");
}

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

Problem solution in JavaScript.

function processData(input) {

    //Enter your code here
    arrs = input.split("n");
    var arr = arrs[1].split(" ");
    var pivot = arr[0];
    pivotArray(parseInt(pivot), arr);
    } 
    function pivotArray(pivot, arr){
        var leftArr = [];
        var rightArr = [];
        for (var i = 0; i < arr.length; i++) {
            var testNum = parseInt(arr[i]);
            if (testNum < pivot) {
                leftArr.push(testNum);
            }        
            else if (testNum > pivot) {
                rightArr.push(testNum);
            }
        }
    var completeArr = [];
   completeArr = completeArr.concat(leftArr);
    completeArr.push(pivot);
   completeArr = completeArr.concat(rightArr);
    var pivotString = "";
    for(var j = 0; j < completeArr.length; j++){
        
    	pivotString = pivotString + completeArr[j];
        if(j != (completeArr.length-1)){
            pivotString = pivotString + " ";
    	}
    }
    console.log(pivotString);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});