Quick sort in C C++

The popular one

Also known as Selection-exchange sort, and Partition-exchange sort

Explanation

Take first element as pivot and assign it to x.

Take two pointers. i and j. i at first element and j at last element. Increment i till a greater element than pivot is obtained and decrement j until smaller element than pivot is obtained.

Obtained required elements

Element at i is greater than pivot and element at j is smaller than pivot.

Now swap these two elements and continue incrementing i and decrementing j till j is not smaller than i.

Swapped. Obtained next pair of elements.

Again found the elements. Now swap them.

Swapped
Obtained next pair of elements.

Again obtained required elements at i and j. Swap them now and further increment i and decrement j.

Stopping condition. j<i;

Stop now as j < i.

Swap the pivot element and element at j.

Swapped pivot and element at j.

We can observe that 50 is positioned at its sorted position, that is the position at which it will be present in the sorted list.

Now the list is divided into two sections.

Now call the QuickSort function recursively on the left and right sublist.

The final outcome of the recursive will be a sorted array.

As the list is dividing or splitting into 2 sublists, time complexity of average case is O(nlogn) and not O(n^2).

Important points

  • Quick sort is a self sorting technique
  • Each element sorts itself to a position such that all elements preceding this element is smaller than it and all the elements succeeding is greater than it.
  • Therefore each element finds a perform spot for itself and hence the list gets sorted.
  • Time complexity is O(nlogn) for best and average case and O(n^2) for the worst case.
  • Best case scenario is when partitioning takes place around the middle of the list.
  • Worst case scenario is when partitioning takes place at either of the two ends.
  • Not adaptive
  • Not stable

Program for Quick sort in C language

#include<stdio.h>
#include<stdlib.h>

void swap(int *p, int *q)
{
    int temp;
    temp = *p;
    *p = *q;
    *q = temp;
}

int partition(int A[],int l,int h)
{

int pivot=A[l];
int i=l,j=h;
do
{
do{i++;}while(A[i]<=pivot);
do{j--;}while(A[j]>pivot);
if(i<j)swap(&A[i],&A[j]);
}while(i<j);
swap(&A[l],&A[j]);
return j;
}


void QuickSort(int A[],int l, int h)
{
    int j;
  if(l<h)
 {
 j=partition(A,l,h);
 QuickSort(A,l,j);
 QuickSort(A,j+1,h);
 }
}


int main()
{
    int A[11] = {1,5,2,1,6,3,6,2,5,10};
    int i;
     A[10] = INT32_MAX;
    QuickSort(A,0,10);
    for(i=0;i<10;i++)
    {
        printf("%d ",A[i]);
    }
    return 0;
}

Other sorting algorithms

Count sort in C/C++

Merge sort in C/C++

Quick Sort in C/C++

Selection sort in C/C++

Insertion Sort in C/C++

Bubble Sort in C/C++

Criteria for sorting analysis

LEAVE A REPLY