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.
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.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.