$($Q$1)[25$ pts$.]$ Solve Problem $4\mathrm{.}48($a$,$b$,$c$)$ from Baase$$s textbook, page $216.$

To sort or not to sort: Outline a reasonable method of solving each of the following problems. Give the order of the worst$-$case complexity of your methods.

You are given a pile of thousands of telephone bills and thousands of checks sent in to pay the bills. $($Assume telephone numbers are on the checks.$)$ Find out who didn$$t pay.

You are given an array in which each entry contains the title, author, call number, and publisher of all the books in a school library and another array of $30$ publishers. Find out how many of the books were published by each of those $30$ companies.

You are given an array containing checkout records of all the books checked out of the campus library during the past year. Determine how many distinct people checked out at least one book.

$($Q$2)[25$ pts$.]$ Solve Problem $4\mathrm{.}51($a$-$h$)$ from Baase$$s textbook, page $216.$

A sorting method is stable if equal keys remain in the same relative order in the sorted sequence as they were in the original sequence. $($That is$,$ a sort is stable if for any i $<$ j such that initially E$[$i$]=$ E$[$j$],$ the sort moves E$[$i$]$ to E$[$k$]$ and E$[$j$]$ to E$[$m$]$ for some k and m such that k $<$ m$.)$ Which of the following algorithms are stable? For each that is not stable, give the relative order of two equal keys is changed.

a$.$ Insertion Sort.

b$.$ Maxsort $($Exercise $4\mathrm{.}1).$

c$.$ Bubble Sort $($Exercise $4\mathrm{.}2).$

d$.$ Quicksort.

e$.$ Heapsort.

f$.$ Mergesort.

g$.$ Shellsort.

h$.$ Radix Sort.

$($Q$3)[25$ pts$.]$ Given the following file:

$24,8,77,2,61,12,57,13,49,18$

Sort this file by hand using Heapsort and answer the following questions:

$($a$)$ Draw the initial COMPLETE tree representation of the file BEFORE the HEAP is created.

$($b$)$ Draw the initial heap.

$($c$)$ Continue with the sort for two iterations PAST the initial heap $$ i$.$e$.,$ you pop off $77$ and $61$ from the root. NOW RESTRUCTURE THE HEAP AFTER $61$ is popped $$ what is the NEW ROOT?

$($Q$4)[25$ pts$.]$ Use Quicksort as shown in class and sort the following file by hand and selecting the first element as the split element:

$71,19,74,41,12,80,38,31,100,45,86,31,22$

$($a$)$ After the initial swapping, there are two subfiles $$ one to the left of $71$ and one to the right of $71.$ What are they in order?

$($b$)$ Continue sorting the entire file until totally sorted. During the entire sort $$ what was the maximum number of inversions removed by a single comparison and swap?

I want questions $3$ and $4$ to be less theoretical and should show work in detail.