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``````

## All 5 Replies

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, learning, and sharing knowledge.