Quick Sort Algorithm

Quick sort is a sorting technique that has the ability to break a massive data array into smaller ones in order to save time. Here, in the case of the quick sort algorithm, an extensive array is divided into two arrays, one of which has values less than the specified value, say pivot. The pivot value is bigger than the other.

Table of Contents

• Working of Quicksort Algorithm
• Quick Sort Algorithm
  • Algorithm
  • Partition Algorithm
• Quicksort Time Complexity
• Quicksort Space Complexity
• Practice Problems

Working of Quick Sort Algorithm

Now, it’s time to see the working of a quick sort algorithm, and for that, we need to take an unsorted array.

Let the components of the array are –

Here,

L= Left

R = Right

P = Pivot

In the given series of arrays, let’s assume that the leftmost item is the pivot. So, in this condition, a[L] = 23, a[R] = 26 and a[P] = 23.

Since, at this moment, the pivot item is at left, so the algorithm initiates from right and travels towards left.

Now, a[P] < a[R], so the algorithm travels forward one position towards left, i.e. –

Now, a[L] = 23, a[R] = 18, and a[P] = 23.

Since a[P] > a[R], so the algorithm will exchange or swap a[P] with a[R], and the pivot travels to right, as –

Now, a[L] = 18, a[R] = 23, and a[P] = 23. Since the pivot is at right, so the algorithm begins from left and travels to right.

As a[P] > a[L], so algorithm travels one place to right as –

Now, a[L] = 8, a[R] = 23, and a[P] = 23. As a[P] > a[L], so algorithm travels one place to right as –

Now, a[L] = 28, a[R] = 23, and a[P] = 23. As a[P] < a[L], so, swap a[P] and a[L], now pivot is at left, i.e. –

Since the pivot is placed at the leftmost side, the algorithm begins from right and travels to left. Now, a[L] = 23, a[R] = 28, and a[P] = 23. As a[P] < a[R], so algorithm travels one place to left, as –

Now, a[P] = 23, a[L] = 23, and a[R] = 13. As a[P] > a[R], so, exchange a[P] and a[R], now pivot is at right, i.e. –

Now, a[P] = 23, a[L] = 13, and a[R] = 23. Pivot is at right, so the algorithm begins from left and travels to right.

Now, a[P] = 23, a[L] = 23, and a[R] = 23. So, pivot, left and right, are pointing to the same element. It represents the termination of the procedure.

Item 23, which is the pivot element, stands at its accurate position.

Items that are on the right side of element 23 are greater than it, and the elements that are on the left side of element 23 are smaller than it.

Now, in a similar manner, the quick sort algorithm is separately applied to the left and right sub-arrays. After sorting gets done, the array will be –

Quick Sort Algorithm

Algorithm:

QUICKSORT (array A, begin, finish)

{

1 if (begin < finish)

2 {

3 p = partition(A, begin, finish)

4 QUICKSORT (A, begin, p – 1)

5 QUICKSORT (A, p + 1, finish)

6 }

}

Partition Algorithm:

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

PARTITION (array A, begin, finish)

{

1 pivot ? A[finish]

2 i ? begin-1

3 for j ? begin to finish-1 {

4 do if (A[j] < pivot) {

5 then i ? i + 1

6 swap A[i] with A[j]

7 }}

8 swap A[i+1] with A[finish]

9 return i+1

}

Quicksort Time Complexity

Quicksort Space Complexity

Practice Problems

Q1.Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists, and each of them contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements, then:

A) T(n)<=2T(n/5)+n

B) T(n)<=T(n/5)+T(4n/5)+n

C) T(n)<=2T(4n/5)+n

D) T(n)<=2T(n/2)+n

Q2. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

A) O(n)

B) O(nlogn)

C) O(n2)

D) O(n2logn)

Q3. The running time of an algorithm is represented by the following recurrence relation:

otherwise

Which one of the following represents the time complexity of the algorithm?

A) O(n)

B) O(nlogn)

C) O(n2)

D) O(n2logn)

Q4. An array of n numbers is given, where n is an even number. The maximum, as well as the minimum of these n numbers, needs to be determined. Which of the following is TRUE about the number of comparisons needed?

A) At least 2n – c comparisons, for some constant c, are needed.

B) At most 1.5n – 2 comparisons are needed.

C) At least n log2 n comparisons are needed.

D) None of the above.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.

Also Explore,

• Algorithm
• Insertion Sort Algorithm
• Selection Sort Algorithm
• Heap Sort Algorithm
• Merge Sort Algorithm
• Greedy Algorithm
• Binary Search Algorithm
• Breadth-First Search
• Depth-First Search
• Recursive Algorithm
• Divide and Conquer Algorithm
• Dynamic Programming Algorithms