3 | C ++ program for 3 - way quick sort ; This function partitions a [ ] in three parts a ) a [ l . . i ] contains all elements smaller than pivot b ) a [ i + 1. . j - 1 ] contains all occurrences of pivot c ) a [ j . . r ] contains all elements greater than pivot ; From left , find the first element greater than or equal to v . This loop will definitely terminate as v is last element ; From right , find the first element smaller than or equal to v ; If i and j cross , then we are done ; Swap , so that smaller goes on left greater goes on right ; Move all same left occurrence of pivot to beginning of array and keep count using p ; Move all same right occurrence of pivot to end of array and keep count using q ; Move pivot element to its correct index ; Move all left same occurrences from beginning to adjacent to arr [ i ] ; Move all right same occurrences from end to adjacent to arr [ i ] ; 3 - way partition based quick sort ; Note that i and j are passed as reference ; Recur ; A utility function to print an array ; Driver code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void partition ( int a [ ] , int l , int r , int & i , int & j ) { i = l - 1 , j = r ; int p = l - 1 , q = r ; int v = a [ r ] ; while ( true ) { while ( a [ ++ i ] < v ) ; while ( v < a [ -- j ] ) if ( j == l ) break ; if ( i >= j ) break ; swap ( a [ i ] , a [ j ] ) ; if ( a [ i ] == v ) { p ++ ; swap ( a [ p ] , a [ i ] ) ; } if ( a [ j ] == v ) { q -- ; swap ( a [ j ] , a [ q ] ) ; } } swap ( a [ i ] , a [ r ] ) ; j = i - 1 ; for ( int k = l ; k < p ; k ++ , j -- ) swap ( a [ k ] , a [ j ] ) ; i = i + 1 ; for ( int k = r - 1 ; k > q ; k -- , i ++ ) swap ( a [ i ] , a [ k ] ) ; } void quicksort ( int a [ ] , int l , int r ) { if ( r <= l ) return ; int i , j ; partition ( a , l , r , i , j ) ; quicksort ( a , l , j ) ; quicksort ( a , i , r ) ; } void printarr ( int a [ ] , int n ) { for ( int i = 0 ; i < n ; ++ i ) printf ( " % d ▁ " , a [ i ] ) ; printf ( " STRNEWLINE " ) ; } int main ( ) { int a [ ] = { 4 , 9 , 4 , 4 , 1 , 9 , 4 , 4 , 9 , 4 , 4 , 1 , 4 } ; int size = sizeof ( a ) / sizeof ( int ) ; printarr ( a , size ) ; quicksort ( a , 0 , size - 1 ) ; printarr ( a , size ) ; return 0 ; }