Sorting and searching algorithms

Sorting and searching algorithms Flashcards

Spec 1.2 · Edexcel International A Level Maths: 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 NN odd, and for NN even?
N+12\frac{N+1}{2} for odd NN; N+22\frac{N+2}{2} for even NN.
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 nn items?
n−1n-1 (fewer on later passes).
How do you show a target is not in the list in a binary search?
Continue until no items remain.

Flashcards