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
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Quicksort 1 - Partition

Quicksort 1 - Partition

Problem
Submissions
Leaderboard
Discussions
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Quicksort 1 - Partition
Exit Full Screen View
  • 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.

  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy