Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 23 Dec, 2020

Moderate

```
Let the array = [ 4, 2, 1, 5, 3 ]
Let pivot to be the rightmost number.
```

```
The first line of input contains an integer 'T' denoting the number of queries or test cases.
The first line of each input consists of an integer 'N' denoting the size of the array.
The second line of each input consists of 'N' space-separated integers denoting the elements of the array.
```

```
For each test case, print a single line containing space-separated integers denoting the elements of the array after sorting.
The output of each test case will be printed in a separate line.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
Can you solve this in the worst case NlogN complexity?
```

```
1 <= T <= 10
1 <= N <= 10 ^ 3
-10 ^ 9 <= ARR[i] <= 10 ^ 9
Where 'T' is the number of test cases, 'N' is the length of the array 'ARR', and 'ARR[i]' is the array element at index i.
Time limit: 1 sec.
```

The first approach will be picking edge elements as pivot.

What needs to be done:

- Pick the rightmost element as pivot.
- Partition the array with numbers smaller than pivot on the left of pivot and numbers larger than pivot on the right of the pivot.
- Recursively sort both left and right partition.

The second approach will be picking a random element as pivot.

What needs to be done:

- Pick the random element in the given range of array as pivot.
- Partition the array with numbers smaller than pivot on the left of pivot and numbers larger than pivot on the right of the pivot.
- Recursively sort both left and right partition.

The third approach will be picking median as pivot and applying 3 - way quick sort.

What needs to be done:

- Pick the median of the given range of array as pivot using an optimized quick select algorithm.
- Partition the array with the left part has elements smaller than pivot, the center part has elements equal to pivot and the right part has elements larger than pivot.
- Recursively sort both left and right partition.

Similar problems

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Merge Two Sorted Arrays Without Extra Space

Moderate

Posted: 19 Nov, 2022

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Sort 0s, 1s, 2s

Easy

Posted: 24 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023