Bubble sort implementation from Pseudocode

Question

Here is the pseudocode I have

Procedure
    i <- n
    last <- 1
    while i > last do
        for j <- 1 to i-1 do
            if t[j] > t[j+1] do
               t[j] <-> t[j+1] {switch values}
               last <- j
            end if
        end for
        i <- last
        last <- 1
    end while
 end

I just need to state why this is an improvement on the standard bubble sort and do a trace of the algorithm. That I can manage. To do some test and for learning purposes, I decided to code it in python. My implementation do not work.

def bubbleSort(arr):
    n = len(arr)
    i = n
    last = 1

    while (i > last):
        for j in range(0, i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
                last = j
        i = last
        last = 1

# Driver code to test above
arr = [5, 3, 89, 100, -4, 7, 45]

bubbleSort(arr)

The output I get is 3 ,5 ,89,-4 ,7 ,45 ,100 witch mean that it only does the first pass in the inner loop but stop right after.

Is there something I am translating wrong from the pseudocode ?

score 1 · Answer 1 · answered Apr 01 '18 at 03:00

The last thing you do in the while loop is

i = last
last = 1

Since last starts as 1, after the first iteration this is will make both i and last 1. So, the while (i > last) condition fails and the loop exits.

To see this a little more clearly, here is your code with only the relevant parts:

def bubbleSort(arr):
    i = len(arr)
    last = 1
    while (i > last):
        i = last
        last = 1

You may want to re-read the pseudo-code to see if that is actually what it says.

I missed an important line in the pseudocode when creating the post. last take the value of j in the inner loop. I eddited the OP. — CareFace, Apr 01 '18 at 03:22

score 1 · Answer 2 · answered Apr 01 '18 at 03:27

1

Here is your answer.

def bubbleSort(arr):
    n = len(arr)
    i = n
    last = 1

    while (i > last):
        for j in range(0, i-1):
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]
        i = i - 1

# Driver code to test above
arr = [5, 3, 89, 100, -4, 7, 45]

bubbleSort(arr)

answered Apr 01 '18 at 03:27

Haris Nadeem

1,322
11
24

The thing is that you never use last in your inner loop so there was never really ever need to use it. Second, you want to iterate through the list so you want to be decrementing by 1 since you start at n – Haris Nadeem Apr 01 '18 at 03:29
Yes, I need to use last in the inner loop. I updated the pseudocode. Your bubblesort work great but the version from the pswudocode with the use of the extra variable is supposed to make the sort more efficiant. – CareFace Apr 01 '18 at 04:08
Oh I see what you were trying to do. If you look at this, they give a nice explanation on how using the extra variable helps. https://stackoverflow.com/questions/16195092/optimized-bubble-sort-java – Haris Nadeem Apr 01 '18 at 04:13
Yeah, I saw that one. The extra variable they added is only to check if an entire pass of the inner loop ends without a swap. If that happen, we know the array is already ordered and just exit. The pseudocode provided for assignment does not seem to be doing that. – CareFace Apr 02 '18 at 02:09

Bubble sort implementation from Pseudocode

2 Answers2