QUICK SORT - Analysis and Design of Algorithms
1. Introduction:
Quick Sort is a widely used and efficient sorting algorithm developed by Tony Hoare in 1959. It
employs a divide-and-conquer strategy to sort elements. The main concept involves selecting a
'pivot' element and partitioning the array into two sub-arrays according to whether they are less than
or greater than the pivot.
2. Problem Statement:
Given an array of n elements, sort the elements in ascending order using the Quick Sort algorithm.
3. Technique:
Quick Sort works by selecting a pivot element from the array. The partition process rearranges the
elements so that all elements less than the pivot are on the left and all greater are on the right. This
process is recursively applied to the sub-arrays.
4. Steps:
- Choose a pivot element.
- Partition the array around the pivot.
- Recursively apply the above steps to the sub-arrays.
5. Algorithm:
QUICKSORT(arr, low, high)
if low < high
pi = PARTITION(arr, low, high)
QUICKSORT(arr, low, pi-1)
QUICKSORT(arr, pi+1, high)
PARTITION(arr, low, high)
pivot = arr[high]
i = low - 1
for j = low to high - 1
if arr[j] < pivot
i=i+1
swap arr[i] and arr[j]
swap arr[i+1] and arr[high]
return i + 1
6. Implementation in C:
#include <stdio.h>
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
swap(&arr[i + 1], &arr[high]);
return (i + 1);
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
7. Implementation in Python:
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print("Sorted array is:", arr)
8. Implementation in Java:
public class QuickSort {
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
void sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
public static void main(String args[]) {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n - 1);
System.out.println("Sorted array:");
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
9. Expected Output:
Sorted array: 1 5 7 8 9 10
10. Advantages:
- Faster in practice than other O(n log n) algorithms.
- In-place sort (does not require extra space).
11. Disadvantages:
- Worst-case performance is O(n^2).
- Unstable sort (relative order of equal sort items is not preserved).
12. Real-World Applications:
- Used in commercial applications like Oracle, Unix, and databases.
- Suitable for large datasets with good average-case performance.
13. Conclusion:
Quick Sort is one of the most efficient and commonly used sorting algorithms due to its
average-case efficiency and simplicity. Although it suffers from worst-case performance in specific
scenarios, it remains popular due to its in-place nature and ease of implementation. With proper
pivot selection (e.g., using median-of-three or random pivot), its performance can be significantly
improved, making it an excellent choice in many real-world applications.
