HackerRank Quicksort 1 - Partition Solution

In this post, we will solve HackerRank Quicksort 1 – Partition Problem Solution.

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running time of O(n²). 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.
Example
arr = [5, 7, 4, 3, 8]
In this challenge, the pivot will always be at arr[0], so the pivot is 5.
arr is divided into left = {4,3}, equal = {5}, and right = {7,8}. Putting them all together, you get {4, 3, 5, 7, 8}. There is a flexible checker that allows the elements of left and right to be in any order. For example, {3, 4, 5, 8, 7} is valid as well. 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 below.

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.

Sample Input

STDIN       Function
-----       --------
5           arr[] size n =5
4 5 3 7 2   arr =[4, 5, 3, 7, 2]

Sample Output

3 2 4 5 7

Explanation
arr = [4, 5, 3, 7, 2] Pivot: p = arr[0] = 4.
left = {}; equal = {4}; right = {}
arr[1] = 5>p, so it is added to right.
left = {}; equal = {4}; right = {5}
arr[2] = 3 p, so it is added to right.
left = {3}; equal = {4}; right = {5,7}
arr[4] = 2 <p, so it is added to left.
left = {3,2}; equal = {4}; right = {5,7}
Return the array {32457}.
The order of the elements to the left and right of 4 does not need to match this answer. It is only required that 3 and 2 are to the left of 4, and 5 and 7 are to the right

HackerRank Quicksort 1 - Partition Problem Solution — HackerRank Quicksort 1 – Partition Problem Solution

Quicksort 1 – Partition C Solution

#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 br[ar_size], p, i, j = 0;

  if (ar_size == 0 || ar_size == 1)
    return;

  p = ar[0];

  for (i = 1; i<ar_size; i++)
  {
    if (ar[i] <= p)
     br[j++] = ar[i];
  }

  br[j++] = p;

  for (i=1; i<ar_size; i++)
  {
    if (ar[i] > p)
      br[j++] = ar[i];
  }
    
  for (i=0; i < ar_size; i++)
{
  printf("%d ", br[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 C++ Solution

/*
Solution to the "QuickSort1" challenge by HackerRank:
https://www.hackerrank.com/challenges/quicksort1
by simba (szczerbiakadam@gmail.com).
*/

#include <iostream>
#include <vector>

int main(int argc, char **argv)
{
  std::vector<int> input;
  std::vector<int> lesser;
  std::vector<int> equal;
  std::vector<int> greater;

  int length;

  std::cin >> length;
  input.reserve(length);
  for (int i = 0; i < length; ++i)
  {
    int value;
    std::cin >> value;
    input.push_back(value);
  }

  // 0-th element is considered a pivot.
  equal.push_back(input.at(0));

  // Partitions the elements into three distinct vectors:
  for (int i = 1; i < length; ++i)
  {
    if (input.at(i) < input.at(0))
    {
      lesser.push_back(input.at(i));
    }
    else if (input.at(i) > input.at(0))
    {
      greater.push_back(input.at(i));
    }
    else
    {
      equal.push_back(input.at(i));
    }
  }

  // Prints out the answer:
  for (int i = 0; i < lesser.size(); ++i)
  {
    std::cout << lesser.at(i) << " ";
  }
  for (int i = 0; i < equal.size(); ++i)
  {
    std::cout << equal.at(i) << " ";
  }
  for (int i = 0; i < greater.size(); ++i)
  {
    std::cout << greater.at(i) << " ";
  }

  return 0;
}

Quicksort 1 – Partition C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
/* Head ends here */
static void partition(int[] ar) {

        int p = ar[0];
        LinkedList<int> lesser = new LinkedList<int>();
        LinkedList<int> greater = new LinkedList<int>();

        foreach (int x in ar)
        {
            if (x < p)
            {
                lesser.AddLast(x);
            }
            else
            {
                greater.AddLast(x);
            }
        }

        foreach (int x in lesser)
        {
            Console.Write("{0} ", x);
        }

        foreach (int x in greater)
        {
            Console.Write("{0} ", x);
        }
}
/* Tail starts here */
/* Tail starts here */
    static void Main(String[] args) {
           
           int _ar_size;
           _ar_size = Convert.ToInt32(Console.ReadLine());
           int [] _ar =new int [_ar_size];
           String elements = Console.ReadLine();
           String[] split_elements = elements.Split(' ');
           for(int _ar_i=0; _ar_i < _ar_size; _ar_i++) {
                  _ar[_ar_i] = Convert.ToInt32(split_elements[_ar_i]); 
           }

           partition(_ar);
    }
}

Quicksort 1 – Partition Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'quickSort' function below.
     *
     * The function is expected to return an INTEGER_ARRAY.
     * The function accepts INTEGER_ARRAY arr as parameter.
     */

    public static List<Integer> quickSort(List<Integer> arr) {
        // Write your code here
        if(arr.size()<2)
            return arr;
        int pivot = partition(arr);
        quickSort(arr.subList(0,pivot));
        quickSort(arr.subList(pivot+1,arr.size()));
        return arr;
    }

    private static int partition(List<Integer> arr){
        int pivot = arr.get(0);
        int start=0;
        int end = arr.size();

        while (start<end){
            while (start<end&&arr.get(--end)>=pivot);
            if(start<end)
                arr.set(start,arr.get(end));

            while (start<end&&arr.get(++start)<=pivot);
            if(start<end)
                arr.set(end,arr.get(start));
        }
        arr.set(end,pivot);

        return end;
    }


}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> arr = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                .map(Integer::parseInt)
                .collect(toList());

        List<Integer> result = Result.quickSort(arr);

        bufferedWriter.write(
                result.stream()
                        .map(Object::toString)
                        .collect(joining(" "))
                        + "\n"
        );

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Quicksort 1 – Partition JavaScript Solution

function solve(arr) {

    var comparisonElement = arr[0];
    var arrayWithoutComparisonElement = arr.splice(1);
    var leftArray = [];
    var rightArray = [];
    var outputString = '';
    for (var i = 0; i < arrayWithoutComparisonElement.length;i++){
        if (arrayWithoutComparisonElement[i] > comparisonElement) {
            rightArray.push(arrayWithoutComparisonElement[i]);
        } else {
            leftArray.push(arrayWithoutComparisonElement[i]);
        }
    }

    for (var j = 0; j < leftArray.length; j++) {
        outputString += leftArray[j] + ' ';
    }

    outputString += comparisonElement + ' ';

    for (var k = 0; k < rightArray.length; k++) {
        outputString += rightArray[k] + ' ';
    }

    return outputString;
}

function processData(input) {

    var lines = input.replace(/(\r\n|\n|\r)/gm, " ");
    var n = lines.substring(0, lines.indexOf(' '));
    var inputArray = lines.split(' ');
    inputArray.splice(0, 1);

    var numArr = [];
    for (var i = 0; i < inputArray.length; i++) {
        numArr.push(inputArray[i] * 1);

    }

    var result = solve(numArr);
    console.log(result);
}

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

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

Quicksort 1 – Partition Python Solution

if __name__ == '__main__':
    n = int(input())
    st = input().strip().split()
    p = int(st[0])
    ar = [int(i) for i in st[1:]]
    s = [e for e in ar if e<p]
    d = [e for e in ar if e>p]
    ans = s + [p,] + d
    print(*ans, sep=' ')

HackerRank Quicksort 1 – Partition Solution