Quick Sort

Code

C language code:

#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 - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quick_sort(int arr[], int low, int high) {
    int stack[high - low + 1];
    int top = -1;

    stack[++top] = low;
    stack[++top] = high;

    while (top >= 0) {
        high = stack[top--];
        low = stack[top--];

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

        if (p - 1 > low) {
            stack[++top] = low;
            stack[++top] = p - 1;
        }

        if (p + 1 < high) {
            stack[++top] = p + 1;
            stack[++top] = high;
        }
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    quick_sort(arr, 0, n - 1);

    printf("\nSorted array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Code Explanation

1. Initialization: arr is the array to be sorted, and n is its length.
2. Swap function:
   • The swap function is used to swap two integer values.
3. Partition function:
   • The partition function selects the last element of the array as the pivot element.
   • i is initialized to low - 1, used to track the region of elements smaller than the pivot.
   • Traverses the array, swapping elements smaller than the pivot to the left side.
   • Finally, places the pivot element in the correct position and returns its index.
4. Quick sort function:
   • quick_sort uses a stack to simulate the recursive process, implementing non-recursive quick sort.
   • Initializes the stack, pushing the initial interval [low, high] onto it.
   • Enters a loop, popping an interval from the stack each time and performing partitioning.
   • Pushes the left and right sub-intervals after partitioning onto the stack, until the stack is empty.

Example Run

Assuming the input array is {12, 11, 13, 5, 6, 7}:

1. Initial state: {12, 11, 13, 5, 6, 7}
2. First partition:
   • Select pivot element 7.
   • Swap elements smaller than 7 to the left: {6, 5, 7, 12, 11, 13}
   • Place pivot element 7 in the correct position: {6, 5, 7, 12, 11, 13}
3. Continue partitioning the left side [6, 5] and right side [12, 11, 13]:
   • Left side [6, 5] after partition: {5, 6, 7, 12, 11, 13}
   • Right side [12, 11, 13] after partition: {5, 6, 7, 11, 12, 13}
4. Final result: {5, 6, 7, 11, 12, 13}

Time Complexity Analysis

The time complexity of quick sort mainly depends on the partitioning process and recursion depth.

• Best-case time complexity: $O(n \log n)$, when each partition can evenly split the array into two parts.
• Worst-case time complexity: $O(n^2)$, when each partition selects the smallest or largest element as the pivot, resulting in extremely uneven partitions.
• Average time complexity: $O(n \log n)$, for most input arrays, quick sort's performance is very stable.

Space Complexity Analysis

Quick sort sorts in place, but recursive calls use stack space, so the space complexity is $O(\log n)$.

Advantages and Disadvantages

Advantages:

• Average time complexity of $O(n \log n)$; suitable for large-scale data sorting.
• No additional auxiliary space needed; low space complexity.
• Simple to implement; works well in most cases.

Disadvantages:

• Worst-case time complexity is $O(n^2)$.
• Unstable sorting algorithm; may change the relative order of equal elements.

Applicable Scenarios

Quick sort is suitable for the following scenarios:

• Sorting large datasets.
• When a highly efficient sorting algorithm with low space complexity is needed.
• Scenarios where stable sorting is not required.

Summary

Quick sort is an efficient sorting algorithm that works by selecting a pivot element to split the array into two parts, sorting each partition in place. Although its worst-case time complexity is relatively high, it performs excellently in average cases and is a sorting algorithm with low time complexity and low space complexity.