bubble sort question

[fishsticks1907]

def bubble_sort(a):
    for i in range(0, len(a)):
        for j in range(0, len(a) - 1):
            if(a[i] < a[j]):
                a[i], a[j] = a[j], a[i]  #can someone explain this part of the code for me

    #i tried doing (im more of a c++ programmer):

    temp = 0
    temp = a[i]
    a[i] = a[j]
    a[j] = temp

    #but that didn't work well

[Sahil89]

I am also not pyhton guy but I think at line 5 the values of a[i] and a[j] are being swap if a[i] is less then a[j] and process goes on until array is sorted.
Its was really weird experience for me to look at python code for first time. I hope my explaination helps you :) Else other python experts are there for your answers. Good Luck :)

[woooee]

You have the range endings reversed and you want to start at +1 on the inner loop.

for x in range(0, len(a)-1):
    for j in range(x+1, len(a)):

Also you swap every time there is a difference instead of once per loop.

import random

a=[random.randint(1, 100) for ctr in range(20)]
print a
#
for x in range(0, len(a)-1):
    largest = x
    for y in range(x+1, len(a)):
        if a[largest] < a[y]:
            largest = y
    if largest > x:
        temp = a[largest]
        a[largest] = a[x]
        a[x] = temp
print a

[TrustyTony]

@wooeee: you are doing selection sort not bubble sort. On the other hand bubble sort is so inefficient, that you should use insertion or selection sort.
______

For bubble sort it is customary to set flag for if swaps were made and stop sort when no swaps were done in inside loop.

[woooee]

I am answering the question as asked. If that means that a I am not your robot then so much the better.

[TrustyTony]

sorry wooeee now I don't get ypur meaning. I ment that buble sort was the question and the exchange part of it in partocular.

You gave code for a better sort as nobody should use in real life the bubble sort. Excuse my English.

[Lardmeister]

in Python you can swap variables via tuple packing

a = 1
b = 2
# swap a with b
a, b = b, a         # now b = 1 and a = 2

# test
print(a)
print(b)

# for clarity you may optionally surround the tuples with ()
# (a, b) = (b, a)

[Lardmeister]

Typical example of a bubble sort that also test prints the progress:

# follow the progression of a bubble sort

def bubble_sort(list1):
    swap_test = False
    for i in range(0, len(list1) - 1):
        for j in range(0, len(list1) - i - 1):
            if list1[j] > list1[j + 1]:
                # do a tuple swap
                list1[j], list1[j + 1] = list1[j + 1], list1[j]
            swap_test = True
        if swap_test == False:
            break
        print(list1)

list1 = [8, 10, 6, 7, 4, 5, 9, 1, 4, 7]
bubble_sort(list1)

"""my output --->
[8, 6, 7, 4, 5, 9, 1, 4, 7, 10]
[6, 7, 4, 5, 8, 1, 4, 7, 9, 10]
[6, 4, 5, 7, 1, 4, 7, 8, 9, 10]
[4, 5, 6, 1, 4, 7, 7, 8, 9, 10]
[4, 5, 1, 4, 6, 7, 7, 8, 9, 10]
[4, 1, 4, 5, 6, 7, 7, 8, 9, 10]
[1, 4, 4, 5, 6, 7, 7, 8, 9, 10]
[1, 4, 4, 5, 6, 7, 7, 8, 9, 10]
[1, 4, 4, 5, 6, 7, 7, 8, 9, 10]
"""

[TrustyTony]

Without testing, the flag setting line at line 10 should be indented inside if.

[Lardmeister]

You are right pyTony.
The swap_test flag is there to detect an already sorted list. My bad.

[Lardmeister]

For the sake of simplicity this might be better:

# follow the progression of a typical bubble sort

def bubble_sort(list1):
    for i in range(0, len(list1) - 1):
        for j in range(0, len(list1) - i - 1):
            if list1[j] > list1[j + 1]:
                # do a tuple swap
                list1[j], list1[j + 1] = list1[j + 1], list1[j]
        print(list1)

list1 = [8, 10, 6, 7, 4, 5, 9, 1, 4, 7]
bubble_sort(list1)

"""my output --->
[8, 6, 7, 4, 5, 9, 1, 4, 7, 10]
[6, 7, 4, 5, 8, 1, 4, 7, 9, 10]
[6, 4, 5, 7, 1, 4, 7, 8, 9, 10]
[4, 5, 6, 1, 4, 7, 7, 8, 9, 10]
[4, 5, 1, 4, 6, 7, 7, 8, 9, 10]
[4, 1, 4, 5, 6, 7, 7, 8, 9, 10]
[1, 4, 4, 5, 6, 7, 7, 8, 9, 10]
[1, 4, 4, 5, 6, 7, 7, 8, 9, 10]
[1, 4, 4, 5, 6, 7, 7, 8, 9, 10]
"""

[TrustyTony]

Maybe mine is more Pythonic (non-destructive sorted style)

import random
import time

def bubble(seq):
    seq = seq[:]
    for thisfar in reversed(range(len(seq))):
        done = True
        for pos in range(thisfar):
            if seq[pos] > seq[pos+1]:
                seq[pos], seq[pos+1] = seq[pos+1], seq[pos]
                done = False
        if done:
            #print thisfar
            return seq

def select(seq):
    seq = seq[:]
    for thisfar in range(len(seq)):
        for pos in range(thisfar, len(seq)):
            if seq[pos] < seq[thisfar]:
                seq[pos], seq[thisfar] = seq[thisfar], seq[pos]
    return seq

mixed = list(random.random() for c in range(4000))
t0 = time.clock()
s=bubble(mixed)
#print s
t1 = time.clock()
s2=select(mixed)
#print s
t2 = time.clock()
assert sorted(mixed)==s==s2 and s != mixed
t3 = time.clock()
print('Bubble %.3f vs selection %.3f, sorted %.3f' % (t1-t0, t2-t1, t3-t2))