CODEWITHSUNDEEP
sortingbubble-sort
gnnort
gnnort

Reputation: 13

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

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

Upvotes: 1

Views: 109

Answers (1)

Reinhard Männer
Reinhard Männer

Reputation: 15247

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.

Upvotes: 1

Related Questions