Bubble Sort Homework

Question

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

User · Answer

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  gt l j                   l i  l j  l j  l i

User · Answer

A simpler example   a   len alist -1 while a  gt  0      for b in range 0 a            compare with the adjacent element         if alist b  gt  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

User · Answer

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   gt  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   gt  badList element   1                    hold   badList element   1                   badList element   1    badList element                   badList element    hold                  unsorted   True                   print badList               else                    unsorted   True       return badList

User · Answer

def bubblesort array       for i in range len array -1           for j in range len array -1-i               if array j   gt  array j 1                   array j   array j 1    array j 1   array j      return array   print bubblesort  3 1 6 2 5 4

User · Answer

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   gt  li ele 1                   tmp   li ele 1                  li ele 1    li  ele                  li ele    tmp     return li

User · Answer

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

User · Answer

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

User · Answer

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  gt val x 1              t   val x             val x    val x 1             val x 1    t  print val

User · Answer

def merge bubble arr       k   len arr      while k gt 2          for i in range 0 k-1               for j in range 0 k-1                   if arr j   gt  arr j 1                       arr j  arr j 1    arr j 1  arr j           return arr         break     else          if arr 0   gt  arr 1               arr 0  arr 1    arr 1  arr 0          return arr

User · Answer

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  lt  length          if badList element   gt  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

User · Answer

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   lt  a j                   swap j  i               find the max index and swap             if a i   gt  a len a  - j - 1                   swap len a  - j - 1  i      return a

User · Answer

If anyone is interested in a shorter implementation using a list comprehension   def bubble sort lst  list  - gt  None       swap items lst  i  i 1  for left in range len lst -1  0  -1  for i in range left  if lst i   gt  lst i 1     def swap items lst  list  pos1  int  pos2  int  - gt  None      lst pos1   lst pos2    lst pos2   lst pos1

User · Answer

def bubble sorted arr list       while True          for i in range 0 len arr -1               count   0             if arr i   gt  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

User · Answer

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  lt  len badList           for element in range 0 length               if badList element   gt  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

User · Answer

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  lt  lastIndex         if self arr count   gt  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

User · Answer

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   gt  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   gt  badList i   1                      swap                 hold   badList i   1                  badList i   1    badList i                  badList i    hold                  swapped   True      return badList

User · Answer

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

User · Answer

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  lt  len lista1 -1      if lista1 i   gt  lista1 i 1           x   lista1 i          lista1 i    lista1 i 1          lista1 i 1    x         i 0         continue     else          i  1  print lista1

User · Answer

def bubble sort l       for i in range len l  -1           for j in range len l -i-1               if l j   gt  l j 1                   l j  l j 1    l j 1   l j      return l

User · Answer

def bubbleSort alist   if len alist   lt   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   gt  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

User · Answer

I consider adding my solution because ever solution here is having    greater time  greater space complexity  or doing too much operations   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   gt  arr j   1                   count    1                 arr j   arr j   1    arr j   1   arr j          if  count    count              break     return count

User · Answer

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   lt  arr b                arr a   arr b    arr b   arr a      return arr

User · Answer

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   gt  arr j                arr i   arr j    arr j   arr i               print  arr

User · Answer

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   gt  a key                   sorted   False                 t   a key-1   a key-1    a key   a key    t      print a

User · Answer

def bubble sort l       for passes left in range len l -1  0  -1           for index in range passes left               if l index   lt  l index   1                  l index   l index   1    l index   1   l index      return l

User · Answer

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   gt  values element   1                    hold   values element   1                   values element   1    values element                   values element    hold                  sorted   False     return values

User · Answer

To explain why your script isn t working right now  I ll rename the variable unsorted to sorted   At first  your list isn t yet sorted  Of course  we set sorted to False   As soon as we start the while loop  we assume that the list is already sorted  The idea is this  as soon as we find two elements that are not in the right order  we set sorted back to False  sorted will remain True only if there were no elements in the wrong order   sorted   False    We haven t started sorting yet  while not sorted      sorted   True    Assume the list is now sorted     for element in range 0  length           if badList element   gt  badList element   1               sorted   False    We found two elements in the wrong order             hold   badList element   1              badList element   1    badList element              badList element    hold       We went through the whole list  At this point  if there were no elements       in the wrong order  sorted is still True  Otherwise  it s false  and the       while loop executes again    There are also minor little issues that would help the code be more efficient or readable    In the for loop  you use the variable element  Technically  element is not an element  it s a number representing a list index  Also  it s quite long  In these cases  just use a temporary variable name  like i for  index    for i in range 0  length    The range command can also take just one argument  named stop   In that case  you get a list of all the integers from 0 to that argument   for i in range length    The Python Style Guide recommends that variables be named in lowercase with underscores  This is a very minor nitpick for a little script like this  it s more to get you accustomed to what Python code most often resembles   def bubble bad list    To swap the values of two variables  write them as a tuple assignment  The right hand side gets evaluated as a tuple  say   badList i 1   badList i   is  3  5   and then gets assigned to the two variables on the left hand side   badList i   badList i 1      bad list i   bad list i 1    bad list i 1   bad list i     Put it all together  and you get this   my list    12  5  13  8  9  65   def bubble bad list       length   len bad list  - 1     sorted   False      while not sorted          sorted   True         for i in range length               if bad list i   gt  bad list i 1                   sorted   False                 bad list i   bad list i 1    bad list i 1   bad list i   bubble my list  print my list    I removed your print statement too  by the way

[python] Bubble Sort Homework

Examples related to python

Examples related to algorithm

Examples related to sorting

Examples related to bubble-sort