CODEWITHSUNDEEP
pythonalgorithm
Bobys
Bobys

Reputation: 677

Bubble Sort following an algorithm

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

Upvotes: 0

Views: 693

Answers (1)

will
will

Reputation: 10650

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

Upvotes: 3

Related Questions