Quick Sort in C [Program & Algorithm] | C Program for Quick Sort

By | May 20, 2020
Quick Sort in C

Before directly jump to learn the Quick sort in C, a general question must raise to your mind that what is sorting and why you need to learn this. So the answer is if you are a software developer than it becomes necessary that you have the knowledge of those all techniques which are required to the software development. Sorting is required to reduce the data searching time and arranged the large data in an arranged way to make it useful and more effective. Quick sort is one of the types of sorting algorithms.

Vamware

Quick Sort in C

Let’s understand the basics of Quick sort in C.

What is Quick Sort?

Quick sort is a highly efficient sorting algorithm. Like merge sort, this algorithm is also based on the divide and conquer technique by using the comparison method. For the large size of data, quick sort is the best solution. This algorithm first divides the array into two sub-arrays by comparing it with a specified value which is called Pivot value. The two sub-arrays are divided in that manner that one of which holds smaller values than pivot value and other holds greater than the pivot value.

There are different ways to do quick sort: –

  1. Always pick the last element as a pivot (implemented below)
  2. Always pick the first element as the pivot.
  3. Pick median as the pivot.
  4. Pick a random element as the pivot.

After the partition, quick sort calls itself recursively to sort the sub-arrays. Quick sort has the time complexity of O(n^2) in the worst and average case, where n is the number of elements. Therefore, quick sort is quite efficient for large data collection. The best case is when the pivot element will be the middle element. The best case time complexity is O(n logn).

Here is an example of quicksort to understand the technique more easily.

Quick Sort

This is the list contains 7 elements. The last element 70 is the pivot value. Now the list will be partitioned around 70 until we get the pivot for each sub-lists and all lists have a single element only.

Steps in the Quick Sort Algorithm: –

  • Step 1 – Start choosing with the highest index value called a pivot.
  • Step 2 − Take two variables that indicated the left and right of the list excluding pivot value.
  • Step 3 − Left variable with the show the low index.
  • Step 4 − Right will point to the high index.
  • Step 5 – If the value at the left index is less than the pivot, then move right.
  • Step 6 − While the value at the right is greater than the pivot, then move left.
  • Step 7 − If both step 5 and step 6 do not match the swap left and right index.
  • Step 8 − if left ≥ right, the point where they met will be the new pivot value.

Example using C Programming

/* QuickSort implementation using C*/

#include<stdio.h> 
// Function to swap two elements
void swap(int* a, int* b) 
{ 
int t = *a; 
*a = *b; 
*b = t; 
} 
/* This function will takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller than pivot
to left of pivot and all greater elements to right of pivot value. */
int partition (int arr[], int low, int high) 
{ 
int pivot = arr[high]; // pivot 
int i = (low - 1); // Index of smaller element 
for (int j = low; j <= high- 1; j++) 
{
// If 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); 
} 
/* The main function to implement QuickSort 
arr[] --> Array that is to be sorted, 
low --> to show Starting index, 
high --> to show Ending index */
void quickSort(int arr[], int low, int high) 
{ 
if (low < high) 
{ 
/* pi is partitioning index, arr[p] is now at right place */
int pi = partition(arr, low, high); 
// Separately sort elements before 
// partition and after partition 
quickSort(arr, low, pi - 1); 
quickSort(arr, pi + 1, high); 
} 
} 
/* Function to print an array */
void printArray(int arr[], int size) 
{ 
int i; 
for (i=0; i < size; i++) 
printf("%d ", arr[i]); 
printf("n"); 
} 
// Driver program to test above functions 
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: n"); 
printArray(arr, n); 
return 0; 
}

Output:

Sorted array:

1 5 7 8 9 10

Example using Java

// Implementation of QuickSort using Java program

class QuickSort 
{ 
/* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */
int partition(int arr[], int low, int high) 
{ 
int pivot = arr[high]; 
int i = (low-1); // index of smaller element 
for (int j=low; j<high; j++) 
{ 
// If current element is smaller than or 
// equal to pivot 
if (arr[j] <= pivot) 
{ 
i++; 
// swap arr[i] and arr[j] 
int temp = arr[i]; 
arr[i] = arr[j]; 
arr[j] = temp; 
}
} 
// swap arr[i+1] and arr[high] (or pivot) 
int temp = arr[i+1]; 
arr[i+1] = arr[high]; 
arr[high] = temp; 
return i+1; 
} 
/* The main function that implements QuickSort() 
arr[] --> Array to be sorted, 
low --> Starting index, 
high --> Ending index */
void sort(int arr[], int low, int high) 
{ 
if (low < high) 
{ 
/* pi is partitioning index, arr[pi] is 
now at right place */
int pi = partition(arr, low, high); 
// Recursively sort elements before 
// partition and after partition 
sort(arr, low, pi-1); 
sort(arr, pi+1, high); 
} 
} 
/* A utility function to print array of size n */
static void printArray(int arr[]) 
{ 
int n = arr.length; 
for (int i=0; i<n; ++i) 
System.out.print(arr[i]+" "); 
System.out.println(); 
} 
// Driver program 
public static void main(String args[]) 
{ 
int arr[] = {20, 17, 3, 9, 2, 5}; 
int n = arr.length; 
QuickSort ob = new QuickSort(); 
ob.sort(arr, 0, n-1); 
System.out.println("sorted array"); 
printArray(arr); 
} 
} 

Output:

Sorted array:

2 3 5 9 17 20

Advantages

  • The high performance of Quicksort makes it popular.
  • Quicksort has easy implementation.
  • On average, quicksort runs very fast and even faster than the merge sort.
  • No additional memory required to hold the variables while sorting.

Disadvantages

  • Quicksort is not stable.
  • Running time is depends on the size of an array.
  • If the pivot selection is unsuccessful, then running time will heavily degrade.
  • Difficult to implement the partitioning and the average efficiency for the worst case.

Real-Time Application

In real-time problems, whenever you need sorting, you may apply quicksort as it is very efficient. Here is a practical example-

Suppose, you have a shopping list, and you have a fixed amount of time to grab them. You will be also given priorities to decide, so you need to grab them first.

This is the shopping list with Item/ and their Priority;

Eggs (4)

Bread (2)

Milk (6)

Meat (1)

Detergent (5)

Water (3)

For small lists, it is easy to arrange with the eyes and follow priority numbers. But what about the list of items with a count of 138 or more? What will you do then? Would you check 138 items to find the next item? NO, it’s obvious that you don’t have that much time!

So you will be reordering the list by priority, by taking the first element as a pivot which is eggs.

STEP 1:

Shift fewer priority elements after eggs and more priority ones before eggs.

bread (2) – Group A

water (3) – Group A

meat (1) – Group A

eggs (4) – Pivot

milk (6) – Group B

detergent (5) – Group B

Then you are doing same thing for each divided group:

STEP 2:

Group A

meat (1)

bread (2) – Pivot

water (3)

Group A is done!

STEP 3:

Group B

detergent (5)

milk (6) – Pivot

Group B is done.

So what we have?

Group A ordered

Pivot (in place where it needs to be)

Group B ordered

STEP 4:

Write them all;

meat (1)

bread (2)

water (3)

eggs (4)

detergent (5)

milk (6)

So, for 6 items, you just performed only with 4 steps and got your sorted shopping list by priority.

You might be also interested In:

Author: Sujata Gaur

Sujata Gaur is an engineering graduate who is a content writer by profession. Writing and learning are the two thing which is her passion. Looking around new things and writing about it gives another level of peace, this is what she presumes. Giving words to your thoughts is creativity and so she is creative. She has an interest in researching new ideologies and creating its content so as to make it easy and understanding.

Leave a Reply

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