When I wrote my CombSort algorithm yesterday, I started running into problems with arrays of small sizes. For example, the array {9, 2, 7, 4} would sort to {4, 2, 7, 9}. And then I realized, every time the last floor(count/1.3) elements failed comparison (meaning that they were already sorted), then the algorithm exited, leaving the middle of the array unsorted. With arrays of thousands or millions of integers, this was not a problem since the probability of this was miniscule. But, as the array size got smaller, this possibility rapidly increased, especially if the range of numbers was also decreased.
However, I just found my logic error, which occurred when testing to see if the algorithm should continue. I was reading that the algorithm should always run with a gap size of 1 (to ensure that it is sorted), even if the last pass didn’t sort anything. The condition for continuing should be if the gap is greater than one or the previous pass did not sort anything. Therefore, my original logic for testing this was flawed since it was the logical inverse.
The code should be:
while(gap > 1 || swaps != 0)
I have updated the original post to reflect this.
0 Responses to “My CombSort logic error”