Quick Sort

Quick Sort is a highly efficient sorting algorithm that is based on the divide and conquer principle. It can sort large datasets significantly faster than selection sort or bubble sort algorithms. Here's a simple explanation using an example with five elements:

Let's say our list is: [5, 3, 7, 2, 8]

Selecting the Pivot: In Quick Sort, a pivot element is chosen from the array. The choice of the pivot can vary - it could be the first element, the last element, the middle one, or even a random element. For simplicity, let's choose the first element as the pivot in our example. So, pivot = 5.
Partitioning: The array is partitioned around the pivot element by rearranging elements so that elements less than the pivot are on its left, and those greater than the pivot are on its right. After this step, the pivot is in its final position.
Recursively Applying Quick Sort: Quick Sort is then recursively applied to the sub-arrays formed by partitioning.

Here's the process visualized using ASCII art, with pivot as the first element:

Initial Array: [5, 3, 7, 2, 8]
Pivot = 5

First Iteration:
[5, 3, 7, 2, 8] -> [2, 3, 7, 5, 8] (Pivot placed in the correct position)
Now, we have two sub-arrays: [2, 3] (left of pivot) and [7, 5, 8] (right of pivot)

Applying Quick Sort on [2, 3]:
Pivot = 2
[2, 3] -> [2, 3] (Pivot is in the correct position, and [3] is already sorted)

Applying Quick Sort on [7, 5, 8]:
Pivot = 7
[7, 5, 8] -> [5, 7, 8] (Pivot placed in the correct position)
Sub-arrays: [5] (left) and [8] (right) are already sorted.

Final Sorted Array: [2, 3, 5, 7, 8]

The pivot is crucial in determining the efficiency of the Quick Sort algorithm. A poorly chosen pivot can lead to inefficient sorts, but a good choice (like the median) can enhance performance significantly. The method of selecting the pivot varies and can be optimized based on the context of the data being sorted.

Here's the pseudocode for the Quick Sort algorithm:

function quickSort(arr, low, high)
    if low < high
        // Partition the array by setting the position of the pivot element
        pi = partition(arr, low, high)

        // Recursively sort the sub-array before the pivot
        quickSort(arr, low, pi - 1)

        // Recursively sort the sub-array after the pivot
        quickSort(arr, pi + 1, high)

function partition(arr, low, high)
    // Select a pivot element
    pivot = arr[high]

    // Index of smaller element
    i = (low - 1)  

    for j = low to high - 1
        // If current element is smaller than or equal to pivot
        if arr[j] <= pivot
            i = i + 1
            swap arr[i] with arr[j]

    // Swap the pivot element with the element at index (i + 1)
    swap arr[i + 1] with arr[high]

    // Return the partitioning index
    return (i + 1)

// A utility function to swap two elements
function swap(a, b)
    temp = a
    a = b
    b = temp

// Main function to call quickSort
function main(arr)
    quickSort(arr, 0, length(arr) - 1)

In this pseudocode:

The quickSort function takes an array and the indices of the first and last elements as its arguments.
The partition function rearranges the elements in the array so that all elements less than the pivot come before the pivot, while all elements greater than the pivot come after it.
The swap function is a utility to swap two elements in the array.
The sorting process is recursive, where the quickSort function is called for sub-arrays formed after the partition.

You can call the main function and pass your array to it to perform the Quick Sort. This pseudocode uses the last element as the pivot for simplicity, but the choice of pivot can be modified as needed.

Here's a C implementation of the Quick Sort algorithm:

#include <stdio.h>

void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void swap(int* a, int* b);

int main() {
    int arr[] = {5, 3, 7, 2, 8};
    int n = sizeof(arr)/sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

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

    return 0;
}

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

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 swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

Explanation of the code:

Include Standard Library: We include the standard I/O library for input and output functions.
Function Declarations:
- quickSort: This function performs the Quick Sort. It takes the array and the indices of the first and last elements as arguments.
- partition: This function partitions the array and returns the index of the pivot placed at its correct position.
- swap: A utility function to swap two elements using pointers.
The main Function:
- It initializes an array arr and calculates its size n.
- Calls quickSort to sort the array.
- Prints the sorted array.
The quickSort Function:
- It's a recursive function.
- If the low index is less than the high index, which means there are elements to be sorted.
- The partition function is called to place the pivot element at its correct position and to get the partition index pi.
- The function then recursively sorts the sub-arrays before and after the partition index.
The partition Function:
- This function takes the last element as a pivot.
- It places all smaller elements than the pivot to the left and all greater elements to the right of the pivot.
- It also rearranges the pivot to its correct position.
The swap Function:
- Swaps values pointed to by the pointers a and b.
Running the Program: When you run this program, it sorts the array [5, 3, 7, 2, 8] using Quick Sort and prints the sorted array.

Complexity analysis of the Quick Sort algorithm involves understanding its time and space complexity under different conditions. The performance of Quick Sort depends on the choice of the pivot element and can vary in the best, average, and worst-case scenarios.

Best Case Scenario (Time Complexity: O(n log n)):
- The best case occurs when the partition process always picks the middle element as the pivot, or very close to it. This results in the array being divided into two nearly equal halves in every recursive call.
- For example, if the initial array is [3, 5, 7, 8, 2] and the pivot chosen leads to almost equal partitions, the recursive calls would be optimally balanced, leading to the best case.
Average Case Scenario (Time Complexity: O(n log n)):
- The average case time complexity is also O(n log n), assuming that the pivot splits the array into parts of varying sizes (but not the worst-case).
- Most of the time, with a 'good' pivot choice (like median or random), the partitions will be reasonably well balanced, and the depth of the recursive call tree is O(log n).
Worst-Case Scenario (Time Complexity: O(n^2)):
- The worst case occurs when the partition process always picks the greatest or smallest element as the pivot (i.e., the pivot is an extreme).
- For instance, if the initial array is already sorted[2, 3, 5, 7, 8] and the last element is always chosen as the pivot, each partition would split the array into two parts of sizes 0 and n-1, leading to highly unbalanced recursive calls.
- This causes the depth of the recursive call tree to be O(n), leading to O(n^2) time complexity.
Space Complexity:
- The space complexity of Quick Sort is O(log n) in the best case, which occurs due to the stack space used for recursive function calls.
- In the worst case, the space complexity can become O(n), due to the recursive calls piling up.

It's important to note that while Quick Sort has a worst-case scenario of O(n^2), it's rarely encountered with a good choice of pivot (like a random pivot). In practice, Quick Sort is one of the fastest sorting algorithms, particularly for large datasets, due to its O(n log n) average time complexity.