Quicksort — (C Version)

OPai

# quicksort
// implement quick sort
// optimize the algorithm if possible 

Code

#include <stdio.h>

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

// Partition function using median-of-three for pivot selection
int partition(int arr[], int low, int high) {
    // Median-of-three pivot selection
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[mid])
        swap(&arr[low], &arr[mid]);
    if (arr[low] > arr[high])
        swap(&arr[low], &arr[high]);
    if (arr[mid] > arr[high])
        swap(&arr[mid], &arr[high]);
    
    // Place the pivot at arr[high-1]
    swap(&arr[mid], &arr[high-1]);
    int pivot = arr[high-1];
    
    int i = low;
    for (int j = low; j < high-1; j++) {
        if (arr[j] <= pivot) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[high-1]);
    return i;
}

// Insertion sort for small subarrays
void insertionSort(int arr[], int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Optimized quicksort implementation
void quicksort(int arr[], int low, int high) {
    // Use insertion sort for small subarrays
    if (high - low + 1 <= 10) {
        insertionSort(arr, low, high);
        return;
    }
    
    if (low < high) {
        int pi = partition(arr, low, high);
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}