Home > C++ > Quick Sort c++

Quicksort in c++

Quicksort is an algorithm for sorting the array. The quicksort algorithm belongs to the family of divide and conquer algorithms. It is an efficient sorting algorithm that works by selecting an input element (pivot) and then portioning the given array into two around that pivot element.  It is also called partition exchange sort. We can choose the pivot element in various ways:

  • 1- The first element as the pivot.
  • 2- Last element as the pivot.
  • 3- Middle element of the array.
  • 4- A random value from the array.
  • 5- Median of the array as the pivot.

 

Hoare Partitioning

A very common procedure for partitioning the array is Hoare Partitioning. It works as follow:

  • 1- Select the leftmost element as the pivot element.
  • 2- Define two variable i & j as pointers for scanning the array. i as left pointer and j as the right pointer.
  • 3- Scan the array from the right by decreasing the j until a value or element in the array appears which is smaller than or equal to the pivot value. Stop at this point.
  • 4- Scan the array from left by increasing the i until a value or element in the array appears which is greater than or equal to the pivot value. Stop at this point.
  • 5- Swap the values identified by i and j. i.e. swap those values where you stop i and j.
  • 6- Move i and j to the next places. i.e. increase i by 1 and decrease j by 1.
  • 7- Repeat the steps from 3 to step 6 until i<j.
  • 8- At termination partition the array at j.

 

Algorithm for the Quicksort

  • 1- Select a pivot element from the array.
  • 2- Place the pivot element at its correct position. Partition the array around that pivot element.
  • 3- Repeat the above two steps recursively.

Partition is the main process in quicksort. The quicksort algorithm works as:

For a given array my_arr and let n be its pivot element. Place the n at its correct position and then place all smaller value before it and all larger value after it. Quicksort algorithm works in a recursive way. I.e. partition the array at the pivot and then repeat the process i.e. again call the quicksort function and select pivot and partition the array.

Pseudo Code for Algorithm

quicksort (my_arr [], start, end)
{
     if (start < end)
     {
          // p is partitioning index, my_arr [pivot] is now at right place.
          p = partition (my_arr, start, end);
          //1st half of the array
          quicksort (my_arr, start, p - 1);
          //2nd half of the array.
          quicksort (my_arr, p + 1, end);
     }
}

Pseudo code for the Partition Function

partition (my_arr [], start, end)
{
     // Last element as pivot element
     pivot = my_arr [end];
     i = (start - 1)  // Index of smaller element
     for (j = start; j <= end - 1; j++)
     {
          // If current element is smaller than or equal to pivot
          if (my_arr [j] <= pivot)
          {
               i++;    // increment index of smaller element
               swap my_arr [i] and my_arr [j]
          }
     }
     swap my_arr [i + 1] and my_arr [end])
     return (i + 1)
}

Graphical representation of quicksort algorithm working

59100111

Take 5 (1st element) as the pivot element. Place it in its proper position.

15910011

Now partition the array around 5. We get the following two arrays.

15910011

Now working with the 1st array. Selecting 1 as the pivot element. As it is placed in its proper position. Now partitioning it will give us:

15

For the 2nd array again repeating the above steps. i.e. select a pivot element. This time we select 9 and it is at its right position. After partition we get:

910011

Working with 2nd array and selecting 100 as the pivot. Placing it in its right position.

11100

The partition will give us:

11100

Now combining all the individual elements will give us the sorted array.

  15911100

 

Quicksort C++ code

We can implement this algorithm in any programming language. Here is the program for quicksort in c++.

Quicksort C++ Code for Sorting Array in Ascending order

#include "stdafx.h"
#include "iostream"

using namespace std;
// Function to swap two elements of the array.
void swap(int* x, int* y)
{
       int temp = *x;
       *x = *y;
       *y = temp;
}
int partition(int my_arr[], int start, int end)
{
       int pivot = my_arr[end];    // pivot element
       int i = (start - 1);
       for (int j = start; j <= end - 1; j++)        
       {      
              if (my_arr[j] >= pivot)
              {
                     i++;
                     swap(&my_arr[i], &my_arr[j]);
              }
       }
       swap(&my_arr[i + 1], &my_arr[end]);
       return (i + 1);
}

void quickSort(int my_arr[], int start, int end)
{
       if (start < end)
       {
              int p = partition(my_arr, start, end);
              /* sort elements before
                and after partition*/
              quickSort(my_arr, start, p - 1);
              quickSort(my_arr, p + 1, end);
       }
}
void display(int arr[], int size)
{
       for (int i = 0; i < size; i++)
              cout<<arr[i] <<" ";
}

int main()
{
       int *arr;
       int size;
       cout << "Please enter the size of array: ";        
       cin >> size;
       arr = new int[size];
       cout << "Please Enter Values for array \n";
       for (int i = 0; i < size;i++) {
              cout << "Value at index " << i + 1 << " : ";       
              cin >> arr[i];
       }

       quickSort(arr, 0, size - 1);
       cout<<"Sorted array using quick sort : ";
       display(arr, size);
       cout << endl;
       return 0;
}

quicksort c++ code ascending

Quicksort C++ Code for Sorting Array in Descending order

Just like sorting the array in ascending order we can sort the array in descending order as well.

#include "stdafx.h"
#include "iostream"

using namespace std;
// Function to swap two elements of the array.
void swap(int* x, int* y)
{
       int temp = *x;
       *x = *y;
       *y = temp;
}
int partition(int my_arr[], int start, int end)
{
       int pivot = my_arr[end];    // pivot element
       int i = (start - 1);
       for (int j = start; j <= end - 1; j++)
       {
              // If current element is smaller than or equal to pivot
              if (my_arr[j] >= pivot)
              {
                     i++;
                     swap(&my_arr[i], &my_arr[j]);
              }
       }
       swap(&my_arr[i + 1], &my_arr[end]);
       return (i + 1);
}

void quickSort(int my_arr[], int start, int end)
{
       if (start < end)
       {
              int p = partition(my_arr, start, end);
              /* sort elements before
                and after partition*/
              quickSort(my_arr, start, p - 1);
              quickSort(my_arr, p + 1, end);
       }
}
void display(int arr[], int size)
{
       for (int i = 0; i < size; i++)
              cout<<arr[i] <<" ";
}

int main()
{
       int *arr;
       int size;
       cout << "Please enter the size of array: ";
       cin >> size;
       arr = new int[size];
       cout << "Please Enter Values for array \n";
       for (int i = 0; i < size;i++) {
              cout << "Value at index " << i + 1 << " : ";
              cin >> arr[i];
       }

       quickSort(arr, 0, size - 1);
       cout<<"Sorted array using quick sort : ";
       display(arr, size);
       cout << endl;
       return 0;
}

quicksort in c++ descending

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: