0

I am implementing bubble sort in Python and used range for indexing the array:

"""
program to implement bubble sort
"""
a = [9,1,5,3,7,4,2,6,8]
for i in range(len(a)):
    for j in range(i+1, len(a)):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]
print(a)

I got the array sorted in increasing order but when I used enumerate instead of range,

"""
program to implement bubble sort
"""
a = [9,1,5,3,7,4,2,6,8]
for i, x in enumerate(a):
    for j, y in enumerate(a):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]
print(a)

I got the array sorted in decreasing order

Why it happened,is there something I am missing?

Kelly Bundy
  • 23,480
  • 7
  • 29
  • 65
Sid
  • 301
  • 3
  • 4
  • 3
    With enumerate, you aren't comparing the correct elements anymore. You could be comparing with elements before the current element in the array. – Unmitigated Jan 31 '23 at 04:35
  • 1
    Your first example always has `first_index` less than `second_index`; the comparison `array_elements[first_index] > array_elements[second_index]` therefore actually tells you something useful about the ordering of the elements. However, the second example loops over every possible combination of the two indexes, without caring about which one is earlier in the list than the other: the comparison is therefore useless. It's basically just random chance that this results in a reversed list. – jasonharper Jan 31 '23 at 04:37
  • Marking this as duplicate because the first code is just an ordinary working sort and the surprise (reverse) sorting of the second code is the real issue here and that's exactly what that older question is about. – Kelly Bundy Jan 31 '23 at 07:15
  • @jasonharper Not random chance. But surprising indeed. It's explained in the duplicate. – Kelly Bundy Jan 31 '23 at 07:17

2 Answers2

2

What you experienced has noting to do with enumerate as such. The core of your confusion is another way of looping over the indices.

Following code shows that the effect you have experienced with enumerate is caused by another range of the inner loop and happens also without enumerate.

The last part of the code shows that code using enumerate but equivalent to the for loops with range delivers the same result as the loops using range:

a = [9,1,5,3,7,4,2,6,8]
for i in range(len(a)):
    for j in range(i+1, len(a)):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]
print(a)

a = [9,1,5,3,7,4,2,6,8]
for i in range(len(a)):
    for j in range(len(a)):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]
print(a)

a = [9,1,5,3,7,4,2,6,8]
for i, x in enumerate(a):
    for j, y in enumerate(a[i+1:], start=i+1):
        if a[i] > a[j]:
            a[i], a[j] = a[j], a[i]
print(a)

prints

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

By the way:

That looping over the full range of indices in both outer and inner loop results in sorting and with same swap condition in a reversed sorting is an interesting effect discussed in answers to the question What is this odd sorting algorithm? .

Why it works and how it does what it does is not easy to understand especially because of the inefficient and unnecessary looping over all of the indices in the inner loop, where going only over indices less than the current index of the outer loop will already sufficiently do the job:

a = [9,1,5,3,7,4,2,6,8]
for i in range(1, len(a)):
    for j in range(0, i):
        if a[i] < a[j]:
            a[i], a[j] = a[j], a[i]
print(a)

There is an interesting worth to study paper about the algorithm looping over full range of indices in both the outer and inner loop here: https://arxiv.org/pdf/2110.01111.pdf ( "Is this the simplest and most surprising sorting algorithm ever?" by Stanley P. Y. Fung ). The paper explains how and why the algorithm works at all and shows how it can be improved to not loop in the inner loop over all of the array indices ( see the code provided above ).


For the sake of completeness below code demonstrating how the sorting which loops over full range of indices in an outer and inner loop in its first iterations destroys the already existing sorting of the array, but only temporary before arriving at the end at the right result anyway. It is the introduction of a worse sorting state what makes it so hard to grasp why and how the algorithm works.

As an example of an easy to understand sorting algorithm below a simple implementation of a bubble sorting which excels at efficiently detecting already sorted data.

See in the output the number of done if-comparisons and actual data swaps by the two different algorithms to clearly see the advantage of bubble sort for already sorted data. Bubble sorts needs ten times less if-comparisons and doesn't swap any data at all.

a = [1,2,3,4,5,6,7,8,9]
actualswaps = 0
iftests     = 0
for i in range(len(a)):
    print(a, i)
    for j in range(len(a)):
        iftests += 1
        if a[i] < a[j]:
            a[i], a[j] = a[j], a[i]
            actualswaps += 1
            swap = [j,i]
            print('                             ', a, swap )
print(a, end=' ')
print('     ifs:', iftests, '--- ^ swaps --- > ', actualswaps)
print(' ================================= ')

a = [1,2,3,4,5,6,7,8,9]
actualswaps = 0
iftests     = 0
noswaps     = False
print('                             ', a )
while not noswaps: 
    noswaps = True
    for i in range(1, len(a)):
        iftests += 1
        if a[i] < a[i-1]:
            noswaps = False
            a[i], a[i-1] = a[i-1], a[i]
            actualswaps += 1
            swap = [i-1,i]
            print('                             ', a, swap )
print(a, end=' ')
print('     ifs:', iftests, '--- ^ swaps --- > ', actualswaps)
print(' ================================= ')

which prints

[1, 2, 3, 4, 5, 6, 7, 8, 9] 0
                              [2, 1, 3, 4, 5, 6, 7, 8, 9] [1, 0]
                              [3, 1, 2, 4, 5, 6, 7, 8, 9] [2, 0]
                              [4, 1, 2, 3, 5, 6, 7, 8, 9] [3, 0]
                              [5, 1, 2, 3, 4, 6, 7, 8, 9] [4, 0]
                              [6, 1, 2, 3, 4, 5, 7, 8, 9] [5, 0]
                              [7, 1, 2, 3, 4, 5, 6, 8, 9] [6, 0]
                              [8, 1, 2, 3, 4, 5, 6, 7, 9] [7, 0]
                              [9, 1, 2, 3, 4, 5, 6, 7, 8] [8, 0]
[9, 1, 2, 3, 4, 5, 6, 7, 8] 1
                              [1, 9, 2, 3, 4, 5, 6, 7, 8] [0, 1]
[1, 9, 2, 3, 4, 5, 6, 7, 8] 2
                              [1, 2, 9, 3, 4, 5, 6, 7, 8] [1, 2]
[1, 2, 9, 3, 4, 5, 6, 7, 8] 3
                              [1, 2, 3, 9, 4, 5, 6, 7, 8] [2, 3]
[1, 2, 3, 9, 4, 5, 6, 7, 8] 4
                              [1, 2, 3, 4, 9, 5, 6, 7, 8] [3, 4]
[1, 2, 3, 4, 9, 5, 6, 7, 8] 5
                              [1, 2, 3, 4, 5, 9, 6, 7, 8] [4, 5]
[1, 2, 3, 4, 5, 9, 6, 7, 8] 6
                              [1, 2, 3, 4, 5, 6, 9, 7, 8] [5, 6]
[1, 2, 3, 4, 5, 6, 9, 7, 8] 7
                              [1, 2, 3, 4, 5, 6, 7, 9, 8] [6, 7]
[1, 2, 3, 4, 5, 6, 7, 9, 8] 8
                              [1, 2, 3, 4, 5, 6, 7, 8, 9] [7, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]      ifs: 81 --- ^ swaps --- >  16
 ================================= 
                              [1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]      ifs: 8 --- ^ swaps --- >  0
 ================================= 
Claudio
  • 7,474
  • 3
  • 18
  • 48
  • @KellyBundy : the https://stackoverflow.com/questions/69437526/what-is-this-odd-sorting-algorithm question has many interesting answers, but to my current insight none of them explains clearly and easy to understand why the algorithm going over all the indices in both the outer and inner loops sorts. – Claudio Jan 31 '23 at 07:17
  • I was satisfied with the answers back then, but if you find them lacking, write one yourself :-) – Kelly Bundy Jan 31 '23 at 07:20
  • @KellyBundy : the duplicate question itself, not its answers provide the link to the paper with the best explanation how and why the algorithm works ( have included a link to it in my answer ). – Claudio Jan 31 '23 at 08:24
  • Updated answer with `enumerate(a[i+1:], start=i+1):`. – Claudio Jan 31 '23 at 09:42
  • Yes, now the link to exchange sort is also mentioned in the answer. – Claudio Jan 31 '23 at 15:10
  • Now with comparison of the strange algorithm to bubble sort while sorting an already sorted array. – Claudio Jan 31 '23 at 17:46
1

Firstly in your examples, I think these are not bubble sort. Secondly, both of them are working differently like first one compare with only greater indexes while in second one it is comparing with all indexes form start to end.

If we go with them as it is, then you need to change the operator in if condition. instead of >(greater than), you should use <(less than). Because if you want to sort in increasing order you need to find smallest number not greater. And in yours code

if a[i] > a[j]:

it is like of poping greater number in left side. And to get smaller number on left side we need to use <(less than) operator to find smaller number and then pop it to the left side

Kelly Bundy
  • 23,480
  • 7
  • 29
  • 65