Problem Solving with Algorithms and Data Structures using C++ The PreTeXt Interactive Edition

Glossary 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.

🔗