CS 1332 Certification Questions and CORRECT Answers

CS 1332 Certification Questions and CORRECT Answers Adaptive✔✔✔ faster when data is already sorted Stable✔✔✔ equal valued elements are in the same relative order before and after sorting In-Place✔✔✔ does not need an additional data structure besides the array already storing the data. O(1) extra memory Iterative Sorts ✔✔✔ sort one at a time Divide and Conquer Sorts ✔✔✔ break the original l arge problem into sub -problems, solve, and then combine solutions to solve large problem (mostly recursive) Non-Comparison Based Sorts ✔✔✔ at no point can we compare two objects Bubble Sort Qualities: ✔✔✔ Adaptive, Stable, In -Place Insertion Sort Qualities: ✔✔✔ Adaptive, Stable, In -Place Selection Sort Qualities: ✔✔✔ In-Place CocktailShaker Sort Qualities: ✔✔✔ Adaptive, Stable, In -Place Heap Sort Qualities: ✔✔✔ None Merge Sort Qualities: ✔✔✔ Stable Quick Sort Qualities: ✔✔✔ In-Place Quick Select Sort Qualities: ✔✔✔ In-Place LSD Radix Sort Qualities: ✔✔✔ Stable Bubble Sort Runtime: ✔✔✔ Best: O(n) Avg: O(n^ 2) Worst: O(n^ 2) Insertion Sort Runtime: ✔✔✔ Best: O(n) Avg: O(n^ 2) Worst: O(n^ 2) Selection Sort Runtime: ✔✔✔ Best: O(n^ 2) Avg: O(n^ 2) Worst: O( n^2) CocktailShaker Sort Runtime: ✔✔✔ Best: O(n) Avg: O(n^ 2) Worst: O(n^ 2) Heap Sort Runtime: ✔✔✔ Best: O(nlogn) Avg: O(nlogn) Worst: O(nlogn) Merge Sort Runtime: ✔✔✔ Best: O(nlogn) Avg: O(nlogn) Worst: O(nlogn) Quick Sort Runtime: ✔✔✔ Best: O(nlogn) Avg: O(nlogn) Worst: O(n^ 2) Quick Select Sort Runtime: ✔✔✔ Best: O(n) Avg: O(n) Worst: O(n^ 2) LSD Radix Sort Runtime: ✔✔✔ Best: O(kn) Avg: O(kn) Worst: O(kn) Brute Force Runtime: ✔✔✔ Best: O(n) Avg: O(nm) Worst: O(nm) Boyer-Moore with Galil Rule Runtime: ✔✔✔ Best: O(n+m) Avg: O(n+m) Worst: O(n+m) Boyer -Moore without Galil Rule Runtime: ✔✔✔ Best: O(m) Avg: O(nm) Worst: O(nm)