0

Im trying to implement a code in python for bubble sort using an algorithm:
I managed to write a code using double for, and it works fine. 

A=[43,21,12,80,3,2,35]
lengthOfList = len(A)
for i in range (lengthOfList):
    for k in range(lengthOfList-1, i,-1 ):
        if ( A[k - 1]> A[k]):
            temp = A[k]
            A[k] = A[k-1]
            A[k-1] = temp
print A

Im trying to adopt the login of this algorithm more than 3 hours now but, I cant get it work:

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       #if this pair is out of order
       if A[i-1] > A[i] then
         # swap them and remember something changed
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Im kind of stuck on the repeat & until stage. I know I have to use while, but I cant get the logical idea of how to implement that using while

Vinay Jain
  • 1,653
  • 20
  • 28
Bobys
  • 677
  • 1
  • 14
  • 37
  • possible duplicate of [Bubble Sort Homework](http://stackoverflow.com/questions/895371/bubble-sort-homework) – Cory Kramer Nov 19 '14 at 19:23
  • The result its obviously the same, but those codes are not following the algorithm Im asking for. I have checked this out before I post. – Bobys Nov 19 '14 at 19:25
  • replace `for i in range (lengthOfList):` by `while swapped`, set to true in the swap part, reset at each iteration – njzk2 Nov 19 '14 at 19:26
  • To exactly replicate the algorithm you posted, you would need a `do-while` loop which is [not directly available in Python](http://stackoverflow.com/questions/743164/do-while-loop-in-python) – Cory Kramer Nov 19 '14 at 19:27
  • If that is from the wiki page this is based on that http://pastebin.com/g3PMXSJA – Padraic Cunningham Nov 19 '14 at 19:32

1 Answers1

3

You're not adapting the code from wikipedia correctly;

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

Is jsut the same as the version above it, except that it takes advantage of the fact that after each run, last X entries are guaranteed to be sorted.

It's probably easier to envisage like this:

procedure bubbleSort(someList):
  while someList is not sorted:
    loop over all elements in the list:
      if the current item is larger than the next item:
        swap items

Bubble sort basically repeatedly scans through the list, swaping any two elements if they are relatively out of order. You just need to do this.

The only mildy tricky part is the "while someList is not sorted"; there are two ways to deal with this. One would be to write a function that simply tells you if the list is sorted, which you could do very simply like so:

def isListSorted(l):
  for i in range(len(l)-1):
    if l[i] > l[i+1]: return False

  return True

Alternatively, you know that if it manages to loop through the whole list without swapping any elements, it is sorted, so you can use a flag to keep track of that;

def bubbleSort(l):
  isSorted = False
  while not isSorted:
    isSorted = True
    for i in range(len(l)-1):
      if l[i] > l[i+1]:
        isSorted = False
        l[i], l[i+1] = l[i+1], l[i]

Or, if you want to use the function mentioned above;

def bubbleSort2(l):
  while not isListSorted(l):
    for i in range(len(l)-1):
      if l[i] > l[i+1]:
        l[i], l[i+1] = l[i+1], l[i]

Not that the first solution is faster, because it's not looping through the whole list at the begining of every loop to check that it's sorted, but then this isn't about optimisation, as you're lookign at bubble sort.

If you are still bothered about adding in the optimisation mentioneed on the page; it's a simple task;

def bubbleSort(l):
  isSorted = False
  n = len(l)-1
  while not isSorted:
    isSorted = True
    for i in range(n):
      if l[i] > l[i+1]:
        isSorted = False
        l[i], l[i+1] = l[i+1], l[i]
    n-=1


def bubbleSort2(l):
  n = len(l)-1
  while not isListSorted(l):
    for i in range(n):
      if l[i] > l[i+1]:
        l[i], l[i+1] = l[i+1], l[i]
    n-=1
will
  • 10,260
  • 6
  • 46
  • 69