Quicksort 1 – Partition – HackerRank Solution

In this post, we will solve Quicksort 1 – Partition HackerRank Solution. This problem (Quicksort 1 – Partition) is a part of HackerRank Problem Solving series.

Task

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.

Constraints

• 1 <= n <= 1000
• -1000 <= arr[i] <= 1000 where 0 <= i < n
• All elements are distinct.

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 left.
left = {3}; equal = {4}; right = {5}

arr[3] = 7 > 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.

Solution – Quicksort 1 – Partition – HackerRank Solution

C++

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void partition(vector<int> arr) {
    
    int length = arr.size() - 1; // store length modded to be without p in next steps
    int p = arr.front(); // declare pivot
    arr.erase(arr.begin()); // erases pivot from array
    
    vector<int> left;
    vector<int> right;
    
    int i, n;
    
    for (i = 0; i < length; i++) {  
        (arr[i] > p) ? right.push_back(arr[i]) : left.push_back(arr[i]); 
    }
    
    for (i = 0, n = left.size(); i < n; i++)
        cout << left[i] << " ";
    
    cout << p << " ";
    
    for (i = 0, n = right.size(); i < n; i++)
        cout << right[i] << " ";
    cout << "\n";
    
}
int main(void) {
   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;
}

Python

import sys

def quickSort(arr):
    left = []
    equal = []
    right = []
    pivot = arr[0]
    
    for el in arr:
        if el < pivot:
            left.append(el)
        elif el == pivot:
            equal.append(el)
        elif el > pivot:
            right.append(el)
            
    return left + equal + right

if __name__ == "__main__":
    n = int(input().strip())
    arr = list(map(int, input().strip().split(' ')))
    result = quickSort(arr)
    print (" ".join(map(str, result)))

Java

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int s = scan.nextInt();
        int[] array = new int[s];
        for (int i = 0; i < s; i++) {
            array[i] = scan.nextInt(); 
        }
        scan.close();
        partition(array);
        printArray(array);
    }
    
    /* Partitions array into 2 parts. 
     *      1) Left side has values smaller than pivotValue
     *      2) Right side has values larger than pivotValue
     * Returns pivotIndex
     */
    public static int partition(int [] array) {
        int pivotIndex = 0; // not a great choice of pivot.
        int pivotValue = array[pivotIndex];
        
        swap(array, pivotIndex, array.length - 1); // put pivot at end for now.
        
        /* Linear search, comparing all elements to pivotValue and swapping as necessary */
        int indexToReturn = 0;
        for (int i = 0; i < array.length; i++){
            if (array[i] < pivotValue){
                swap(array, i, indexToReturn);
                indexToReturn++;
            }
        }
        
        swap(array, indexToReturn, array.length - 1); // puts pivot where it belongs
        return indexToReturn;
    }
    
    private static void swap(int [] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    private static void printArray(int[] array) {
        for (int num: array) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

Note: This problem (Quicksort 1 – Partition) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.