We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Quicksort 1 - Partition

Quicksort 1 - Partition

Problem
Submissions
Leaderboard
Discussions

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running time of . 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, , and partition your unsorted array, , into three smaller arrays: , , and , where each element in , each element in , and each element in .

Example

In this challenge, the pivot will always be at , so the pivot is .

is divided into , , and .
Putting them all together, you get . There is a flexible checker that allows the elements of and to be in any order. For example, is valid as well.

Given and , partition into , , and using the Divide instructions above. Return a 1-dimensional array containing each element in first, followed by each element in , followed by each element in .

Function Description

Complete the quickSort function in the editor below.

quickSort has the following parameter(s):

  • int arr[n]: is the pivot element

Returns

  • int[n]: an array of integers as described above

Input Format

The first line contains , the size of .
The second line contains space-separated integers (the unsorted array). The first integer, , is the pivot element, .

Constraints

  • where
  • 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

Pivot: .
; ;

, so it is added to .
; ;

, so it is added to .
; ;

, so it is added to .
; ;

, so it is added to .
; ;

Return the array .

The order of the elements to the left and right of does not need to match this answer. It is only required that and are to the left of , and and are to the right.

Author

HackerRank

Difficulty

Easy

Cutoff Score

10.00

Max Score

10

Submitted By

106182

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy