Partitioning and Sorting Arrays with Many Repeated Entries

Easy
0/40
Average time to solve is 15m
profile
Contributed by
12 upvotes
Asked in company
HSBC

Problem statement

You’re given an array with many repeated values. Your task is to sort this array efficiently.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains an integer N, the size of the array.

The second line of each test case contains N space-separated integers, the elements present in the array.
Output Format : 
For every test case, the only line of output should contain N space-separated integers in sorted order.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <=  N <= 10^5
10^-9<= arr[i] <= 10^9

Time limit: 1 sec
Sample Input 1 :
1
4
3 1 2 4
Sample Output 1 :
1 2 3 4
Explanation of Sample Input 1 :
‘1 2 3 4’, is the sorted array for the given input.
Sample Input 2 :
2
6
3 4 1 6 2 5
5
3 5 8 9 11
Sample Output 2 :
1 2 3 4 5 6
3 5 8 9 11
Explanation of Sample Input 2 :
‘1 2 3 4 5 6’ and  ‘3 5 8 9 11’ are the sorted arrays for the given inputs.
Hint

Divide and Conquer

Approaches (3)
Quick Sort Based Approach

In the QuickSort Algorithm, we do the partitioning of the array into smaller arrays. We partition our array into two smaller arrays such that elements of one sub-array are smaller than the pivot element and the elements of the other sub-array are greater than the pivot element.

 

Algorithm:

  1. Create a helper function quickSortHelper() to partition the array, which will have three parameters, given our array, an integer low, and an integer high.
    1. Select any value of the array and name it as “pivot”. Let’s assume the last element of the array(arr[high]) as our pivot.
    2. Make an integer variable named ‘small’ which will have an index of the smallest element i.e low-1.
    3. Then run a loop from low to (high - 1) and for elements check if their value is greater than or less than the pivot. If their value is less, then increment ‘small’ and then swap that element with ‘small’.
    4. After exiting this loop and swapping arr[small+1] with arr[high], return the partitioning index i.e small+1.
  2. In the function quickSort, we’ll also have three arguments i.e our array, an integer low, and an integer high.
    1. If low < high, then in order to sort the smaller elements and the greater elements we make an integer variable partitonIndex  = quickSortHelper(arr, low, high).
    2. Then one by one, sort the elements before partition by calling quickSortHelper(arr, low, partitonIndex -1), and after partition by calling quickSortHelper(arr, partitionIndex + 1, high).
Time Complexity

O(N^2),  where ‘N’ is the number of elements in the given array.

 

When the pivot element is chosen such that it lies to either side of the array, it will make one empty array and another array with N-1 elements. Therefore the quick sort algorithm will be called on this array with N - 1 elements only. The recursive call for these N -1 elements will take N - 1 time, then for N - 2 elements, it will take N - 2 time, and it continues like that. Hence, the worst time complexity becomes O(N^2).

Space Complexity

O(N),  where ‘N’ is the number of elements in the given array.

 

In the worst case, we have N recursive calls in the stack space. Thus, the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Partitioning and Sorting Arrays with Many Repeated Entries
Full screen
Console