In class we are doing sorting algorithms and, although I understand them fine when talking about them and writing pseudocode, I am having problems writing actual code for them.
This is my attempt in Python:
mylist = [12, 5, 13, 8, 9, 65]
def bubble(badList):
length = len(badList) - 1
unsorted = True
while unsorted:
for element in range(0,length):
unsorted = False
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
print badList
else:
unsorted = True
print bubble(mylist)
Now, this (as far as I can tell) sorts correctly, but once it finishes it just loops indefinitely.
How can this code be fixed so the function finishes properly and correctly sorts a list of any (reasonable) size?
P.S. I know I should not really have prints in a function and I should have a return, but I just have not done that yet as my code does not really work yet.
This question is related to
python
algorithm
sorting
bubble-sort
The problem with the original algorithm is that if you had a lower number further in the list, it would not bring it to the correct sorted position. The program needs to go back the the beginning each time to ensure that the numbers sort all the way through.
I simplified the code and it will now work for any list of numbers regardless of the list and even if there are repeating numbers. Here's the code
mylist = [9, 8, 5, 4, 12, 1, 7, 5, 2]
print mylist
def bubble(badList):
length = len(badList) - 1
element = 0
while element < length:
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
element = 0
print badList
else:
element = element + 1
print bubble(mylist)
You've got a couple of errors in there. The first is in length, and the second is in your use of unsorted (as stated by McWafflestix). You probably also want to return the list if you're going to print it:
mylist = [12, 5, 13, 8, 9, 65]
def bubble(badList):
length = len(badList) - 2
unsorted = True
while unsorted:
for element in range(0,length):
unsorted = False
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
print badList
unsorted = True
return badList
print bubble(mylist)
eta: You're right, the above is buggy as hell. My bad for not testing through some more examples.
def bubble2(badList):
swapped = True
length = len(badList) - 2
while swapped:
swapped = False
for i in range(0, length):
if badList[i] > badList[i + 1]:
# swap
hold = badList[i + 1]
badList[i + 1] = badList[i]
badList[i] = hold
swapped = True
return badList
The goal of bubble sort is to move the heavier items at the bottom in each round, while moving the lighter items up. In the inner loop, where you compare the elements, you don't have to iterate the whole list in each turn. The heaviest is already placed last. The swapped variable is an extra check so we can mark that the list is now sorted and avoid continuing with unnecessary calculations.
def bubble(badList):
length = len(badList)
for i in range(0,length):
swapped = False
for element in range(0, length-i-1):
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
swapped = True
if not swapped: break
return badList
Your version 1, corrected:
def bubble(badList):
length = len(badList) - 1
unsorted = True
while unsorted:
unsorted = False
for element in range(0,length):
#unsorted = False
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
unsorted = True
#print badList
#else:
#unsorted = True
return badList
This is what happens when you use variable name of negative meaning, you need to invert their values. The following would be easier to understand:
sorted = False
while not sorted:
...
On the other hand, the logic of the algorithm is a little bit off. You need to check whether two elements swapped during the for loop. Here's how I would write it:
def bubble(values):
length = len(values) - 1
sorted = False
while not sorted:
sorted = True
for element in range(0,length):
if values[element] > values[element + 1]:
hold = values[element + 1]
values[element + 1] = values[element]
values[element] = hold
sorted = False
return values
def bubble_sort(l):
for passes_left in range(len(l)-1, 0, -1):
for index in range(passes_left):
if l[index] < l[index + 1]:
l[index], l[index + 1] = l[index + 1], l[index]
return l
def bubble_sort(l):
for i in range(len(l) -1):
for j in range(len(l)-i-1):
if l[j] > l[j+1]:
l[j],l[j+1] = l[j+1], l[j]
return l
A simpler example:
a = len(alist)-1
while a > 0:
for b in range(0,a):
#compare with the adjacent element
if alist[b]>=alist[b+1]:
#swap both elements
alist[b], alist[b+1] = alist[b+1], alist[b]
a-=1
This simply takes the elements from 0 to a(basically, all the unsorted elements in that round) and compares it with its adjacent element, and making a swap if it is greater than its adjacent element. At the end the round, the last element is sorted, and the process runs again without it, until all elements have been sorted.
There is no need for a condition whether sort
is true or not.
Note that this algorithm takes into consideration the position of the numbers only when swapping, so repeated numbers will not affect it.
PS. I know it has been very long since this question was posted, but I just wanted to share this idea.
idk if this might help you after 9 years... its a simple bubble sort program
l=[1,6,3,7,5,9,8,2,4,10]
for i in range(1,len(l)):
for j in range (i+1,len(l)):
if l[i]>l[j]:
l[i],l[j]=l[j],l[i]
def bubble_sort(a):
t = 0
sorted = False # sorted = False because we have not began to sort
while not sorted:
sorted = True # Assume sorted = True first, it will switch only there is any change
for key in range(1,len(a)):
if a[key-1] > a[key]:
sorted = False
t = a[key-1]; a[key-1] = a[key]; a[key] = t;
print a
def bubble_sort(l):
exchanged = True
iteration = 0
n = len(l)
while(exchanged):
iteration += 1
exchanged = False
# Move the largest element to the end of the list
for i in range(n-1):
if l[i] > l[i+1]:
exchanged = True
l[i], l[i+1] = l[i+1], l[i]
n -= 1 # Largest element already towards the end
print 'Iterations: %s' %(iteration)
return l
Here is a different variation of bubble sort without for
loop. Basically you are considering the lastIndex
of the array
and slowly decrementing
it until it first index of the array.
The algorithm
will continue to move through the array like this until an entire pass is made without any swaps
occurring.
The bubble is sort is basically Quadratic Time: O(n²)
when it comes to performance.
class BubbleSort:
def __init__(self, arr):
self.arr = arr;
def bubbleSort(self):
count = 0;
lastIndex = len(self.arr) - 1;
while(count < lastIndex):
if(self.arr[count] > self.arr[count + 1]):
self.swap(count)
count = count + 1;
if(count == lastIndex):
count = 0;
lastIndex = lastIndex - 1;
def swap(self, count):
temp = self.arr[count];
self.arr[count] = self.arr[count + 1];
self.arr[count + 1] = temp;
arr = [9, 1, 5, 3, 8, 2]
p1 = BubbleSort(arr)
print(p1.bubbleSort())
def bubble_sorted(arr:list):
while True:
for i in range(0,len(arr)-1):
count = 0
if arr[i] > arr[i+1]:
count += 1
arr[i], arr[i+1] = arr[i+1], arr[i]
if count == 0:
break
return arr
arr = [30,20,80,40,50,10,60,70,90]
print(bubble_sorted(arr))
#[20, 30, 40, 50, 10, 60, 70, 80, 90]
Your use of the Unsorted variable is wrong; you want to have a variable that tells you if you have swapped two elements; if you have done that, you can exit your loop, otherwise, you need to loop again. To fix what you've got here, just put the "unsorted = false" in the body of your if case; remove your else case; and put "unsorted = true before your for
loop.
def merge_bubble(arr):
k = len(arr)
while k>2:
for i in range(0,k-1):
for j in range(0,k-1):
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
return arr
break
else:
if arr[0] > arr[1]:
arr[0],arr[1] = arr[1],arr[0]
return arr
If anyone is interested in a shorter implementation using a list comprehension:
def bubble_sort(lst: list) -> None:
[swap_items(lst, i, i+1) for left in range(len(lst)-1, 0, -1) for i in range(left) if lst[i] > lst[i+1]]
def swap_items(lst: list, pos1: int, pos2: int) -> None:
lst[pos1], lst[pos2] = lst[pos2], lst[pos1]
I am a fresh fresh beginner, started to read about Python yesterday. Inspired by your example I created something maybe more in the 80-ties style, but nevertheless it kinda works
lista1 = [12, 5, 13, 8, 9, 65]
i=0
while i < len(lista1)-1:
if lista1[i] > lista1[i+1]:
x = lista1[i]
lista1[i] = lista1[i+1]
lista1[i+1] = x
i=0
continue
else:
i+=1
print(lista1)
def bubblesort(array):
for i in range(len(array)-1):
for j in range(len(array)-1-i):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return(array)
print(bubblesort([3,1,6,2,5,4]))
I consider adding my solution because ever solution here is having
then is should be
So, here is my solution:
def countInversions(arr):
count = 0
n = len(arr)
for i in range(n):
_count = count
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
count += 1
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if _count == count:
break
return count
def bubble_sort(li):
l = len(li)
tmp = None
sorted_l = sorted(li)
while (li != sorted_l):
for ele in range(0,l-1):
if li[ele] > li[ele+1]:
tmp = li[ele+1]
li[ele+1] = li [ele]
li[ele] = tmp
return li
arr = [5,4,3,1,6,8,10,9] # array not sorted
for i in range(len(arr)):
for j in range(i, len(arr)):
if(arr[i] > arr[j]):
arr[i], arr[j] = arr[j], arr[i]
print (arr)
def bubbleSort ( arr ):
swapped = True
length = len ( arr )
j = 0
while swapped:
swapped = False
j += 1
for i in range ( length - j ):
if arr [ i ] > arr [ i + 1 ]:
# swap
tmp = arr [ i ]
arr [ i ] = arr [ i + 1]
arr [ i + 1 ] = tmp
swapped = True
if __name__ == '__main__':
# test list
a = [ 67, 45, 39, -1, -5, -44 ];
print ( a )
bubbleSort ( a )
print ( a )
def bubbleSort(a):
def swap(x, y):
temp = a[x]
a[x] = a[y]
a[y] = temp
#outer loop
for j in range(len(a)):
#slicing to the center, inner loop, python style
for i in range(j, len(a) - j):
#find the min index and swap
if a[i] < a[j]:
swap(j, i)
#find the max index and swap
if a[i] > a[len(a) - j - 1]:
swap(len(a) - j - 1, i)
return a
Answers provided by the-fury and Martin Cote fixed the problem of the infinite loop, but my code would still not work correctly (for a larger list, it would not sort correctly.). I ended up ditching the unsorted
variable and used a counter instead.
def bubble(badList):
length = len(badList) - 1
n = 0
while n < len(badList):
for element in range(0,length):
if badList[element] > badList[element + 1]:
hold = badList[element + 1]
badList[element + 1] = badList[element]
badList[element] = hold
n = 0
else:
n += 1
return badList
if __name__ == '__main__':
mylist = [90, 10, 2, 76, 17, 66, 57, 23, 57, 99]
print bubble(mylist)
If anyone could provide any pointers on how to improve my code in the comments, it would be much appreciated.
def bubbleSort(alist):
if len(alist) <= 1:
return alist
for i in range(0,len(alist)):
print "i is :%d",i
for j in range(0,i):
print "j is:%d",j
print "alist[i] is :%d, alist[j] is :%d"%(alist[i],alist[j])
if alist[i] > alist[j]:
alist[i],alist[j] = alist[j],alist[i]
return alist
alist = [54,26,93,17,77,31,44,55,20,-23,-34,16,11,11,11]
print bubbleSort(alist)
Try this
a = int(input("Enter Limit"))
val = []
for z in range(0,a):
b = int(input("Enter Number in List"))
val.append(b)
for y in range(0,len(val)):
for x in range(0,len(val)-1):
if val[x]>val[x+1]:
t = val[x]
val[x] = val[x+1]
val[x+1] = t
print(val)
#A very simple function, can be optimized (obviously) by decreasing the problem space of the 2nd array. But same O(n^2) complexity.
def bubble(arr):
l = len(arr)
for a in range(l):
for b in range(l-1):
if (arr[a] < arr[b]):
arr[a], arr[b] = arr[b], arr[a]
return arr
Source: Stackoverflow.com