CODEWITHSUNDEEP
pseudocodebubble-sort
Coder88
Coder88

Reputation: 1055

How these pseudocodes for bubble sort works?

I got this pseudocode from Wikipedia:

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

And this from a book (named Principles of Computer Science)

BubbleSort( list )
    length  <-- lenght of list
    do  {
        swapped_pair    <-- false
        index       <-- 1
        while index <= length - 1 {
            if list[index] > list[index + 1] {
                swap( list[index], list[index + 1] )
                swapped_pair = true
                index <-- index + 1
            }
        }
    } while( swapped = true )
end

I don't know which is better pseudocode.

The parts I don't understand is the swapped_pair <-- false part and the last lines.

In the line 4 when it's written swapped=false or swapped_pair <-- false.

Why it's set to false at the start? What would happen if it weren't set to false?

And the last lines, on the Wikipedia it's written:

       end if
     end for
   until not swapped
end procedure

And on the pseudocode from the book it's written:

while( swapped = true )

What does these last lines mean?

Upvotes: 0

Views: 844

Answers (1)

M.Paunov
M.Paunov

Reputation: 1887

The swapped variable keeps track if any swaps were made in the last pass through the array.

  • If a swap was made, the array is still not sorted and we need to continue.
  • If no swaps were made, then the array is already sorted and we can stop there. Otherwise we will do redundant iterations.

This is one of the optimizations that we ca do to make bubble sort more efficient. If you are interested in more optimizations you can look here: http://www.c-programming-simple-steps.com/bubble-sort.html

However, even optimized, bubble sort is too inefficient to be used in practice. It is an interesting case to look at, while learning, but if you need a simple sort algorithm use insertion sort instead.

Upvotes: 1

Related Questions