Data Structure & Algorithm Prof.
Muzamil Umar (KFGC)
Quick Sort
(Considering Last Element as Pivot)
1. Introduction
Quick Sort is a Divide and Conquer sorting algorithm.
It works by selecting a pivot element, placing it in its correct sorted position, and
dividing the array into two parts.
• Elements smaller than pivot → left side
• Elements greater than pivot → right side
Then the same process is applied recursively to both sides.
2. Steps of Quick Sort
1. Choose the last element as pivot
2. Rearrange the array so that:
o Smaller elements come before pivot
o Larger elements come after pivot
3. Pivot gets its correct position
4. Recursively apply Quick Sort to:
o Left subarray
o Right subarray
3. Example: Quick Sort (Last Element as Pivot)
Array:
[8, 3, 1, 7, 0, 10, 2]
Pivot = 2
Step 1: Partition
Compare elements with pivot 2.
Result:
[1, 0 | 2 | 8, 3, 7, 10]
Data Structure & Algorithm Prof. Muzamil Umar (KFGC)
Recursive calls on:
Left → [1, 0]
Right → [8, 3, 7, 10]
Step 2: Sort Left Subarray
Array: [1, 0]
Pivot = 0
Result:
[0 | 1]
Step 3: Sort Right Subarray
Array: [8, 3, 7, 10]
Pivot = 10
Result:
[8, 3, 7 | 10]
Recursive call on:
[8, 3, 7]
Step 4: Next Partition
Array: [8, 3, 7]
Pivot = 7
Result:
[3 | 7 | 8]
Final Sorted Array
[0, 1, 2, 3, 7, 8, 10]
7. Algorithm
QuickSort(arr, low, high)
1. if (low < high)
Data Structure & Algorithm Prof. Muzamil Umar (KFGC)
2. pivotIndex = partition(arr, low, high)
3. QuickSort(arr, low, pivotIndex-1)
4. QuickSort(arr, pivotIndex+1, high)
8. C++ Implementation
#include <iostream> // Library for input/output
using namespace std; // Allows use of standard names like cout
// Function to partition the array
int partition(int arr[], int low, int high)
{
int pivot = arr[high]; // Select the last element as pivot
int i = low - 1; // Index of smaller element
for(int j = low; j < high; j++) // Traverse array from low to high-1
{
if(arr[j] < pivot) // If current element is smaller than pivot
{
i++; // Move index of smaller element forward
swap(arr[i], arr[j]); // Swap smaller element to correct position
}
}
swap(arr[i+1], arr[high]); // Place pivot in its correct position
return i+1; // Return pivot index
}
// Function to perform Quick Sort
void quickSort(int arr[], int low, int high)
{
if(low < high) // Check if there are at least two elements
{
int pi = partition(arr, low, high); // Find pivot index after partition
quickSort(arr, low, pi-1); // Recursively sort left subarray
quickSort(arr, pi+1, high); // Recursively sort right subarray
}
}
Data Structure & Algorithm Prof. Muzamil Umar (KFGC)
// Main function
int main()
{
int arr[] = {8,3,1,7,0,10,2}; // Unsorted array
int n = 7; // Size of array
quickSort(arr,0,n-1); // Call Quick Sort function
for(int i=0;i<n;i++) // Loop to print sorted array
cout<<arr[i]<<" "; // Display elements
return 0; // End of program
}
9. Time Complexity
Case Complexity
Best Case O(n log n)
Average Case O(n log n)
Worst Case O(n²)
Worst case happens when the array is already sorted.
10. Advantages
✔ Very fast for large datasets
✔ Uses divide and conquer
✔ In-place sorting
11. Disadvantages
✖ Worst case O(n²)
✖ Not a stable sorting algorithm
Data Structure & Algorithm Prof. Muzamil Umar (KFGC)
MCQs
1. Quick Sort is based on which technique?
A) Dynamic Programming
B) Divide and Conquer
C) Greedy Method
D) Backtracking
Answer: B
2. In Quick Sort, the element used to divide the array is called:
A) Key
B) Pivot
C) Root
D) Index
Answer: B
3. In the given implementation, which element is chosen as pivot?
A) First element
B) Middle element
C) Last element
D) Random element
Answer: C
4. The function used to place the pivot in its correct position is:
A) sort()
B) partition()
C) merge()
D) divide()
Answer: B
5. Average time complexity of Quick Sort is:
A) O(n)
B) O(log n)
C) O(n log n)
D) O(n²)
Answer: C
6. Worst case time complexity of Quick Sort is:
A) O(n)
B) O(n log n)
Data Structure & Algorithm Prof. Muzamil Umar (KFGC)
C) O(n²)
D) O(log n)
Answer: C
7. Best case time complexity of Quick Sort is:
A) O(n log n)
B) O(n²)
C) O(n)
D) O(log n)
Answer: A
8. Quick Sort is generally faster than Bubble Sort because:
A) It uses hashing
B) It divides the problem into smaller subproblems
C) It avoids comparisons
D) It uses extra memory
Answer: B
9. Quick Sort is:
A) Stable sorting algorithm
B) Not stable by default
C) Always stable
D) Only stable for integers
Answer: B
10. Quick Sort is an example of:
A) Recursive algorithm
B) Iterative algorithm
C) Linear algorithm
D) Greedy algorithm
Answer: A
11. In Quick Sort, elements smaller than pivot are placed:
A) Right side
B) Left side
C) Randomly
D) In another array
Answer: B
12. In Quick Sort, elements greater than pivot are placed:
A) Left side
B) Right side
C) At the beginning
Data Structure & Algorithm Prof. Muzamil Umar (KFGC)
D) In another array
Answer: B
13. Space complexity of Quick Sort due to recursion is:
A) O(1)
B) O(log n)
C) O(n)
D) O(n²)
Answer: B
14. Quick Sort performs best when:
A) Pivot divides array into equal halves
B) Pivot is always smallest
C) Pivot is always largest
D) Array is empty
Answer: A
15. Worst case occurs in Quick Sort when:
A) Pivot divides array evenly
B) Array is already sorted and pivot is first/last element
C) Array size is small
D) Array contains duplicates
Answer: B
16. Quick Sort is an example of:
A) In-place sorting algorithm
B) Out-of-place sorting algorithm
C) External sorting
D) Hash-based sorting
Answer: A
17. After partitioning, pivot element will be:
A) At random position
B) At correct sorted position
C) At beginning of array
D) At end of array
Answer: B
18. Quick Sort works well for:
A) Large datasets
B) Small datasets only
C) Linked lists only
D) Graphs only
Answer: A
Data Structure & Algorithm Prof. Muzamil Umar (KFGC)
19. The recursive calls in Quick Sort are applied to:
A) Entire array again
B) Left and right subarrays
C) Only left subarray
D) Only right subarray
Answer: B
20. Which of the following sorting algorithms uses the partition method?
A) Merge Sort
B) Quick Sort
C) Selection Sort
D) Insertion Sort
Answer: B