Quick sort is a widely used sorting algorithm that follows the divide-and-conquer approach. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted using the same process until the entire array is sorted.

Here's an explanation of the quick sort algorithm:

1. Choose a pivot element from the array. The pivot can be selected randomly or as the first, middle, or last element.

2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot..

3. Recursively apply the quick sort algorithm to the two sub-arrays. This step can be performed using separate recursive calls.

4. Combine the sorted sub-arrays and the pivot to get the final sorted array.

Here's an example implementation of the quick sort algorithm in C:

#include <stdio.h>

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

// Function to partition the array and return the pivot index
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choose the last element as the pivot
    int i = low - 1;
    int j;

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

// Function to perform quick sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);

        // Recursively sort the sub-arrays
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Test the algorithm
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    quickSort(arr, 0, n - 1);

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

    return 0;
}

In this example, the `swap` function is used to swap two elements in the array. The `partition` function chooses the last element as the pivot, partitions the array, and returns the pivot index. The `quickSort` function performs the quick sort algorithm recursively on the sub-arrays. The `printArray` function is used to display the array before and after sorting.

The output will be:

Original array: 64 34 25 12 22 11 90
Sorted array: 11 12 22 25 34 64 90

As you can see, the quick sort algorithm partitions the array based on the pivot and recursively sorts the sub-arrays, resulting in a sorted array. Quick sort is known for its efficient average-case performance and is widely used in practice.

Time Complexity

The time complexity of the Quick Sort algorithm in DAA (Design and Analysis of Algorithms) is typically O(n log n) in the average and best cases.

In Quick Sort, the array is recursively partitioned based on a selected pivot element. On average, the pivot element divides the array into two nearly equal halves during each partitioning step. This recursive partitioning process continues until each sub-array contains only one element, which is already sorted. The average time complexity arises from the fact that each partitioning step reduces the array size by approximately half, resulting in a logarithmic number of recursive calls.

However, in the worst case, when the selected pivot is always the smallest or largest element, Quick Sort's time complexity degrades to O(n^2). This occurs if the partitioning is consistently unbalanced, causing the algorithm to make n-1 recursive calls for an array of size n. To mitigate the worst-case time complexity, randomized pivot selection or other techniques, such as choosing the median of three elements as the pivot, can be used.

Overall, the average and best-case time complexity of Quick Sort is O(n log n), making it an efficient sorting algorithm, particularly for large input sizes. However, the worst-case time complexity of O(n^2) makes Quick Sort less desirable when the input contains already sorted or nearly sorted data.

Space Complexity

The space complexity of the Quick Sort algorithm in DAA (Design and Analysis of Algorithms) is O(log n) in the average and best cases.

The space complexity arises from the auxiliary space required for the recursive calls made during the sorting process. Each recursive call requires a certain amount of additional space on the call stack to maintain local variables and return addresses.

In the average and best cases, Quick Sort divides the array into two sub-arrays with nearly equal sizes during each partitioning step. This balanced partitioning results in a logarithmic number of recursive calls. As a result, the maximum depth of the recursion is logarithmic in the input size.

Therefore, in the average and best cases, the space complexity of Quick Sort is O(log n), where n is the size of the input array.

However, it's worth noting that in the worst case, when the pivot selection consistently leads to unbalanced partitions, the space complexity can degrade to O(n). This occurs when the recursion depth reaches the maximum limit due to the unbalanced partitions, which can happen if the pivot is always the smallest or largest element. However, techniques such as randomized pivot selection or choosing the median of three elements as the pivot can help mitigate the worst-case scenario and maintain the average and best-case space complexity of O(log n).

Overall, Quick Sort's space complexity is generally considered efficient, especially when compared to algorithms that require additional data structures or auxiliary arrays. The additional space required is limited to the call stack space used for the recursive calls, which is logarithmic in the input size.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc