End of scan 1:
6 3 1 4 7
Scanning left to right again results in:
3 1 4 6 7
Scanning left to right again results in a correct ordering:
1 3 4 6 7
Write pseudo code for the bubble-sort.
bubbleSort( list )
length <-- length of list
// look through the whole list to find
// mis-ordered pairs, and continue until
// we get through the whole list without
// swapping any pairs
do {
// start at the left end of the list: index = 1
swapped_pair <-- false
index <-- 1
while index <= length - 1 {
// if this pair is mis-ordered, swap them
if list[index] > list[index + 1] {
swap( list[index], list[index + 1] )
swapped_pair = true
// increment the index to look at the
// next pair up
index <-- index + 1
}
}
// quit only when we have gone through the whole
// list and found it unnecessary to swap any pair
} while( swapped = true )
end
2.8 What is the bubble-sort ???
??( n2 )
2.9 How will the bubble sort compare for speed with the merge sort when the task is to sort 1,000,000 social
security numbers which initially are in random order?
ANSWERS TO REVIEW QUESTIONS 183
bubble-sort:merge-sort::(1,000,000)2:1,000,000*lg 1,000,000
bubble-sort : merge-sort :: 1,000,000 : lg 1,000,000
bubble-sort : merge-sort :: 1,000,000 : 20
bubble-sort : merge-sort :: 50,000 : 1
The merge-sort will run 50,000 times faster than the bubble-sort!
If the merge-sort takes 10 seconds, the bubble-sort will take
almost 6 days!
184 ANSWERS TO REVIEW QUESTIONS
COMPUTER ORGANIZATION
3.
Pages:
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501