Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
A bubble sort puts the scores , , , , into ascending order. It stops after a pass that makes no swaps.
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. : swap, giving . : swap, giving . : swap, giving . : no swap. So swaps, and the list is .
Step 2. Pass 2. : no swap. : swap, giving . : no swap. One swap.
Step 3. Pass 3. and : no swaps. A pass with no swaps, so the sort stops.
Answer: (a) after swaps; (b) passes.
Check. The list was sorted after pass 2, but the algorithm only knows this when pass 3 makes no swap.
Log in to join the discussion.
Loading…