David W. answered • 03/13/23
Tutor
4.7
(90)
Experienced Prof
Jam J.
asked • 03/13/231- Sort this list of numbers 8, 22, 7, 31 , 9 in ascending order using bubble sort- you need to show your work
End of Pass 1:
End of pass 2:
More
2 Answers By Expert Tutors
Juliet C. answered • 03/13/23
Tutor
5.0
(788)
PhD in Computer Science with 8+ Years of Teaching Experience
The bubble sort algorithm works by comparing adjacent elements, at index p and index p+1 where p starts as the index of the first element, and swapping them if they are not in the correct order and then increasing p by 1 until p is the index of the last element. That is one pass. Note that the same element could be swapped repeatedly during a pass as it "bubbles" through other elements. For example:
9 2 4 7 8
2 9 4 7 8
2 4 9 7 8
2 4 7 9 8
2 4 7 8 9
If any swap occurred during a pass, the algorithm will do another full pass. If no swap occurs during a full pass, the elements are in order and the algorithm stops.
The Wikipedia page has a nice step-by-step example: https://en.wikipedia.org/wiki/Bubble_sort#Step-by-step_example
David W.
Correction: "until p is the index of the last element" should be "until p+1 is the index of the last element NOT YET SORTED."
Report
03/13/23
Juliet C.
tutor
[ Updated to add: I see that you are referring to the optimized version of bubble sort, where the ending index for a pass is decremented by 1 after each pass. ] .......... original comment .........
When p is the index of the last element, that means the last pair of elements in the list have been compared and swapped if necessary.
Note that doing one pass through the list does not mean that every element is in its final sorted position, therefore I would not characterize the elements as sorted or not yet sorted.
Here is an example of a pass, with square brackets indicating elements being compared since I cannot make them bold in a comment:
-- [4 7] 8 2 9 --
-- 4 [7 8] 2 9 --
-- 4 7 [8 2] 9 --
-- 4 7 2 [8 9] --
Report
03/17/23
Still looking for help? Get the right answer, fast.
Ask a question for free
Get a free answer to a quick problem.
Most questions answered within 4 hours.
OR
Find an Online Tutor Now
Choose an expert and meet online. No packages or subscriptions, pay only for the time you need.
Juliet C.
03/20/23