Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
132 Sort
Sorting algorithms for cmsc132 final exam
| Term | Definition |
|---|---|
| Bubble Sort Worst Case | O(n^2) |
| Bubble Sort Best Case | O(n) |
| Is Bubble Sort In-Place? Stable? | Yes in place Yes stable |
| Bubble Sort Average Case | O(n^2) |
| Explain how Bubble Sort works. Is it D&C or Comparison based? | checks the element nearest to it and swaps them if the one next to it is smaller. This makes it so the largest elements bubble up into their correct place Comparison based |
| Selection Sort worst case | O(n^2) |
| Selection Sort best case | O(n^2) |
| Selection sort average case | O(n^2) |
| Explain how Selections sort works. Is it D&C or comparison based? | Selection sort takes the element at the current index, finds the smallest element in the array in the current index and up, and swaps it with the current value. Comparison based. |
| Is selection sort in place? stable? | Yes in place Not stable |
| Insertion Sort worse case | O(n^2) |
| Insertion Sort best case | O(n) |
| Insertion sort average case | O(n^2) |
| Explain how insertion sort works. Is it D&C or comparison based? | Insertion sort keeps a pointer of the array that is sorted. Takes a new item and inserts it into the already sorted section of the array. Comparison |
| Is insertion sort in place? stable | Yes in place Yes stable |
| Quick sort worst case | O(n^2) |
| Quick sort best case | O(n log n) |
| Quick sort average case | O(n log n) |
| How does quick sort work? Is it D&C or comparison based. (easy split vs. easy merge) | Quick sort breaks the array into two sections (elements less than the pivot and elements greater than the pivot) and it basically keeps doing this until it has sorted sections of length 1, then it merges them all back together hard split, easy merge |
| Is quick sort in place? stable? | In place Not stable |
| Merge sort worst case | O(n log n) |
| Merge sort best case | O(n log n) |
| Merge sort average case | O(n log n) |
| How does merge sort work? Is it D&C or comparison based. (easy split vs. easy merge) | Divides the array in half, sorts each half, merges the halves back together at the end. Divide and conquer. Easy split, hard merge |
| Is merge sort in place? stable? | Usually out of place yes stable |
| Heap sort worst case | O(n log n) |
| Heap sort best case | O(n log n) |
| Heap sort average case | O(n log n) |
| How does heap sort work? is it D&C or comparison? | comparison based. Build a max heap from the given array. repeatedly remove the max element and place at the end of the array (then heapify) |
| Is heap sort in place? stable? | In place Not stable |
Created by:
Lily_loves_u