Lab $2$: Implementation of Quick Sort

Write a C$++$ program that will take N number of data as input into an array and sort them using quick sort

Function QuickSort and LomutoPartition

void QuickSort$($Data $*$A$,$ int p$,$ int r$)$;

int LomutoPartition$($Data $*$ arr, int lo$,$ int hi$)$;

Psuedocode for QuickSort

QUICKSORT$($A$,$ p$,$ r$)$

if$($p $<$ r$)$

q $$ LomutoPartition$($A$,$ p$,$ r$)//$ q index for part

QUICKSORT$($A$,$ p$,$ q$-1)//$ recursive call

QUICKSORT$($A$,$ q$+1,$ r$)//$ recursive call

Pseudocode for Lomuto Partition

LomutoPartition$($arr$,$ lo$,$ hi$)$

pivot $=$ arr$[$hi$]$

i $$ lo$-1//$ place for swapping

for j $$ lo to hi $1$

if arr$[$j$]<=$ pivot

i $$ i $+1$

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

swap arr$[$i$+1]$ with arr$[$hi$]$

return i$+1$

$//$ Header files

typedef int Data;

$//$ Declare both functions

int main$()$

$\{$

Data $*$ A;

int N; $//$ N is number of data

$//$ get value for N

A $=$ new Data $[$N$]$;

$//$ Get all N values of A

$//$ Call Quicksort

$//$ Display sorted array

return $0$;

$\}$

$//$ Define the functions