I'm trying to do bubble sorting in an efficient manner. I have a count which adds up all the call I've made to the function bubble. I need to find a way to make it efficient where if the bubble function is called and no values in the list are swapped, then i shouldn't call the bubble function again.
I have this code with three functions here
def bubble_sort(values):
count = 0
for i in range(len(values)-1):
count += 1
bubble(values)
return count
def bubble(values):
while True:
swapped = False
for i in range(len(values) - 1):
if values[i] > values[i + 1]:
swap(values, i, i+1)
swapped = True
if not swapped:
break
def swap(values, i, j):
values[i], values[j] = values[j], values[i]
test_1 = [1, 3, 67, 58, 91, 36, 100, 28, 90, 10, 57, 51, 52, 64, 56]
x = bubble_sort(test_1)
print(x, test_1)
test_2 = [2, 3, 4, 1, 5, 6, 7]
y = bubble_sort(test_2)
print(y, test_2)
when I try run the following code the output I get is:
14 [1, 3, 10, 28, 36, 51, 52, 56, 57, 58, 64, 67, 90, 91, 100]
the expected output is:
8 [1, 3, 10, 28, 36, 51, 52, 56, 57, 58, 64, 67, 90, 91, 100]
I thought that editing my bubble code would do the trick, but it doesn't change anything even if I were to use a normal bubble-sort function.
Any help is appreciated. Thank you.
You need to break out the outer loop in bubble_sort that is calling bubble in case there's no swaps. Just remove while from bubble and return a bool indicating if swaps were made. Then you can stop the for loop in bubble_sort if you get False as return value:
def bubble_sort(values):
count = 0
for i in range(len(values)-1):
count += 1
if not bubble(values):
break
return count
def bubble(values):
swapped = False
for i in range(len(values) - 1):
if values[i] > values[i + 1]:
swap(values, i, i+1)
swapped = True
return swapped
With these modification you get the expected output:
(8, [1, 3, 10, 28, 36, 51, 52, 56, 57, 58, 64, 67, 90, 91, 100])
(4, [1, 2, 3, 4, 5, 6, 7])