3 | C ++ program for 3 - way quick sort ; A utility function to print an array ; It uses Dutch National Flag Algorithm ; To handle 2 elements ; update i and j ; j = mid ; or high + 1 ; 3 - way partition based quick sort ; if ( low >= high ) 1 or 0 elements ; Note that i and j are passed as reference ; Recur two halves ; Driver Code ; int a [ ] = { 4 , 39 , 54 , 14 , 31 , 89 , 44 , 34 , 59 , 64 , 64 , 11 , 41 } ; int a [ ] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } ; int a [ ] = { 91 , 82 , 73 , 64 , 55 , 46 , 37 , 28 , 19 , 10 } ; int a [ ] = { 4 , 9 , 4 , 4 , 9 , 1 , 1 , 1 } ; ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void swap ( int * a , int * b ) { int temp = * a ; * a = * b ; * b = temp ; } void printarr ( int a [ ] , int n ) { for ( int i = 0 ; i < n ; ++ i ) printf ( " % d ▁ " , a [ i ] ) ; printf ( " STRNEWLINE " ) ; } void partition ( int a [ ] , int low , int high , int & i , int & j ) { if ( high - low <= 1 ) { if ( a [ high ] < a [ low ] ) swap ( & a [ high ] , & a [ low ] ) ; i = low ; j = high ; return ; } int mid = low ; int pivot = a [ high ] ; while ( mid <= high ) { if ( a [ mid ] < pivot ) swap ( & a [ low ++ ] , & a [ mid ++ ] ) ; else if ( a [ mid ] == pivot ) mid ++ ; else if ( a [ mid ] > pivot ) swap ( & a [ mid ] , & a [ high -- ] ) ; } i = low - 1 ; } void quicksort ( int a [ ] , int low , int high ) { return ; int i , j ; partition ( a , low , high , i , j ) ; quicksort ( a , low , i ) ; quicksort ( a , j , high ) ; } 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 ; }