Sorting and searching algorithms Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
13 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 13 cards
- Describe one pass of a bubble sort.
- Compare adjacent items from the left and swap them if they are in the wrong order, to the end of the list.
- After a bubble-sort pass, where is the largest item?
- At the end of the list.
- When does a bubble sort stop?
- After a pass in which no swaps are made.
- What is the middle item position for odd, and for even?
- for odd ; for even .
- Which item is the middle item of a list of 10?
- The 6th item.
- What is the pivot in quick sort here?
- The middle item of the list or sub-list being sorted.
- Describe one pass of quick sort.
- Write items smaller than the pivot to the left and larger to the right, in their original order; the pivot is then in position.
- When does quick sort stop?
- When every sub-list has at most one item.
- What must be true of a list before a binary search?
- It must be in order.
- Describe binary search.
- Compare with the middle item and discard that item and the half that cannot contain the target; repeat until found or nothing remains.
- If the target is smaller than the middle item in a binary search, what is discarded?
- The middle item and all items after it.
- How many comparisons does a bubble-sort pass make on items?
- (fewer on later passes).
- How do you show a target is not in the list in a binary search?
- Continue until no items remain.