Quick sort is a divide & conquer algorithm and is one of the most efficient sorting algorithms it is performed by splitting an array into small arrays. Quick sort is the fastest internal sorting algorithm it is faster than any common sorting algorithms having time complexity O (n log n)

Quick sort works in the following manner:

  1. Choose an element from the array, that element is called a pivot element.
  2. Break the unsorted array of elements in two arrays including values smaller than the pivot appears in the first sub array, while all elements with values greater than the pivot appear in the second sub-array (same values can go either approach). This step is called the partition operation.
  3. Recursively repeat step 2 (until the sub-arrays are sorted) to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values. This same logic we have performed in the following C program. but before that we have a blueprint (Pseudocode) of the program so you understand it easily

Pseudocode of Quick Sort Algorithm:

/* low  --> Starting point or index,  high  --> Ending point or index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning point or index, arr[pi] is now
           at right place in the array */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Actual Program For Quick Sort In C

#include<stdio.h>

// to swap two numbers
void swap(int* a, int* b) {
  int t = *a;
  *a = *b;
  *b = t;
}
int partition_function (int arr[], int low, int high) 
{
  int pivot = arr[high]; // selecting last element as pivot
  int i = (low - 1); // index of smaller element

  for (int j = low; j<= high- 1; j++) 
  {
    // If the current element is smaller than or equal to pivot
    if (arr[j] <= pivot) 
    {
      i++; // increment index of smaller element
      swap(&arr[i], &arr[j]);
    }
  }
   swap(&arr[i + 1], &arr[high]);
   return (i + 1);
}
/*
  a[] is the array, p is starting point or index, which is 0,
   and r is the last point or index of array.
*/
void quicksort_algorithm(int a[], int p, int r)
{
   if(p < r)
   {
       int q;
       q = partition_function(a, p, r);
       quicksort_algorithm(a, p, q-1);
       quicksort_algorithm(a, q+1, r);
   }
 }

// function to print the array
void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
       printf("%d ", a[i]);
    }
    printf("n");
}
int main()
{
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // call quickSort Algorithm function
    quicksort_algorithm(arr, 0, n-1);

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

Output

Sorted array: 
 2 3 5 6 7 9 10 11 12 14 

If you like this post, don’t forget to share 🙂

This article is written by our awesome writer
Contributor
Do you like Zubeen's articles?  Follow on social!
Comments to: Quick Sort in C

Your email address will not be published. Required fields are marked *

Attach images - Only PNG, JPG, JPEG and GIF are supported.

New Dark Mode Is Here

Sign In to access the new Dark Mode reading option.

Join our Newsletter

Get our monthly recap with the latest news, articles and resources.

By subscribing you agree to our Privacy Policy.

Latest Articles

Explore Tutorials By Categories

About

Codeverb is simply an all in one interactive learning portal, we regularly add new topics and keep improving the existing ones, if you have any suggestions, questions, bugs issue or any other queries you can simply reach us via the contact page

Login

Welcome to Codeverb

Ready to learn something new?
Join Codeverb!

Read Smart, Save Time
  •  
    Strength indicator
  •  
  •  
    Log In | Lost Password