Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A bubble sort is changed so that it sorts in descending order: the comparison becomes IF Scores[Index] < Scores[Index + 1]. It sorts , , , , , and stops after a pass with no swaps. Each pass compares one pair fewer than the pass before.
Linear search: compare each item in turn from the first; stop when it is found or the list ends. Bubble sort: compare each pair of neighbours and swap them if they are in the wrong order; repeat passes until a pass makes no swaps. A pass over items makes comparisons at most.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Pass 1 (4 comparisons). : swap, giving . : swap, giving . : swap, giving . : no. The list is .
Step 2. Pass 2 (3 comparisons). : no. : swap, giving . : no.
Step 3. Pass 3 (2 comparisons). : swap, giving . : no. A swap happened, so the sort goes on.
Step 4. Pass 4 (1 comparison). : no. No swaps, so the sort stops.
Answer: (a) ; (b) comparisons; (c) passes.
Check. The list was ready after pass 3, but the sort only knows this after a pass with no swaps. Pass 1 moved the smallest value to the end, as a descending sort should.
Log in to join the discussion.
Loading…