Quick Sort

Quick Sort is a divide-and-conquer sorting algorithm. It works by selecting a pivot element, then partitioning the array so that:

• All elements less than the pivot are moved to its left
• All elements greater than the pivot are moved to its right

Then, the same process is applied recursively on the left and right subarrays.

How Quick Sort Works?

• Choose a pivot element.
• Partition the array: move elements smaller than pivot to left, greater to right.
• Recursively apply Quick Sort to the subarrays.

Example: Quick Sort

Sorting the array [10, 7, 8, 9, 1, 5] using Quick Sort

Step 1: Choose Pivot (Last Element)

• Pivot = 5
• Partition the array so elements < 5 go to left, > 5 to right

Partitioning:

Compare each element to pivot:

• 10 > 5 → ignore
• 7 > 5 → ignore
• 8 > 5 → ignore
• 9 > 5 → ignore
• 1 < 5 → move 1 to the left side

After Partition: [1] [5] [10, 7, 8, 9]

Step 2: Recursively sort left and right subarrays

Left: [1] → Already sorted

Right: [10, 7, 8, 9], pivot = 9

Partition:

• 10 > 9 → ignore
• 7 < 9 → move to left
• 8 < 9 → move to left

Result: [7, 8] [9] [10]

Final Sorted Array: [1, 5, 7, 8, 9, 10]

Advantages of Quick Sort

• Fastest in practice for large datasets
• In-place sort (no need for extra array)
• Efficient for randomized or large data

Disadvantages

• Not stable (equal elements may reorder)
• Worst case time is O(n²)
• Can cause stack overflow with large recursion depth

When to Use Quick Sort

• Sorting large datasets
• When average performance matters more than worst-case
• When you want to sort in-place

Time and Space Complexity

Space Complexity: O(log n) due to recursive stack (no extra arrays used)

C Program of Quick Short

#include <stdio.h>
int partition(int a[], int beg, int end);
void quickSort(int a[], int beg, int end);
void main()
 {
 	int i;
 	int arr[10]={90,23,101,45,65,23,67,89,34,23};
 	quickSort(arr, 0, 9);
 	printf("\n The sorted array is: \n");
 	for(i=0;i<10;i++)
 	printf(" %d\t", arr[i]);
 }
 	int partition(int a[], int beg, int end)
 	{

 		int left, right, temp, loc, flag;
 		loc = left = beg;
 		right = end;
 		flag = 0;
 		while(flag != 1)
 		{
 			while((a[loc] <= a[right]) && (loc!=right))
 			right--;
 			if(loc==right)
 			flag =1;
 			else if(a[loc]>a[right])
 			{
 				temp = a[loc];
 				a[loc] = a[right];
 				a[right] = temp;
 				loc = right;
 			}
 			if(flag!=1)
 			{
 		while((a[loc] >= a[left]) && (loc!=left))
 		left++;
 		if(loc==left)
 		flag =1;
 		else if(a[loc] <a[left])
 		{
 			temp = a[loc];
 			a[loc] = a[left];
 			a[left] = temp;
 			loc = left;
 		}
 	}
  }
  return loc;
 }
 void quickSort(int a[], int beg, int end)
 {
 	int loc;
 	if(beg<end)
 	{
 		loc = partition(a, beg, end);
 		quickSort(a, beg, loc-1);
 		quickSort(a, loc+1, end);
 	}
 } 

Output:

The sorted array is: 
23 
23 
23 
34 
45 
65 
67 
89 
90 
101

Numerical Questions Quick Sort

1. Use Quick Sort to sort [25, 17, 31, 13, 2]. Show pivot and each partitioning step.

2. Sort [9, 8, 7, 6, 5] with Quick Sort. Show worst-case behavior.

3. Apply Quick Sort on [15, 22, 13, 27, 12, 10, 20] Use last element as pivot

4. Sort this array using Quick Sort and track recursion: [3, 6, 8, 10, 1, 2, 1]