Quick Sort in C, C++, Java, and Python [Program and Algorithm]

By | November 15, 2021
Quick Sort in C, C++, Java, and Python

Before directly jumping to learn the quick sort in C algorithm, a general question that might come to your mind is, “What is sorting, and why do you need to learn it?” The answer to the question is simple. If you are a software developer, then it becomes necessary that you have the knowledge of all those techniques that are required for software development.

Also, sorting is required to reduce the data search time and arrange a large set of data in an organized way to make it useful and more effective. Quick sort is one of the many types of sorting algorithms.

Vamware

Quick Sort in C

Before seeing the implementation of quick sort in C, let’s first understand the basics of quick sort.

What is Quick Sort?

Quicksort is a highly efficient sorting algorithm. Like merge sort, this algorithm is also based on the divide and conquer technique and uses the comparison method. Quick sort is an ideal solution for a large set of data. The sorting algorithm first divides the array into two sub-arrays by comparing all elements with a specified value, called the Pivot value.

The two sub-arrays are divided in a way that one of them holds smaller values than the pivot value, and the other holds greater values than the pivot value. There are different ways to implement quick sort:

  1. Always pick the last element as a pivot (we’ll use this in our quick sort in C example).
  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 cases, where n is the number of elements. Therefore, quicksort is quite efficient for large data. The best case is when the pivot element will be the middle element. The best case time complexity for quick sort is O(n logn).

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

Quick Sort

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

Steps for the Quick Sort in C Algorithm

  • First Step – Start choosing with the highest index value called a pivot.
  • Second Step − Take two variables that indicate the left and right of the list, excluding the pivot value.
  • Third Step − Left variable will show the low index.
  • Fourth Step − Right will point to the high index.
  • Fifth Step – If the value at the left index is less than the pivot, then move right.
  • Sixth Step − If the value at the right index is greater than the pivot, then move left.
  • Seventh Step − If both step 5 and step 6 do not match, then swap left and right indexes.
  • Eighth Step − If left ≥ right, the point where they meet will be the new pivot value.

Quick Sort in C Example

/* 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 takes the last element as pivot, places the pivot element at its correct position in a sorted array, and places all smaller than pivot
to the left of the pivot and all greater elements to the right of the pivot. */
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

Quick Sort in Java Example

// Implementation of QuickSort using Java program

class QuickSort 
{ 
/* This function takes the last element as pivot, places the pivot element at its correct position in the sorted array, and places all smaller (smaller than pivot) to the left of the pivot and all greater elements to the right of the 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

Quick Sort in C++ Example

#include <bits/stdc++.h>
using namespace std;

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

int partition (int arr[], int low, int high)
{
    int pivot = arr[high]; 
    int i = (low - 1); 

    for (int j = low; j <= high - 1; j++)
    {

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

void applyQuickSort(int arr[], int low, int high)
{
    if (low < high)
    {

        int pivotIndex = partition(arr, low, high);

        applyQuickSort(arr, low, pivotIndex - 1);
        applyQuickSort(arr, pivotIndex + 1, high);
    }
}

int main()
{
    int arr[] = {1, 4, 3, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    applyQuickSort(arr, 0, n - 1);
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    return 0;
}

Output

1 2 3 4 5

Quick Sort in Python Example

def partition(start, end, arr):
      
      pivotIndex = start
      pivot = arr[pivotIndex]
      
      while start < end:

            while start < len(arr) and arr[start] <= pivot:
                  start += 1
                  
            while arr[end] > pivot:
                  end -= 1
            if(start < end):
                  arr[start], arr[end] = arr[end], arr[start]

      arr[end], arr[pivotIndex] = arr[pivotIndex], arr[end]
      
      return end
      
def applyQuickSort(start, end, arr):
      
      if (start < end):

            p = partition(start, end, arr)
            
            applyQuickSort(start, p - 1, arr)
            applyQuickSort(p + 1, end, arr)
            
arr = [ 1, 2, 4, 3, 5 ]
applyQuickSort(0, len(arr) - 1, arr)

print(arr)

Output

[1, 2, 3, 4, 5]

Advantages of Quick Sort

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

Disadvantages of Quick Sort

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

A Real-Time Application Example of Quick Sort

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 purchase the items. You will also be given priorities to decide. Thus, you need to grab the items with the highest priority first. This is the shopping list with items and their priorities:

Eggs (4)

Bread (2)

Milk (6)

Meat (1)

Detergent (5)

Water (3)

For small lists, it is easy to arrange the products manually 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 repeat the same 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 do we have?

Group A ordered

Pivot (in the 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 sorting with only 4 steps and got your sorted shopping list by priority.

Conclusion

So that was all about examples of quick sort in C and other popular programming languages. Like other sorting algorithms, quicksort has its own advantages and disadvantages. So, first, underline your requirements and then choose wisely!

People are also reading:

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 *