#include

#include

#include

#include

using namespace std;

static long comparisons $=0$;

static long swaps $=0$;

void swap$($int$*$ a$,$ int$*$ b$)$

$\{$

int temp $=*$a;

$*$a $=*$b;

$*$b $=$ temp;

swaps$++$;

$\}$

void selectionSort$($int$*$ first, int$*$ last$)$

$\{$

for $($int$*$ i $=$ first; i $<$ last $-1$; $++$i$)\{$

int$*$ minIndex $=$ i;

for $($int$*$ j $=$ i $+1$; j $<$ last; $++$j$)\{$

comparisons$++$;

if $(*$j $<*$minIndex$)\{$

minIndex $=$ j;

$\}$

$\}$

if $($minIndex $!=$ i$)\{$

swap$($i$,$ minIndex$)$;

$\}$

$\}$

$\}$

void insertionSort$($int$*$ first, int$*$ last$)$

$\{$

for $($int$*$ i $=$ first $+1$; i $<$ last; $++$i$)\{$

int key $=*$i;

int$*$ j $=$ i $-1$;

comparisons$++$;

while $($j $>=$ first && $*$j $>$ key$)\{$

$*($j $+1)=*$j;

j$--$;

swaps$++$;

$\}$

$*($j $+1)=$ key;

$\}$

$\}$

$//$ Helper function for quicksort partitioning

int partition$($int$*$ first, int$*$ last$)$

$\{$

int pivot $=*$first;

int$*$ i $=$ first $+1$;

int$*$ j $=$ last $-1$;

while $($i $<=$ j$)\{$

comparisons$++$;

while $($i $<=$ j && $*$i $<=$ pivot$)\{$

i$++$;

$\}$

comparisons$++$;

while $($i $<=$ j && $*$j $>$ pivot$)\{$

j$--$;

$\}$

if $($i $<$ j$)\{$

swap$($i$,$ j$)$;

$\}$

$\}$

swap$($first$,$ j$)$;

return j $-$ first;

$\}$

void quickSortHelper$($int$*$ first, int$*$ last$)$

$\{$

if $($first $<$ last $-1)\{$

int pivotIndex $=$ partition$($first$,$ last$)$;

quickSortHelper$($first$,$ first $+$ pivotIndex$)$;

quickSortHelper$($first $+$ pivotIndex $+1,$ last$)$;

$\}$

$\}$

void quickSort$($int$*$ first, int$*$ last$)$

$\{$

quickSortHelper$($first$,$ last$)$;

$\}$

int main$($int argc, char$**$ argv$)$

$\{$

$//...($unchanged code$)$

$//$ Uncomment for level $3$ and $4$

cout $<<$ "Comparisons: $"<<$ comparisons $<<\text{'}$

$\text{'}$;

cout $<<$ "Swaps: $"<<$ swaps $<<\text{'}$

$\text{'}$;

delete$[]$ data;

return $0$;

$\}$