Why does my Descending Bubble Sort not work for an input in ascending order?

user_17532855 0
Viewed 65

This code works for most inputs except for when the input is in ascending order.

e.g. input is [1,2,3,4,5], output is [5,1,4,2,3], expected is [5,4,3,2,1]

DescBubbleSort(A) 
    for i from n downto 1 do
        for j from n downto i + 1 do
            if A[j] > A[j − 1] then
                A[j] swap A[j-1]
    return A
bubble-sort sorting
1 Answers

You do the operations in the wrong order.
According to this Wiki-Entry, the correct code is:

 for (n=A.size; n>1; --n){
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
      }
    }
  }

EDIT:

Sorry that I was not detailed enough (although SO does not like questions like "find my bug").
Anyway: I assume your code is in Pascal. I hope I corrected your code correctly as follows:

for i from n downto 1 do
  for j from n downto n-i+1 do
    if A[j] > A[j-1] then
      A[j] swap A[j-1]
return A

The same in Swift (that I tested):

var a = [1,2,3,4,5]
print(a) // Prints [1, 2, 3, 4, 5]
for i in stride(from: 4, through: 1, by: -1) {
  for j in stride(from: 4, through: 4-i+1, by: -1) {
    if a[j] > a[j-1] {
      a.swapAt(j, j-1)
    }
  }
}
print(a) // Prints [5, 4, 3, 2, 1]

As you see, your bug is in the 2nd line at downto i + 1.

user_19877260
Related