Quick Sort

Quick Sort

QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.

How does QuickSort work?

The key process in quickSort is a partition(). The target of partitions is to place the pivot (any element can be chosen to be a pivot) at its correct position in the sorted array and put all smaller elements to the left of the pivot, and all greater elements to the right of the pivot.

Partition is done recursively on each side of the pivot after the pivot is placed in its correct position and this finally sorts the array.

Program:

#include <bits/stdc++.h>

using namespace std;

 

int partition(int arr[],int low,int high)

{

  //choose the pivot

   

  int pivot=arr[high];

  //Index of smaller element and Indicate

  //the right position of pivot found so far

  int i=(low-1);

   

  for(int j=low;j<=high;j++)

  {

    //If current element is smaller than the pivot

    if(arr[j]<pivot)

    {

      //Increment index of smaller element

      i++;

      swap(arr[i],arr[j]);

    }

  }

  swap(arr[i+1],arr[high]);

  return (i+1);

}

 

// The Quicksort function Implement

            

void quickSort(int arr[],int low,int high)

{

  // when low is less than high

  if(low<high)

  {

    // pi is the partition return index of pivot

     

    int pi=partition(arr,low,high);

     

    //Recursion Call

    //smaller element than pivot goes left and

    //higher element goes right

    quickSort(arr,low,pi-1);

    quickSort(arr,pi+1,high);

  }

}

              

  

int main() {

  int arr[]={10,7,8,9,1,5};

  int n=sizeof(arr)/sizeof(arr[0]);

  // Function call

  quickSort(arr,0,n-1);

  //Print the sorted array

  cout<<"Sorted Array\n";

  for(int i=0;i<n;i++)

  {

    cout<<arr[i]<<" ";

  }

  return 0;

}

Output: