Quick Sort Algorithm in C: Step-by-Step Explanation

One of the fastest and most efficient ways of sorting elements in C is Quick Sort. From the array, it chooses one element which is called the pivot, and then it divides the rest of the elements such that those less than the pivot are placed on its left and those which are greater than the pivot are placed on its right. The partitioning is a term that is used for this operation.

The Quick Sort in C, after that, divides the left and right parts of the array, continues with the same process to further split the array until the order of each part is known. The technique is called recursion, which, by dividing the steps, makes it possible to sort the entire array.

Simply put, Quick Sort is a great answer, especially because, unlike some other methods of sorting (such as Merge Sort), it does not require additional space. It performs the sorting on the very same array, thus the method is both memory efficient and quicker when dealing with large data sets.

Algorithm For Quick Sort in C

Quick Sort is among the most widely used and effective sorting algorithms in programming. It applies the divide and conquer rule to sort elements rapidly, even in big data sets. Here is the quick sort algorithm in C language explained.

1. Choose a Pivot Element

The first step in an algorithm for quick sort in C is to select a pivot. It is simply a single element from the array. The first, last, or middle element can be chosen, or you can choose at random. The pivot decision does not alter the logic, but it may have an impact on performance.

2. Rearrange the Array Around the Pivot (Partitioning)

After selecting the pivot, the next job is to rearrange the array. The concept is to place all the elements that are less than the pivot on the left of the pivot and all the elements that are greater than the pivot on the right of the pivot.

• The pivot is now at its final, correctly sorted position.
• This is called partitioning the array.

3. Recursively Apply Quick Sort

Once the pivot is set correctly and the array has been divided into two parts, we perform the same action recursively for the left and right segments:

• The left subarray (all entries smaller than the pivot) should be sorted using Quick Sort.
• To the right subarray (all elements larger than the pivot), apply Quick Sort.

4. Base Case of Recursion

Until the subarrays are so small, one element or none at all, that they are deemed to have already been sorted, the recursion continues. This time, the algorithm halts, and the whole array is sorted.

How to Choose a Pivot Element in Quick Sort

Choosing a suitable pivot element in a quick sort C algorithm is extremely crucial since this factor alone determines the speed and efficiency of sorting. A good pivot allows a more balanced division of the data, thus resulting in faster sorting. Below are a few popular methods of selecting the pivot:

1. First or Last Element

This method simply picks either the first or last element in the array as the pivot.

• Why it's used: It's very easy to implement.
• Drawback: This strategy might make Quick Sort difficult if the data is already sorted or almost sorted.

2. Random Element

In this approach, a pivot is chosen randomly from the array.

• Why it's used: It lowers the chance of hitting the worst-case performance with sorted or patterned data.
• Drawback: It adds a tiny bit of randomness and overhead, but it usually helps more than it hurts.

3. Median-of-Three

This strategy takes the first, middle, and last elements of the array, finds the median (middle value among the three), and uses it as the pivot.

• Why it's used: It gives a more balanced split of the array most of the time, helping Quick Sort run efficiently.
• Drawback: Slightly more code and logic to write, but the performance boost is often worth it.

Why Choosing A Good Pivot Matters

The performance of the Quick Sort in C code is highly affected by the choice of a pivot element. The pivot is an element that is used to break the input array into two halves, recursively, thus eventually the whole array is sorted. If your choice of the pivot is not good, Quick Sort can become really slow.

For instance, consider the case when you pick the smallest or largest value as the pivot in an already sorted or almost sorted array. Your splits will be very uneven, and one sub-array will have almost all of the elements, whereas the other sub-array will have very few. This will bring about many more recursive calls, and the algorithm can slow down to a worst-case time complexity of O(n).

In fact, if the pivot divides the array into two almost equal halves, then each step of sorting is both justified and efficient. Thus, the recursion depth is kept low; the algorithm can thus work at its average-case time of O(n log n), which is much faster and better for larger datasets.

Let’s understand how Quick Sort in C works using a simple example.

Initial Array

10, 70, 40, 90, 50

Step 1: Choosing a Pivot

In this example, we choose the last element of the array as the pivot.

Pivot = 50

The pivot is used as a reference point to divide the array into two parts:

• Elements smaller than the pivot
  
• Elements greater than the pivot
  

Step 2: Partitioning Around the Pivot

We rearrange the array so that all elements smaller than the pivot appear before it, and all elements larger than the pivot appear after it.

After partitioning:

10, 40, 50, 90, 70

• Left subarray: [10, 40]
  
• Pivot: 50
  
• Right subarray: [90, 70]
  

Step 3: Recursive Sorting of Subarrays

Quick Sort is now applied to both subarrays.

Left subarray [10, 40]:

• Already sorted
  
• No further changes required
  

Right subarray [90, 70]:

• Choose the last element as pivot → 70
  
• Rearrange elements
  

After partitioning:

70, 90

Step 4: Final Sorted Array

After combining the sorted left subarray, pivot, and sorted right subarray, the final sorted array becomes:

10, 40, 50, 70, 90

Final Output

10, 40, 50, 70, 90

Note:

Quick Sort works by selecting a pivot, partitioning the array around it, and recursively sorting the subarrays until the entire array is sorted.

The partitioning process is the heart of the Quick Sort algorithm. It determines how the array is divided and rearranged around a chosen pivot element during each recursive step.

How Partitioning Works

1. Select a Pivot Element:
   Typically, the last element in the current subarray is chosen as the pivot, but other strategies are possible.
2. Initialize Pointers:
   
   • A pointer (i) starts just before the leftmost index of the subarray.
   • Another pointer (j) scans from the leftmost index up to one before the pivot.
3. Rearrange Elements:
   
   • For each element at index j, if it is less than the pivot, increment i and swap the elements at i and j.
   • This ensures all elements less than the pivot are on the left, and those greater stay on the right.
4. Place Pivot in Correct Position:
   
   • After scanning, swap the pivot with the element at i + 1.
   • The pivot is now at its correct sorted position, with all smaller elements to its left and larger elements to its right.
5. Recursive Calls:
   
   • The process repeats for the left and right subarrays (excluding the pivot), continuing until all subarrays are sorted.

Example

Suppose the array is [34, 7, 23, 32, 5, 62] and the pivot is 62:

• All elements are less than 62, so after partitioning, 62 remains at the end, and the array is divided for further recursive sorting.

Writing your own sorting routines instead of using the qsort() function from the C standard library is the manual implementation of Quick Sort in C. This practical method enables modification and optimization while assisting you in comprehending the underlying workings of the algorithm.

Essential Components of an Implementation of a Manual Quick Sort

A typical manual implementation in C consists of the following functions:

1. Swap Function

This utility function exchanges the values of two elements in the array.

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

2. Partition Function

The partition function chooses a pivot (commonly the last element) and rearranges the array so that all elements less than the pivot are on its left, and all greater elements are on its right. The pivot ends up in its correct sorted position.

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;
}

3. Recursive Quick Sort Function

This function applies Quick Sort recursively to the subarrays formed by partitioning.

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);
    }
}

4. Printing the Array

A helper function to display the sorted array.

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);

    printf("\n");
}

Step-by-Step Example: Manual Quick Sort

Let’s walk through sorting the array {34, 7, 23, 32, 5, 62}:

1. Initial Array: 34, 7, 23, 32, 5, 62
2. Choose Pivot: 62 (last element)
   
   • All elements are less than 62, so no swaps needed.
   • 62 is placed at the end—array remains unchanged.
3. Partition Left Subarray: 34, 7, 23, 32, 5
   
   • Pivot: 5
   • All elements are greater than 5, so 5 is swapped to the front.
   • Array becomes: 5, 7, 23, 32, 34, 62
4. Recursively Sort Remaining Subarrays: Repeat the process for each subarray until all are sorted.

Interactive Quick Sort: User Input Example

Below is a C program that allows the user to input an array and see it sorted using your manual Quick Sort:

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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 n;

    printf("Enter the number of elements: ");
    scanf("%d", &n);

    int arr[n];

    printf("Enter the elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Sample Output:

Enter the number of elements: 6 Enter the elements: 34 7 23 32 5 62 Sorted array: 5 7 23 32 34 62

Troubleshooting and Best Practices

• Index Errors: Be careful with array indices, especially in the partition function. Off-by-one errors are common.
• Stack Overflow: For very large arrays, recursion depth can cause a stack overflow. Consider iterative Quick Sort for such cases.
• Pivot Choice: Generally, the last element is used as the pivot, but trying out a random or median of three selection can lead to better results with some datasets.
• In-Place Sorting: Quick Sort changes the array itself. So, if you want to keep the original, you have to make a copy first.

Bottom Line: By writing your own Quick Sort in C, you can decide totally how the process goes, from the method of choosing a pivot to the partitioning and sorting of the array. Having this deep knowledge is very helpful when you want to fine-tune and personalize sorting algorithms for real-life scenarios.

Understanding Quick Sort’s computational complexity is crucial for evaluating its performance and resource usage in different scenarios.

Time Complexity

1. Best Case:
   
   • O(n log n)
   • Occurs when the pivot divides the array into two nearly equal halves at every step.
   • Example: Using median-of-three or randomized pivot selection on unsorted/random data.
2. Average Case:
   
   • O(n log n)
   • Most likely scenario for random input data and reasonably balanced partitions.
3. Worst Case:
   
   • O(n²)
   • Happens when the pivot always ends up as the smallest or largest element, such as sorting an already sorted or reverse-sorted array with poor pivot selection.

Space Complexity

1. Auxiliary Stack Space:
   
   • O(log n) in the best and average cases, due to the recursion stack depth when partitions are balanced.
   • O(n) in the worst case, if partitions are highly unbalanced (e.g., always picking the smallest/largest element as pivot).
2. In-Place Sorting:
   
   • Quick Sort does not require extra memory for another array; all sorting is performed within the original array.
3. Recursion Stack Overhead:
   
   • Memory usage depends on recursion depth; deep recursion increases stack usage.

Key Points

• Divide and Conquer:
  Quick Sort repeatedly splits the array into subarrays, sorting each recursively.
• Pivot Selection Impact:
  Techniques like median-of-three or randomized pivot selection help maintain O(n log n) complexity by keeping partitions balanced.
• Memory Usage:
  Quick Sort’s primary memory usage comes from the recursive stack, not from allocating new arrays.

Summary:

Quick Sort generally offers O(n log n) time with O(log n) space due to recursion, but poor pivot choices can degrade both time and space complexity. Choosing a good pivot and optimizing recursion are key to maintaining its efficiency.

1. Recursive Quick Sort in C

#include <stdio.h>

void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

int partition(int arr[], int start, int end) {
    int pivot = arr[end];
    int i = start - 1;

    for (int j = start; j < end; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[end]);
    return i + 1;
}

void quickSort(int arr[], int start, int end) {
    if (start < end) {
        int pivotIndex = partition(arr, start, end);
        quickSort(arr, start, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, end);
    }
}

int main() {
    int arr[] = {25, 10, 55, 30, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, size - 1);

    printf("Sorted array: ");
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);

    return 0;
}

Code Explanation:

This C program for Quick Sort uses the algorithm to sort an array in ascending order. It selects the last element as the pivot, arranges the other elements around it, and then recursively sorts the resulting sub-arrays.

Output:

Sorted array: 5 10 25 30 55

Time and Space Complexity:

• Time Complexity: O(n log n) on average, O(n²) in the worst case.
• Space Complexity: O(log n) due to recursive stack usage.

2. Iterative Quick Sort in C

#include <stdio.h>

#define MAX 100

// Custom stack frame to hold start and end indexes
typedef struct {
    int start;
    int end;
} Stack;

// Swaps two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition function - similar to recursive version
int partition(int arr[], int start, int end) {
    int pivot = arr[end];
    int i = start - 1;

    for (int j = start; j < end; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[end]);
    return i + 1;
}

// Iterative quick sort using stack
void quickSortIterative(int arr[], int start, int end) {
    Stack stack[MAX];
    int top = -1;

    // Push initial range
    stack[++top] = (Stack){start, end};

    while (top >= 0) {
        Stack current = stack[top--];
        int low = current.start;
        int high = current.end;

        int pivotIndex = partition(arr, low, high);

        // Push left side if needed
        if (pivotIndex - 1 > low)
            stack[++top] = (Stack){low, pivotIndex - 1};

        // Push right side if needed
        if (pivotIndex + 1 < high)
            stack[++top] = (Stack){pivotIndex + 1, high};
    }
}

int main() {
    int arr[] = {35, 10, 65, 20, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    quickSortIterative(arr, 0, size - 1);

    printf("Sorted array: ");
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);

    return 0;
}

Code Explanation:

This C program for Quick Sort avoids recursion by using a manual stack to manage sub-array ranges. It works similarly to the recursive version but replaces function calls with loops and stack operations for better control and efficiency.

Output:

Sorted array: 5 10 20 35 65

Time and Space Complexity:

• Time Complexity: O(n log n) on average, O(n²) worst case.
• Space Complexity: O(log n) for the stack in the best case, O(n) worst case due to stack usage.

Quick Sort is often compared with other commonly used sorting algorithms such as Bubble Sort, Insertion Sort, Selection Sort, and Merge Sort. Each algorithm differs in terms of time complexity, memory usage, stability, and performance on large datasets.

Quick Sortin C is a popular sorting algorithm known for being fast and efficient with large amounts of data. Here's how and where it's commonly used:

• Handling Big Data: Quick Sort can sort through millions of items quickly, which makes it ideal for applications that deal with large datasets, like databases or big data analytics.
• Built into Programming Languages: Many system-level libraries use Quick Sort behind the scenes. For example, the qsort() function in the C programming language uses it to sort data.
• Part of More Complex Algorithms: Quick Sort is often used as a building block in advanced sorting techniques. For example, both Introsort (used in C++) and Timsort (used in Python and Java) include Quick Sort as a part of their sorting strategy.
• Low Memory Use: Since Quick Sort in C works in-place (it doesn’t need extra space for another array), it's a good choice when working with systems where memory is tight.

Quick Sort is widely used for its impressive performance and efficiency, but it’s important to understand both its strengths and its limitations before choosing it for your project.

Advantages

• Speed:
  Quick Sort is one of the fastest sorting algorithms for large datasets. Its average-case time complexity is O(n log n), making it much quicker than simpler algorithms like Bubble Sort or Insertion Sort for most real-world data.
• In-Place Sorting:
  Quick Sort doesn’t require extra memory for another array. It sorts the data within the original array, making it highly memory-efficient—especially important in systems with limited resources.
• Suitable for Large Datasets:
  Because of its speed and low memory usage, Quick Sort is well-suited for sorting large volumes of data, such as those found in databases or analytics applications.
• Works Well on Embedded and Mobile Devices:
  Its low memory footprint and efficiency make Quick Sort a strong choice for embedded systems and mobile devices, where both memory and processing power may be limited.
• Iterative Version Available:
  While Quick Sort is commonly implemented recursively, it can also be written in an iterative form to avoid recursion-related issues, such as stack overflow.

Drawbacks

• Unstable Sorting:
  Quick Sort is not a stable sort, meaning that it may change the relative order of equal elements. This can be a problem if stability is required (for example, when sorting records with duplicate keys).
• Worst-Case Performance:
  If a poor pivot is chosen (such as always picking the smallest or largest element in a nearly sorted array), Quick Sort can degrade to O(n²) time complexity. This is much slower than algorithms like Merge Sort in the worst case.
• Recursion Overhead:
  The standard recursive implementation can lead to significant recursion depth for large arrays, consuming stack space and potentially causing stack overflow errors if not managed carefully.
• Stack Overflow Risk:
  On very large datasets, especially with unbalanced partitioning, the recursion stack can grow too deep and cause a stack overflow. This risk can be reduced by using an iterative implementation or by optimizing the recursion.
• Not Always the Best for Small Arrays:
  For very small datasets, simpler algorithms like Insertion Sort may outperform Quick Sort due to lower overhead.

Quick Sort in C is a fast and effective way to sort data. It’s a useful tool for programmers because it usually works in O(n log n) time and doesn’t need extra space to sort. The main idea is to pick a good pivot and split the data around it using recursion. If you're looking to implement this, a C program for Quick Sort is a great example of how efficient sorting can be achieved with minimal code.

The more you practice writing Quick Sort in different ways, like exploring different pivot strategies or even coding a C program for Quick Sort, the better you’ll become at applying it to a variety of problems.

Advice for Learners

• The efficiency of Quick Sort largely depends on choosing a good pivot, as poor pivot selection can significantly degrade performance.
• Although Quick Sort is fast on average, it is not a stable sorting algorithm and may change the order of equal elements.
• Recursive implementations of Quick Sort can cause a stack overflow for very large inputs if partitioning is unbalanced.
• Iterative Quick Sort can be used to reduce recursion-related overhead and improve control over memory usage.
• Understanding partitioning logic is more important than memorizing code, as it forms the core of the Quick Sort algorithm.

1. How many types of Quick Sort are there?

You can use Quick Sort in two main styles:

• Recursive: This version calls itself over and over.
• Iterative: This one uses a stack to do the same job without calling itself.

2. What is a fast sorting algorithm?

Quick Sort is one of the fastest sorting methods out there. It works quickly for most inputs and doesn’t need much extra memory.

3. Why is Quick Sort often chosen?

People like Quick Sort because it’s fast, uses little memory, and works well with computer hardware (like cache). It’s often quicker than Merge Sort in real-world situations.

4. What’s the time complexity of Quick Sort?

• Average & Best case: O(n log n)
• Worst case: O(n²), but this can be improved by choosing the pivot randomly.

5. Is Quick Sort stable?

No, Quick Sort isn’t stable. That means it might change the order of equal items while sorting.

6. When is it good to use Quick Sort?

Quick Sort is a great choice when you need fast results and don’t mind if equal items change order. It’s especially useful when you want to sort large amounts of data efficiently.