Home » Data Structure

Complete algorithm of Quick Sort in Data Structure

In this article, we are going to learn about quick sort, how it works and its algorithm? By Manu Jemini, on January 15, 2018

What is Quick Sort in Data Structure?

Quicksort is one the very popular sorting algorithm or technique to sort a collection of data. Quicksort is better because of few decent reasons.

1. It does not need any temporary storing memory; which means if you don’t need to invest any more storage capacity during the process. It makes sense when your data is quite large.
2. It is very fast because it uses divide and conquers. In this algorithm, we choose a pivot and divide it into two sub-arrays and then repeat the process again.

Quick Sort Example

The example shows it clearly that first choose the pivot which is 5 in the array 6 1 4 3 5 7 9 2 8 0. Now start from the first index and check if it’s greater than the pivot, if you found a greater element which 6 in our case, 6 1 4 3 5 7 9 2 8 0. We will replace it with the element which is lower than the pivot and is in the right side of the pivot or the pivot itself in some case.

When all the elements which are smaller than the pivot are on the left side and all the elements which are bigger than the pivot are on the right side, at that point we call the Quicksort function again with the different indices.

This approach makes it possible to process in the sub-array without conflict the other elements of the main array.

Pseudo Code of Quicksort Algorithm

quick(arr,first,last)

arr: is an array contains last elements
piv: contains pivot key
low/first: holds index of  lower bound
high/last: holds index of upper bound

step 1:[initialization]
  set	low=first
  set high=last
[Take the mid element of sublist as piv]
  set piv=arr[(first+last)/2]

[Loop till pivot is placed at proper place in the sublist]

step 2: repeat step (3) to step (5) while low<=high

step 3: [Compare from  left side]
    repeat step (i)
        while( arr[low]< piv )
          i) set low=low+1
    [end of step 3 loop]

step 4: [Compare from  right side]
    repeat step (i)
        while( arr[high]> piv )
          i)	set high=high -1
    [end of step 4 loop]

step 5: [swaping]
    if( low<=high ) then
    set temp=arr[low]
    set arr[low]=arr[high]
    set arr[high]=temp
    set low=low+1
    set high=high-1
    [end of if statement]
[end of step (2) while loop]

step 6:[apply same process on sublist]
    if(first<high) then
    call quick(arr,first,high)
    [end of if statement]
    if(low<last) then
    quick(arr,low,last)
    [end of if statement]
step 7 return

Implementation of Quick Sort Using C

#include <stdio.h>

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

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 quick_sort(int arr[], int low, int high)
{
    if (low < high) {
        int q = partition(arr, low, high);

        quick_sort(arr, low, q - 1);
        quick_sort(arr, q + 1, high);
    }
}

int main()
{
    int arr[] = { 10, 80, 30, 90, 40, 50, 70 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("After performing quick sort:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    quick_sort(arr, 0, n - 1);

    printf("\nAfter performing quick sort:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

Output

After performing quick sort:
10 80 30 90 40 50 70 
After performing quick sort:
10 30 40 50 70 80 90