quick sort

Quick Sort is a highly efficient sorting algorithm that uses the divide-and-conquer strategy. It works by selecting a “pivot” element from the array, partitioning the remaining elements into two sub-arrays (elements less than the pivot and elements greater than the pivot), and recursively sorting the sub-arrays.

---

Key Concepts of Quick Sort:

1. Pivot Selection:
   1. A pivot is an element around which the array is partitioned.
   1. Common strategies: choose the first element, last element, middle element, or a random element.
2. Partitioning:
   1. Rearrange elements so that:
      1. Elements smaller than the pivot are on the left.
      1. Elements larger than the pivot are on the right.
   1. The pivot is placed in its correct position in the sorted array.
3. Recursive Sorting:
   1. The process is repeated for the left and right sub-arrays.

---

Characteristics of Quick Sort:

• Time Complexity:
  • Best Case: O(nlog⁡n)O(n \log n)O(nlogn)
  • Average Case: O(nlog⁡n)O(n \log n)O(nlogn)
  • Worst Case: O(n2)O(n^2)O(n2) (occurs when the pivot is the smallest or largest element repeatedly).
• Space Complexity:
  • O(log⁡n)O(\log n)O(logn) (recursive stack space).
• In-Place Sorting:
  • Quick Sort does not require extra memory, making it efficient for large datasets.

---

Implementation of Quick Sort in C:

C Code Example:

#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 arr[], int low, int high) {

    int pivot = arr[high];  // Choosing the last element as pivot

    int i = low – 1;  // Index of smaller element

    for (int j = low; j < high; j++) {

        if (arr[j] <= pivot) {  // If current element is smaller than or equal to pivot

            i++;

            swap(&arr[i], &arr[j]);

        }

    }

    swap(&arr[i + 1], &arr[high]);  // Place pivot in the correct position

    return i + 1;  // Return the pivot index

}

// Quick Sort function

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pi = partition(arr, low, high);  // Partitioning index

        // Recursively sort elements before and after partition

        quickSort(arr, low, pi – 1);

        quickSort(arr, pi + 1, high);

    }

}

// Utility function to print an array

void printArray(int arr[], int size) {

    for (int i = 0; i < size; i++) {

        printf(“%d “, arr[i]);

    }

    printf(“\n”);

}

// Main function

int main() {

    int arr[] = {10, 7, 8, 9, 1, 5};

    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;

}

---

How It Works:

1. Initial Array: {10, 7, 8, 9, 1, 5}
   1. Pivot: 5 (last element).
   1. After partition: {1, 5, 8, 9, 7, 10}.
   1. Pivot 5 is placed in its correct position at index 1.
2. Left Sub-Array: {1}
   1. Already sorted.
3. Right Sub-Array: {8, 9, 7, 10}
   1. Pivot: 10.
   1. After partition: {8, 9, 7, 10}.
   1. Pivot 10 is placed in its correct position.
4. Recursively sort left and right sub-arrays.

---

Advantages and Disadvantages:

Advantages:

1. Efficient: One of the fastest algorithms for large datasets.
2. In-Place: No additional memory is needed for sorting.

Disadvantages:

1. Worst-Case Performance: O(n2)O(n^2)O(n2), though this can be mitigated by using randomized pivot selection.
2. Recursive: May lead to stack overflow for very large datasets if not optimized.

---

Example Output:

For the input array {10, 7, 8, 9, 1, 5}:

Original array: 10 7 8 9 1 5

Sorted array: 1 5 7 8 9 10

---

Quick Sort is one of the most widely used sorting algorithms due to its speed and efficiency, especially for large datasets. Proper pivot selection and handling can mitigate its worst-case performance.