## Schaum's Outline of Principles of Computer Science

Paul Tymann, Carl Reynolds

Mentioned 1

Learn the essentials of computer science Schaumâ€™s Outline of Principles of Computer Science provides a concise overview of the theoretical foundation of computer science. It also includes focused review of object-oriented programming using Java.

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?

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.

Realated tags