# Understanding Quick Sort with C Implementation

Sorting algorithms play a crucial role in computer science, helping us organize and manipulate data efficiently. One such powerful and widely used sorting technique is **Quick Sort**. In this blog, we’ll explore the Quick Sort algorithm, understand its mechanism, and provide a C implementation.

## What is Quick Sort?

Quick Sort is a **divide-and-conquer** algorithm that works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays: those less than the pivot and those greater than the pivot. The process is then applied recursively to the sub-arrays.

### Why Use Quick Sort?

* **Efficiency**: Quick Sort is one of the fastest sorting algorithms in practical use.
    
* **Flexibility**: It works well for both small and large datasets.
    
* **In-Place Sorting**: It doesn’t require additional memory compared to other sorting methods like Merge Sort.
    

## How Does Quick Sort Work?

### Steps of the Algorithm:

1. **Choose a Pivot**: Select an element as the pivot. This can be the first element, the last element, or any random element in the array.
    
2. **Partition the Array**: Rearrange the elements so that all elements less than the pivot are to its left, and all elements greater are to its right.
    
3. **Recursively Apply**: Apply the same process to the left and right sub-arrays until the base case (a single-element array) is reached.
    

```c
#include <stdio.h>

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

// Partition function
int partition(int array[], int low, int high) {
    int pivot = array[high]; // Choosing the last element as the pivot
    int i = (low - 1); // Index of smaller element

    for (int j = low; j < high; j++) {
        // If the current element is smaller than or equal to the pivot
        if (array[j] <= pivot) {
            i++;
            swap(&array[i], &array[j]);
        }
    }

    swap(&array[i + 1], &array[high]);
    return (i + 1);
}

// Quick Sort function
void quickSort(int array[], int low, int high) {
    if (low < high) {
        // Partition the array
        int pi = partition(array, low, high);

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

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

int main() {
    int data[] = {8, 7, 6, 1, 0, 9, 2};
    int n = sizeof(data) / sizeof(data[0]);

    printf("Unsorted array: \n");
    printArray(data, n);

    quickSort(data, 0, n - 1);

    printf("Sorted array in ascending order: \n");
    printArray(data, n);

    return 0;
}
```

dtytry

## Explanation of the Code

1. **Partition Function**:
    
    * It selects the last element as the pivot.
        
    * Rearranges elements around the pivot so that smaller elements are on the left and larger ones are on the right.
        
    * Returns the partition index, which is the final position of the pivot.
        
2. **Quick Sort Function**:
    
    * Recursively applies Quick Sort to the sub-arrays before and after the pivot.
        
3. **Main Function**:
    
    * Initializes the array and prints it before and after sorting.
        

## Time and Space Complexity

### Time Complexity:

* **Best Case**: when the pivot divides the array into two nearly equal halves.
    
* **Worst Case**: when the pivot divides the array into extremely unbalanced parts (e.g., when the array is already sorted).
    
* **Average Case**: .
    

### Space Complexity:

* **In-Place Algorithm**: Requires space for recursion stack.
    

## Advantages of Quick Sort

* Faster than other algorithms like Merge Sort for smaller datasets.
    
* Requires less memory as it sorts in place.
    

## Disadvantages of Quick Sort

* Performance degrades to in the worst-case scenario.
    
* Not a stable sorting algorithm (relative order of equal elements may change).
    

Quick Sort is an elegant and efficient sorting algorithm that strikes a balance between performance and simplicity. Its practical utility and straightforward implementation make it a valuable tool for software developers.