Section 26.16 Vocabulary and Comparison
Subsection 26.16.1 Comparison Based Sorts
Here is a summary of the comparison based sorting algorithms:
| Algorithm | Best Case | Average Case | Worst Case | Stable? | Notes |
|---|---|---|---|---|---|
| Selection Sort | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | No | |
| Insertion Sort | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | Yes | |
| Merge Sort | \(O(n \cdot log n)\) | \(O(n \cdot log n)\) | \(O(n \cdot log n)\) | Yes | Requires \(O(n)\) space |
| Quick Sort | \(O(n \cdot log n)\) | \(O(n \cdot log n)\) | \(O(n^2)\) | No |
Subsection 26.16.2 Vocabulary
- adaptive sort
- A sorting algorithm that takes advantage of existing order in its input to improve efficiency.
- binary search
- An efficient algorithm for finding an item in a sorted collection by repeatedly dividing the search interval in half.
- bucket sort
- A sorting algorithm that distributes elements into a number of buckets and then reassembles the buckets into a sorted collection.
- comparison sort
- A sorting algorithm that determines the order of elements based solely on comparisons between them.
- insertion sort
- A simple sorting algorithm that builds a sorted array one element at a time by repeatedly taking the next element from the input and inserting it into the correct position in the sorted portion.
- linear search
- A simple algorithm for finding an item in a collection by checking each item one by one until the desired item is found or the end of the collection is reached.
- merge sort
- A divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves back together.
- quick sort
- A divide-and-conquer sorting algorithm that selects a ’pivot’ element and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot, then recursively sorts the sub-arrays.
- radix sort
- A non-comparative sorting algorithm that sorts numbers or strings by processing individual digits.
- selection sort
- A simple sorting algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion of the list and moves it to the end of the sorted portion.
- stable sort
- Any sorting algorithm that preserves the relative order of records with “equal” values.
You have attempted of activities on this page.
