does anybody know how to make bubble sort work in progressively smaller sizes and determine if a list is sorted on it's first try?

i've got the basic bubble sort algorithm down.
i just can't figure out the rest of it
(my basic bubble sort code below)

def bubbleSort(list1):
    for j in range(len(list1)-1):
        for k in range(len(list1)-1-j):
            if list1[k] > list1[k+1]:
                swap = list1[k]
                list1[k] = list1[k+1]
                list1[k+1] = swap

Maybe something like this:

def bubbleSort(list1):
    swap = False
    for j in range(len(list1)-1):
        for k in range(len(list1)-1-j):
            if list1[k] > list1[k+1]:
                list1[k], list1[k+1] = list1[k+1], list1[k]
                swap = True
        if swap == False:
            break

list1 = [4, 6, 2, 8, 1]
bubbleSort(list1)

print list1  # [1, 2, 4, 6, 8]

hm....thanks for your help zzucker, but i was actually thinking of something that takes the largest value of a list of size N, and switches it to the very end, and goes in a n-1 progression...

something like this....

[8, 10, 6, 7, 4, 5, 9, 1, 4, 7]
[8, 7, 6, 7, 4, 5, 9, 1, 4, 10]
[8, 7, 6, 7, 4, 5, 4, 1, 9, 10]
[1, 7, 6, 7, 4, 5, 4, 8, 9, 10]
etc...

So you don't want a bubble sort then, you would rather have a selection sort that instead you find the largest value and put it in the end.

commented: nice, you must be a mind reader +1

Actually a bubble sort will do exactly what you want:

# 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)

"""
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]
"""

To make things complete, here is a selection sort:

# follow the progression of a selection sort

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

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

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

The insertion sort is also interesting:

# follow the progression of an insertion sort

def insertion_sort(list1):
    for i in range(1, len(list1)):
        save = list1[i]
        j = i
        while j > 0 and list1[j - 1] > save:
            list1[j] = list1[j - 1]
            j -= 1
        list1[j] = save
        print list1

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

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

Under normal circumstances, the insertion and the selection sort are at least twice as fast as the bubble sort.

o wow thanks.
that really cleared things up.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.