CODEWITHSUNDEEP
pythonpython-3.xalgorithmsorting
matt_3773
matt_3773

Reputation: 73

Issue with bubblesort not sorting last number

New to coding and algorithims. Trying out the easiest one, the bubblesort. But it seems like the last number isnt being sorted? Can't really figure out why.

Original list looks like this - list = [4, 5, 3, 10, 17, 6, 2, 22, 76, 99, 18, 7] But my output looks like this - [99, 2, 3, 4, 5, 6, 7, 10, 17, 18, 22, 76]

For some reason 99 isn't being swapped to the back and I cant pinpoint why.

list = [4, 5, 3, 10, 17, 6, 2, 22, 76, 99, 18, 7]

def bblSort(list):
    for i in range(len(list)):
        print(list[i])
        for j in range(len(list) - 1):
            if list[i] <list[j+1]:
                list[i], list[j+1] = list[j+1], list[i]

    print(list)

Upvotes: 1

Views: 625

Answers (4)

pakpe
pakpe

Reputation: 5479

Bubble sort can be implemented with two for loops or a while loop and a for loop. Here is an implementation which uses a while and a for loop and is easier to understand.

This function traverses the list with the inner for loop, compares each object to the object after it, and swaps the two if necessary. The outer while loop ensures that it repeats the for-loop over and over again through the whole list until no further swapping is required.

def bubble_sort(unsorted_list):
    my_list = list(unsorted_list) # create a copy to avoid mutating the original list
    unsorted = True
    while unsorted:
        unsorted = False
        for i in range (len(my_list)-1):
            if my_list[i] > my_list[i+1]:
                unsorted = True
                my_list[i] , my_list[i+1] = my_list[i+1], my_list[i]
    return my_list

unsorted_list = [5,2,4,90,140,23,554,32,98,12,15,0,43,-34,10]
print(bubble_sort(unsorted_list))

Prints: [-34, 0, 2, 4, 5, 10, 12, 15, 23, 32, 43, 90, 98, 140, 554]

Upvotes: 1

trincot
trincot

Reputation: 350290

Your code has several issues, if your aim was to implement bubble sort:

  • Bubble sort only compares and swaps adjacent elements, so a comparison between lst[j] and lst[j+1].
  • The comparison should then be adapted accordingly, to lst[j] > lst[j+1], which indicates those two values appear in the wrong order.
  • Although not absolutely needed to make it work, a good bubble sort algorithm will not verify pairs that are sure to be already in the right order. This means that the inner loop really needs one iteration less each time i increments, since the end of the list will have the (growing) part that is already sorted.

So:

def bblSort(lst):
    for i in range(len(lst)):
        for j in range(len(lst) - 1 - i):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]

Upvotes: 0

rossum
rossum

Reputation: 15685

For a bubblesort you need to do multiple passes through the list to ensure that it is sorted. Each pass is guaranteed to move the largest number to the end of the part of the list being sorted. That means you don't need to sort that position again, so you only need to sort up to that position on the next pass.

I don't know much Python, so this is pseudocode. It does an in-place sort of the list into ascending order.

bubblesort(list myList)
  for (hi <- myList.length - 1 downto 0) do
    for (lo <- 1 to hi) do
      if (myList[lo - 1] > myList[lo]) then
        swap(myList[lo - 1], myList[lo]) 
      endif
    endfor
  endfor
end bubblesort()

Each pass sorts the part of the list between the start and hi with hi being reduced by one for each pass.

For extra credit, think of a way to finish early if a pass does not do any swaps. In that case the list is already sorted with everything in order.

Upvotes: 0

user122644
user122644

Reputation: 109

You only need one loop, since bubble sort compare adjacent values. Try doing a single loop with i, and then just comparing list[i] and list[i+1] (watch out for end of the list)

Btw, it's good practice not to call your variables with type names, here choose another name for the variable 'list'.

Upvotes: 0

Related Questions