CSCI$3320$ Written Assignment $\backslash$#$2$

Topic $2$: Sorting Algorithms

$1.(5$ points$)$ Answer the following questions:

a$.(3$ points$)$ Find the number of inversions for the following input:

b$.(2$ points$)$ By swapping $13$ and $2,$ how many inversions will be removed? $($including the inversions possibly created by the swap$)$

$2.(20$ points$)$ Sort $\backslash (3,4,18,13,1,5,12,9,2\backslash ),$ and $7$ using

a$.(5$ pts$)$ insertion sort. Find the number of swaps in each phase.

b$.(5$ pts$)$ shell sort using the increments $\backslash (\backslash \{1,3,7\backslash \}\backslash ).$ Find the number of swaps