The Quicksort algorithm

The Quicksort algorithm is a fast sorting algorithm which divides a large array into two smaller sub arrays, which are the low elements and the high elements. The advantage with the quicksort is that is can recursively sort the sub arrays. This is faster than the bubble sort algorithm as it requires to go through several passes through the data to determine of the values need to be swapped.

The steps of the QuickSort algorithm follows

  1. Make the right most index value pivot
  2. Partition the array using the pivot value
  3. Quicksort the left partition recursively
  4. Quicksort the right partition recursively

quicksort diagram

Quicksort diagram from Hacker rank

Code sample in C++

//QuickSort<!--DVFMTSC--> Algoritm<!--DVFMTSC--> Application

#include<!--DVFMTSC--> <!--DVFMTSC--><iostream<!--DVFMTSC-->>

using<!--DVFMTSC--> namespace<!--DVFMTSC--> std;

int<!--DVFMTSC--> quickSort(int[],<!--DVFMTSC--> int,<!--DVFMTSC--> int);

int<!--DVFMTSC--> partition(int[],<!--DVFMTSC--> int,<!--DVFMTSC--> int,<!--DVFMTSC--> int<!--DVFMTSC-->&);

int<!--DVFMTSC--> main()
{
int<!--DVFMTSC--> array[]<!--DVFMTSC--> =<!--DVFMTSC--> {7,<!--DVFMTSC--> 8,<!--DVFMTSC--> 10,<!--DVFMTSC--> 1,<!--DVFMTSC--> 5,<!--DVFMTSC--> 6};
int<!--DVFMTSC--> size<!--DVFMTSC--> =<!--DVFMTSC--> sizeof(array)/sizeof(array[0]);

/*
first<!--DVFMTSC--> and<!--DVFMTSC--> last<!--DVFMTSC--> indices<!--DVFMTSC--> are<!--DVFMTSC--> passed
idea<!--DVFMTSC--> is<!--DVFMTSC--> to<!--DVFMTSC--> move<!--DVFMTSC--> lower<!--DVFMTSC--> elements<!--DVFMTSC--> to<!--DVFMTSC--> the<!--DVFMTSC--> left<!--DVFMTSC--> of<!--DVFMTSC--> the<!--DVFMTSC--> list/pivot
*/

int<!--DVFMTSC--> swaps<!--DVFMTSC--> =<!--DVFMTSC--> quickSort(array,<!--DVFMTSC--> 0,<!--DVFMTSC--> size<!--DVFMTSC-->−1);

std::cout<!--DVFMTSC--> <!--DVFMTSC--><<!--DVFMTSC--><<!--DVFMTSC--> "Minimum<!--DVFMTSC--> Swaps<!--DVFMTSC--> are:\n<!--DVFMTSC--> "<!--DVFMTSC--> <!--DVFMTSC--><<!--DVFMTSC--><<!--DVFMTSC--> swaps;

for(int<!--DVFMTSC--> i<!--DVFMTSC--> =<!--DVFMTSC--> 0;<!--DVFMTSC--> i<!--DVFMTSC--> <!--DVFMTSC--><<!--DVFMTSC--> size;<!--DVFMTSC--> i++)
{
std::cout<!--DVFMTSC--> <!--DVFMTSC--><<!--DVFMTSC--><<!--DVFMTSC--> array[i]<!--DVFMTSC--> <!--DVFMTSC--><<!--DVFMTSC--><<!--DVFMTSC--> "<!--DVFMTSC--> ";
}
}

int<!--DVFMTSC--> quickSort(int<!--DVFMTSC--> array[],<!--DVFMTSC--> int<!--DVFMTSC--> start,<!--DVFMTSC--> int<!--DVFMTSC--> end)
{
int<!--DVFMTSC--> swaps<!--DVFMTSC--> =<!--DVFMTSC--> 0;
if(start<!--DVFMTSC--> <!--DVFMTSC--><<!--DVFMTSC--> end)
{
int<!--DVFMTSC--> pIndex<!--DVFMTSC--> =<!--DVFMTSC--> partition(array,<!--DVFMTSC--> start,<!--DVFMTSC--> end,<!--DVFMTSC--> swaps);

//after<!--DVFMTSC--> each<!--DVFMTSC--> call<!--DVFMTSC--> one<!--DVFMTSC--> number(the<!--DVFMTSC--> PIVOT)<!--DVFMTSC--> will<!--DVFMTSC--> be<!--DVFMTSC--> at<!--DVFMTSC--> its<!--DVFMTSC--> final<!--DVFMTSC--> position
swaps<!--DVFMTSC--> +=<!--DVFMTSC--> quickSort(array,<!--DVFMTSC--> start,<!--DVFMTSC--> pIndex<!--DVFMTSC-->−1);
swaps<!--DVFMTSC--> +=<!--DVFMTSC--> quickSort(array,<!--DVFMTSC--> pIndex+1,<!--DVFMTSC--> end);
}
return<!--DVFMTSC--> swaps;
}

int<!--DVFMTSC--> partition(int<!--DVFMTSC--> array[],<!--DVFMTSC--> int<!--DVFMTSC--> start,<!--DVFMTSC--> int<!--DVFMTSC--> end,<!--DVFMTSC--> int<!--DVFMTSC-->&<!--DVFMTSC--> swaps)
{
int<!--DVFMTSC--> pivot<!--DVFMTSC--> =<!--DVFMTSC--> array[end];
int<!--DVFMTSC--> pIndex<!--DVFMTSC--> =<!--DVFMTSC--> start;

for(int<!--DVFMTSC--> i<!--DVFMTSC--> =<!--DVFMTSC--> start;<!--DVFMTSC--> i<!--DVFMTSC--> <!--DVFMTSC--><<!--DVFMTSC--> end;<!--DVFMTSC--> i++)
{
if(array[i]<!--DVFMTSC--> <!--DVFMTSC--><=<!--DVFMTSC--> pivot)
{

if(pIndex<!--DVFMTSC--> !=<!--DVFMTSC--> i)
{
std::swap(array[i],<!--DVFMTSC--> array[pIndex]);
swaps++;
}
pIndex++;
}
}
if(pIndex<!--DVFMTSC--> !=<!--DVFMTSC--> end)
{
std::swap(array[pIndex],<!--DVFMTSC--> array[end]);
swaps++;
}
return<!--DVFMTSC--> pIndex;
}

Share this post