MediumPython ProgrammingHigh School (9–10)High School (11–12)UndergraduateGeneralPython Essentials › Searching and SortingConceptualPython-Coded
Bubble sort needs n * (n - 1) // 2 comparisons.
Contributed by StemPy LabTry it on paper first. A hint, the key idea and the worked solution are here when you need them.
Bubble sort needs n * (n - 1) // 2 comparisons. How many for 50 items, and for 100 items? How many times bigger is the second? Then check with a program.
The worked solution
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.
Plan. Put the numbers into the formula.
- For 50 items:
50 * 49 // 2 = 1225. - For 100 items:
100 * 99 // 2 = 4950. - The ratio: 4950 divided by 1225 is about 4.04.
So doubling the list makes the work about four times as big.
Check. The program shows 1225 4950 4.04.... The ratio is a little over 4, and gets closer to 4 as the lists grow.
Answer: 1225 and 4950. About four times as many.
Discussion (0)
Log in to join the discussion.
Loading…