- Prepare
- Algorithms
- Sorting
- Quicksort 1 - Partition

# Quicksort 1 - Partition

# Quicksort 1 - Partition

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.