Sort an Array using Quick Sort in C

To sort an array using Quick Sort in C, we use the divide-and-conquer approach. The algorithm selects a pivot element, partitions the array into elements less than and greater than the pivot, and recursively sorts the subarrays. This process continues until the entire array is sorted efficiently.

Examples of Quick Sort in C

1. Basic Implementation of Quick Sort

In this example, we will implement the Quick Sort algorithm to sort an array of integers in ascending order.

main.c

</>
Copy
#include <stdio.h>

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

// Partition function to rearrange elements
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choosing the last element as pivot
    int i = (low - 1);

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

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

        quickSort(arr, low, pi - 1);  // Recursively sort left partition
        quickSort(arr, pi + 1, high); // Recursively sort right partition
    }
}

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

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);

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

Explanation:

  1. The function swap() exchanges two elements.
  2. The function partition() selects the last element as the pivot and rearranges the array.
  3. All elements smaller than the pivot are moved to the left, and larger elements are moved to the right.
  4. The function quickSort() recursively sorts the left and right partitions.
  5. Finally, the sorted array is printed using printArray().

Output:

Sorted array: 1 5 7 8 9 10

2. Sorting an Array in Descending Order

In this example, we modify the Quick Sort algorithm to sort an array in descending order.

main.c

</>
Copy
#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Modified partition function for descending order
int partitionDesc(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++) {
        if (arr[j] >= pivot) { // Change condition for descending order
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Quick Sort function for descending order
void quickSortDesc(int arr[], int low, int high) {
    if (low < high) {
        int pi = partitionDesc(arr, low, high);

        quickSortDesc(arr, low, pi - 1);
        quickSortDesc(arr, pi + 1, high);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {3, 6, 2, 9, 4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSortDesc(arr, 0, n - 1);

    printf("Sorted array in descending order: ");
    printArray(arr, n);
    return 0;
}

Explanation:

  1. We modify the condition in partitionDesc() to move larger values to the left.
  2. The function quickSortDesc() recursively sorts the array in descending order.
  3. After sorting, we print the sorted array using printArray().

Output:

Sorted array in descending order: 9 7 6 4 3 2

Conclusion

In this tutorial, we covered Quick Sort algorithm in C with different implementations:

  1. Basic Quick Sort: Sorting an array in ascending order.
  2. Descending Order Quick Sort: Modifying the partition logic for descending sorting.

Quick Sort is an efficient sorting algorithm, widely used due to its divide-and-conquer strategy, achieving an average time complexity of O(n log n).