Quick Sort
You are given an array of integers. You need to sort the array in ascending order using quick sort.

Quick sort is a divide and conquer algorithm in which we choose a pivot point and partition the array into two parts i.e, left and right. The left part contains the numbers smaller than the pivot element and the right part contains the numbers larger than the pivot element. Then we recursively sort the left and right parts of the array.

Example:

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

After the 1st level partitioning the array will be { 2, 1, 3, 4, 5 } as 3 was the pivot. After 2nd level partitioning the array will be { 1, 2, 3, 4, 5 } as 1 was the pivot for the left part and 5 was the pivot for the right part. Now our array is sorted and there is no need to divide it again.

Input format:

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.

Output format:

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.

Note:

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

Follow Up

Can you solve this in the worst case NlogN complexity?

Constraints:

1

Question

Quick Sort

You are given an array of integers. You need to sort the array in ascending order using quick sort.

Quick sort is a divide and conquer algorithm in which we choose a pivot point and partition the array into two parts i.e, left and right. The left part contains the numbers smaller than the pivot element and the right part contains the numbers larger than the pivot element. Then we recursively sort the left and right parts of the array.

Example:

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

example

After the 1st level partitioning the array will be { 2, 1, 3, 4, 5 } as 3 was the pivot. After 2nd level partitioning the array will be { 1, 2, 3, 4, 5 } as 1 was the pivot for the left part and 5 was the pivot for the right part. Now our array is sorted and there is no need to divide it again.

Input format:

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.

Output format:

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.

Note:

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

Follow Up

Can you solve this in the worst case NlogN complexity?

Constraints:

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.

Accepted Answer

Algorithm :

QUICKSORT (array A, start, end) 
{ 
	if (start < end) 
	{ 
		p = partition(A, start, end) 
		QUICKSORT (A, start, p - 1) 
		QUICKSORT (A, p + 1, end) 
	} 
}

Partition Algorithm :

The partition algorithm rearranges the sub-arrays in a place.

PARTITION (array A, start, end) 
{ 
	pivot = A[end] 
	i = start-1 
	for j = start to end -1 
	{ 
		do if (A[j] < pivot) 
		{ 
			then i = i + 1 
			swap A[i] with A[j] 
		}
	} 
	swap A[i+1] with A[end] 
	return i+1 
}

Accepted Answer

Right most pivot

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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the array.

In the worst case, we are creating a recursive stack of size ‘N’.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the size of the array.

In the worst case, the pivot element will be the largest or smallest element and will make a partition of size (N - 1).

Accepted Answer

Random pivot

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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of the array.

In the worst case, we are creating a recursive stack of size ‘N’.

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where ‘N’ is the size of the array.

In the worst case, the pivot element will be the largest or smallest element and will make a partition of size (N - 1).

Accepted Answer

Median pivot

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.

Space Complexity: O(logn)Explanation:

O(log N), where ‘N’ is the size of the array.

In the worst case, we are creating a recursive stack of size log N.

Time Complexity: O(nlogn)Explanation:

O(N * log N) per test case where ‘N’ is the size of the array.

In the worst case, the array is partitioned into two parts of equal size so we created log N recursive levels.

You are given an array of integers. You need to sort the array in ascending order using quick sort.

Example:

After the 1st level partitioning the array will be { 2, 1, 3, 4, 5 } as 3 was the pivot. After 2nd level partitioning the array will be { 1, 2, 3, 4, 5 } as 1 was the pivot for the left part and 5 was the pivot for the right part. Now our array is sorted and there is no need to divide it again.

Input format:

Output format:

Note:

Follow Up

Constraints:

Top Capgemini Engineering Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Capgemini Engineering Software Developer