Review - Chapter 10 - Searching and Sorting

1)        Suppose that, in a certain environment, a sort (or search) requires 0.4 s to sort (or search) a list of length 1000.

            a) Estimate the time that it would take to sort (or search) a similar list of length 150 000 using:

                        i) sequential search

                        ii) binary search

                        iii) insertion sort

                        iv) selection sort

                        v) Shellsort

b) Estimate the number of items that could be sorted or searched in one hour using the same searches and sorts from part (a).

2)        Given the following data, show how they would appear after they have been 3-sorted.

            15 85 93 11 84 19 29 39 99 54 27 18 77 84 12 95 31 44 54 55 88 32 72 48 75 49

3)        The following list is going to be sorted:

            15 85 93 11 84 19 29 39 99 54 27 18 77 84 12 95 31

            Show how the list would look after the first three passes of:

            a) selection sort

            b) insertion sort

4)        Fix the following selection sort so that it will sort the items as a selection sort should and in ascending order.

[5]

     public static void selectSort(double[] list)

     {

            int top = list.length - 1;

                  int largeLoc = top;

                  for (int i = 1; i <= top; i++)

                        if (list[i] < list[largeLoc])

                              largeLoc = i;

                  list[top] = list[largeLoc];

                 list[largeLoc] = list[top];

     }