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?
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
=================================