Implementing QuickSort Algorithm

Views 186

About:

Like Merge Sort, QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

Program:

// simple C program for Quick Sort
# include <stdio.h>

// to swap two numbers
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/*  
    a[] is the array, p is starting index, that is 0, 
    and r is the last index of array.  
*/
void quicksort(int a[], int p, int r)    
{
    if(p < r)
    {
        int q;
        q = partition(a, p, r);
        quicksort(a, p, q);
        quicksort(a, q+1, r);
    }
}

int partition (int a[], 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 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);
}

// 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 function
    quickSort(arr, 0, n-1);
    
    printf("Sorted array: n");
    printArray(arr, n);
    return 0;
}
 

Output:

Output :

Sorted List of elements

Explanation:

How Quick Sorting Works?

Following are the steps involved in quick sort algorithm:

  1. After selecting an element as pivot, which is the last index of the array in our case, we divide the array for the first time.
  2. In quick sort, we call this partitioning. It is not simple breaking down of array into 2 subarrays, but in case of partitioning, the array elements are so positioned that all the elements smaller than the pivot will be on the left side of the pivot and all the elements greater than the pivot will be on the right side of it.
  3. And the pivot element will be at its final sorted position.
  4. The elements to the left and right, may not be sorted.
  5. Then we pick subarrays, elements on the left of pivot and elements on the right of pivot, and we perform partitioning on them by choosing a pivot in the subarrays.

Let's consider an array with values {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}

Below, we have a pictorial representation of how quick sort will sort the given array.

Quick Sort Algorithm

In step 1, we select the last element as the pivot, which is 6 in this case, and call for partitioning, hence re-arranging the array in such a way that 6 will be placed in its final position and to its left will be all the elements less than it and to its right, we will have all the elements greater than it.

Then we pick the subarray on the left and the subarray on the right and select a pivot for them, in the above diagram, we chose 3 as pivot for the left subarray and 11 as pivot for the right subarray.

And we again call for partitioning.

Share Me:

Program List

Data Structure Programming Lists
1.  Implementation of Quicksort Algorithm using C 2.  Tree Traversal in C Programming Language 3.  C Program of polynomial addition and multiplication using linked list 4.  C Program to concatenate two circular linked lists 5.  C Program to concatenate two single linked lists 6.  C Program of sorting a singly linked list 7.  Program of merging two sorted single linked lists 8.  C Program of sorted linked list 9.  C Program of the single linked list with header node 10.  C Program of circular linked list 11.  C Program of doubly linked list 12.  C Program of single linked list 13.  C Program of the queue using the circular linked list 14.  C Program of the circular queue 15.  C Program of dequeue using a circular array 16.  C Program of reversing a string using stack 17.  C Program of priority queue using a linked list 18.  Program of queue using linked list 19.  Program of queue using array 20.  Program of stack using linked list 21.  Program of stack using array 22.  Array limit value and an array element address are printed in this program 23.  Implementation of insertion sort in c programming language 24.  C Program to Read Array Elements 25.  C Program to Print Array Elements 26.  How to add array Elements with a constant 27.  Multiply all elements in an array 28.  How to add only the even elements in the array 29.  How to add only the odd elements in the array 30.  How to add an element to every element of the array 31.  How to subtract an element form every element of the array 32.  How to multiply an element to every element of the array 33.  How to divide an element from every element of the array 34.  How to square each element of the array 35.  Add all element in the array 36.  C Program to Delete an element from the specified location from Array 37.  C Program to Insert an element in an Array 38.  C Program to Copy all elements of an array into Another array 39.  C Program to Search an element in Array 40.  C Program to Merge Two arrays in C Programming 41.  C Program to Reversing an Array Elements in C Programming 42.  C Program to Find Largest Element in Array in C Programming 43.  C Program to Find Smallest Element in Array in C Programming 44.  C Program to Calculate Addition of All Elements in Array 45.  C Program to Delete duplicate elements from an array 46.  C Program to Read integers into an array and Reversing them using Pointers 47.  Bubble sort algorithm implementation in C 48.  Bubble sort in C language using function 49.  C program for implementation of selection sort input taken inside program 50.  Selection sort algorithm implementation in C 51.  C Program to Sort Elements Using Selection Sort Algorithm 52.  Selection Sort Program in C using different function 53.  Merge Sort program in the data structure 54.  Implementing QuickSort Algorithm