1
$\begingroup$

In Robert Lafore's book "Object Oriented Programming in C++, Fourth Edition", on page 450, he has a section on the bubble sort. The way he describes it is as follows:

Here's how it works, assuming we want to arrange the numbers in the array in ascending order. First the first element of the array (arr[0]) is compared in turn with each of the other elements (starting with the second). If it's greater than any of them, the two are swapped. When this is done we know that at least the first element is in order; it's now the smallest element. Next the second element is compared in turn with all the other elements, starting with the third, and again swapped if it's bigger. When we're done we know that the second element has the second-smallest value. This process is continued for all the elements until the next-to-the-last, at which time the array is assumed to be ordered.

This sounds to me like it is very different from what is commonly called the bubble sort (you iterate through the array comparing 0 and 1, 1 and 2, 2 and 3 and so on, repeatedly, until they are all in order). I wrote some code to compare the speed of these two algorithms and found that Lafore's bubble sort is consistently twice as fast as the standard one. So what's going on here? Does Lafore's bubble sort ordinarily go by a different name?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This is closer to a bad SelectionSort. I say bad because it's doing a lot of useless swaps. In standard SelectionSort, you only swap once per pass, when you know where the smallest element is found. $\endgroup$
    – user16034
    Aug 2, 2022 at 7:22

1 Answer 1

Reset to default
1
$\begingroup$

Ok, I think I found what Lafore is calling the "Bubble sort". It is commonly known as selection sort: https://www.geeksforgeeks.org/selection-sort/

Edit: As greybeard and Yves Daoust have pointed out, Lafore's algorithm actually performs a lot more swaps than selection sort. Someone has since pointed out to me that in fact Lafore's bubble sort performs a roughly similar number of comparisons and swaps to the standard bubble sort. He also showed me that the difference in speed that I observed is due to the way I wrote the code and can be eliminated by implementing the standard bubble sort differently. So in conclusion, although it may not be obvious at first, it seems that Lafore's bubble sort is actually just another version of the standard bubble sort.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Sort of, looking at the final values at each index. But for each target index, selection sort just swaps once, where the procedure sketched in the question will swap each and every remaining value for a sequence in reverse order. $\endgroup$
    – greybeard
    Aug 2, 2022 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.