Quick Sort program in C - and how it works

Like the merge sort, quick sort is another sorting algorithm that works well for larger arrays. However, the downside is that it is not stable, so it is not good for multi-level sorts.

The algorithm works by recursively dividing the array to the left and right of a pivot element.

Quick Sort Program in C

#include <stdio.h>

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

void quickSort(int arr[], int leftIndex, int rightIndex) {
    if(leftIndex<rightIndex) {
        int pivot = arr[rightIndex];
        int leftCount = 0;
        int rightCount = 0;
        int segmentLength = rightIndex-leftIndex+1;
        int oLength = segmentLength-1;
        int others[oLength];
        int i;

        for(i=leftIndex; i<rightIndex; i++) {
            if(arr[i] <= pivot) {
              others[leftCount] = arr[i];
              leftCount++;  
            }
            else {
                others[oLength-1-rightCount] = arr[i];
                rightCount++;
            }
        }

        int j=leftIndex;

        for(i=0;i<leftCount;i++) {
            arr[j] = others[i];
            j++;
        }

        arr[j] = pivot;
        j++;

        for(i=rightCount+leftCount-1;i>=leftCount;i--) {
          arr[j] = others[i];
          j++;  
        }

        quickSort(arr, leftIndex, leftIndex+leftCount-1);
        quickSort(arr, leftIndex+leftCount+1, rightIndex);

    } 
}

int main() {
    int n;
    printf("Enter the no. of items in the array: ");
    scanf("%d", &n);

    int arr[n];

    printf("Enter the array: ");
    for(int i=0; i<n; i++) {
        scanf("%d", &arr[i]);
    }

    printf("Here is the array before sorting:\n");
    printArray(arr, n);

    quickSort(arr, 0, n-1);

    printf("Here is the sorted array:\n");
    printArray(arr, n);
    return 0;
}

How the program works

The function quickSort() receives the left and right indexes for the current portion of the array. Then it sets the element at the right index as the pivot.

The array others[] is for storing all the other elements. All elements between leftIndex and rightIndex-1 and smaller than the pivot are stored from the left side of the array others[]. And all the larger elements are stored from the right side. The counts for each parts - leftCount and rightCount - are also kept. This way we can store both the parts in a single array and identify them later.

Once the others[] array is calculated, we'll iterate the left part first, placing each of the element back to the original array arr[], starting from the leftIndex. Then we'll put the pivot element at the index leftIndex+leftCount, and the remaining slots will contain the right part, until rightIndex.

Then this is repeated for the left part and right part recursively until there is only one element in a portion. At that point the original array arr[] will be sorted.