Hoare 's vs Lomuto partition scheme in QuickSort | This function takes first element as pivot , and places all the elements smaller than the pivot on the left side and all the elements greater than the pivot on the right side . It returns the index of the last element on the smaller side ; Find leftmost element greater than or equal to pivot ; Find rightmost element smaller than or equal to pivot ; If two pointers met . ; The main function that implements QuickSort arr -- > Array to be sorted , low -- > Starting index , high -- > Ending index ; pi is partitioning index , arr [ p ] is now at right place ; Separately sort elements before partition and after partition ; Function to pran array ; Driver code
def partition ( arr , low , high ) : NEW_LINE INDENT pivot = arr [ low ] NEW_LINE i = low - 1 NEW_LINE j = high + 1 NEW_LINE while ( True ) : NEW_LINE INDENT i += 1 NEW_LINE while ( arr [ i ] < pivot ) : NEW_LINE INDENT i += 1 NEW_LINE DEDENT j -= 1 NEW_LINE while ( arr [ j ] > pivot ) : NEW_LINE INDENT j -= 1 NEW_LINE DEDENT if ( i >= j ) : NEW_LINE INDENT return j NEW_LINE DEDENT arr [ i ] , arr [ j ] = arr [ j ] , arr [ i ] NEW_LINE DEDENT DEDENT def quickSort ( arr , low , high ) : NEW_LINE INDENT if ( low < high ) : NEW_LINE INDENT pi = partition ( arr , low , high ) NEW_LINE quickSort ( arr , low , pi ) NEW_LINE quickSort ( arr , pi + 1 , high ) NEW_LINE DEDENT DEDENT def printArray ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT arr = [ 10 , 7 , 8 , 9 , 1 , 5 ] NEW_LINE n = len ( arr ) NEW_LINE quickSort ( arr , 0 , n - 1 ) NEW_LINE print ( " Sorted ▁ array : " ) NEW_LINE printArray ( arr , n ) NEW_LINE