Quick Sort in C

In this tutorial, we are going to see how to create a Quick Sort program in C. Quick Sort is an algorithm based on the Divide and Conquer principle. The steps are as follows:

• Choose one element from the array, this element is called the pivot element.
• Divide the unsorted array of elements into two arrays whose value is less than the pivot and appear in the first subarray. All elements with values greater than the pivot are in the second subarray (equal values can go either way). This step is called the partition operation.
• Recursively repeat step 2 (until the sub-tables are sorted).

The same logic we implemented in the following C program.
 

 

Quick Sort program in C

#include <stdio.h>

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

void quickSort(int arr[], int first, int last) {
    int pivot, i, j;
    if(first < last) {
        pivot = first;
        i = first;
        j = last;
        while (i < j) {
            while(arr[i] <= arr[pivot] && i < last)
                i++;
            while(arr[j] > arr[pivot])
                j--;
            if(i < j) {
                swap(&arr[i], &arr[j]);
            }
        }
        swap(&arr[pivot], &arr[j]);
        quickSort(arr, first, j - 1);
        quickSort(arr, j + 1, last);
    }
}

int main() {
    int arr[100], nbr, i;
  
    printf("\n Enter the total number of elements: ");
    scanf("%d", &nbr);
    
    printf("\n Enter the array elements: ");
    for(i = 0; i < nbr; i++)
        scanf("%d", &arr[i]);
    
    quickSort(arr, 0, nbr - 1);
    
    printf("\n Sorted array: ");
    for(i = 0; i < nbr; i++)  {
        printf(" %4d", arr[i]);
    }
    printf("\n");
    return 0;
}

Output:

 Enter the total number of elements: 5

 Enter the array elements: 3 7 1 2 0

 Sorted array:     0    1    2    3    7

 

MCQPractice competitive and technical Multiple Choice Questions and Answers (MCQs) with simple and logical explanations to prepare for tests and interviews.Read More