7.13. Glossary¶
- bubble sort¶
sorting method that makes multiple passes through a collection, comparing adjacent items, and swaps items that are out of order
- gap¶
an increment used to divide a collection into subsets without breaking apart the collection during a shell sort
- insertion sort¶
sorting method that maintains a sorted and unsorted subset of a collection and inserts elements from the unsorted subset into the sorted subset
- median of three¶
method of choosing the pivot value for a quick sort by taking the median of the first, middle, and last element of a collection
- merge¶
part of merge sort that takes two smaller sorted subsets and combines them
- merge sort¶
sorting method that uses recursion to split a collection in half until there is one item and then combines the smaller subsets back into larger sorted subsets
- partition¶
process of quick sort that that finds the split point and moves items to the appropriate side of the collection, either less than or greater than the pivot value
- pivot value¶
value selected in a collection during quick sort in order to split a collection
- selection sort¶
sorting method that makes multiple passes through a collection, taking the largest (ascending) or smallest (descending) unsorted element and places it into its correct place by swapping places with the next largest or lowest element
- shell sort¶
sorting method that divides the collection into subsets, sorts the subsets individually using insertion sort, then also sorts the combination of the sorted subsets using insertion sort
- short bubble¶
a modified bubble sort that stops if there are no exchanges to do
- sorting¶
the process of placing elements from a collection in some kind of order
- split point¶
the position of the pivot value in the sorted collection; used to divide the collection for subsequent calls to quick sort
- quick sort¶
sorting method that uses recursion to split a collection in half (without using extra space) and places elements on the proper side of the split point
7.14. Matching¶
-
Q-1: Drag the word on the left to its corresponding definition
Review classes and their properties
- bubble sort
- Makes multiple passes through a collection, comparing adjacent items, and swaps items that are out of order
- short bubble
- Stops if there are no exchanges to do
- shell sort
- Divides the collection into subsets, sorts the subsets individually using insertion sort, then also sorts the combination of the sorted subsets using insertion sort
- sorting
- Process of placing elements from a collection in some kind of order
- split point
- Position of the pivot value in the sorted collection; used to divide the collection for subsequent calls to quick sort
- quick sort
- Uses recursion to split a collection in half and places elements on the proper side of the split point
- gap
- Used to divide a collection into subsets without breaking apart the collection during a shell sort
- insertion sort
- Maintains a sorted and unsorted subset of a collection and inserts elements from the unsorted subset into the sorted subset
- median of three
- Method of choosing the pivot value for a quick sort by taking the median of the first, middle, and last element of a collection
- merge
- Takes two smaller sorted subsets and combines them
- merge sort
- Uses recursion to split a collection in half until there is one item and then combines the smaller subsets back into larger sorted subsets
- partition
- Finds the split point and moves items to the appropriate side of the collection, either less than or greater than the pivot value
- pivot value
- Value selected in a collection during quick sort in order to split a collection
- selection sort
- Makes multiple passes through a collection, taking the largest or lowest unsorted element and places it into its correct place by swapping places with the next largest or lowest element