Define each of the key terms listed in the chart below.

Explain the reason for using the term non-decreasing or non-increasing when discussing sorting (10.1).

Discuss the single most important attribute of a key field when sorting composite lists of data (10.1).

Describe what the swap procedure accomplishes with two records in an array (10.2).

Describe what the shift procedure accomplishes with elements in an array (10.2).

Explain how the insertion sort works. Be sure to include a description of how a boundary can be moved in a single array to help keep the sorted data separate from the unsorted data (10.2).

Explain how the selection sort works. Be sure to include a description of how the algorithm selects and manages the unsorted and sorted data (10.3).

Explain how the bubble sort works (10.4).

Discuss how the concept of successive refinement was applied to the development of the bubble sort algorithm (10.4).

Describe how the basic bubble sort algorithm can be improved (10.4).

Generally compare the running times of the insertion sort, selection sort, and bubble sort algorithms, and describe whether they behave as n² sorts or as n (log n) sorts (10.5).

Explain how a merge sort works (10.6).

Describe the running time of the merge sort (10.6).

Briefly describe how the recursion procedes in the merge sort (10.6).

State the three general principles needed when adopting a recursive approach to solving a problem (10.6).

Explain how a quicksort works (10.7).

Describe why the quicksort is considered a recursive sort (10.7).

Given the typical trace output from a running program, state which of the following sort algorithms generated the output: insertion sort, selection sort, bubble sort (10.2 - 10.4).

Explain how the merge sort satisfies the requirements of a recursive approach (10.6).

From memory, generate one of the sort algorithms presented in this chapter.