Header Ad

HackerRank Quicksort 1 - Partition problem solution

In this HackerRank Quicksort 1 - Partition, 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.

HackerRank Quicksort 1 - Partition problem solution


Problem solution in Python programming.

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))


Problem solution in Java Programming.

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 programming.

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);
});


Post a Comment

0 Comments