Topical Information

This set of questions should help you firm up your knowledge of the common processes of searching thru data and sorting data into order.

Questions

  1. Do Programming Exercises P14.1, 2, and 4. (Yes, I said Programming exercises..! Just tell me the code that needs to change in each exercise. You don't have to actually compile and run it — unless you personally feel the need or want to.)
  2. Do Programming Exercise P14.8. (Yes, I said Programming exercise..! Just tell me the code that needs to change. You don't have to actually compile and run it — unless you personally feel the need or want to.)
  3. This space reserved to add more questions...maybe...

This question set is worth (Level 2).

Optional Questions

Do any of the following for an additional (Levels) as listed.

  1. Do Review Exercise R14.1 as a small (1-2 page) paper for (Level 1).

  2. Given this bubble sort pseudocode, compare and contrast the approaches of the selection, insertion, and bubble sorts in a small (1-2 page) paper for (Level 1.5).

  3. An often crucial aspect of a sorting algorithm is stability — that duplicate elements are kept in their original order. This becomes most important when you have multi-key data or multi-columnar data. Then if you sort on one key followed by another, the other parts of the data are still in their original relative sorted order.

    Consider, for instance, the following data:

        5    2400    10
    5    2000    11
    5    2300    12
    6    2000    10
    6    1700    11
    6    1800    12
    7    2100    10
    7    2200    11
    7    2000    12

    The first column is the sale person's id code, the second column their sales per month, and the third column the month in question. The data is currently sorted on id code. If we then sort the data on the sales column, we expect that equal sales amounts will remain in their current respective order:

        6    1700    11
    6    1800    12
    5    2000    11
    6    2000    10
    7    2000    12
    7    2100    10
    7    2200    11
    5    2300    12
    5    2400    10

    The question is, which of the sorts you've learned in Chapter 14 are stable? (Include selection, insertion, merge, and quick sorts in your discussion.) (Tip: It is easy to see that bubble sort is stable since it only compares neighbors and swaps them only if they are out of order. Thus a b element will swap thru a sequence of a elements leaving them relatively ordered but moving the b to its proper place on the other side of the whole group of as.)

    This 'booster', by the way, will probably also result in a small (1-2 page) paper and will be worth (Level 2.5).