Bubble Sort

[Admin]

The Bubble Sort is a very slow algorithm but it is one of the simplest which is why it is often used to introduce students to the concept of sorting.

Imagine you are looking at numbers on a screen. There is a line of numbers but the screen is so small you can only see 2 numbers at any one time. Let the amount of numbers be n and if we take the first number as being position 0 then the last number is in position n-1.

Now to start with we compare the number in position 0 with the number in position 1. If the number in position is bigger than the number in position 2 then you swap the postion of the numbers, so that the number that was in position 1 is now in position 0 and the number that was in position 0 is now in position 1.

However, if the number in position 0 is not bigger or is equal to the number in position 1 then leave them as they are. Now look at the numbers in position 1 and position 2 and repeat the process. Move down the line of numbers until you compare the last two in positions n-2 and n-1. Once you have completed the process with these two numbers you will be able to conclude that the largest number is now in position n-1. The number in position n-1 is therefore sorted and will not have to be included in the next run through the line.

You now start again at position 0 and position 1 and compare them again. You will run through the line as before but this time you will stop when you compare the numbers in position n-3 and n-2 (as n-1 is in the correct position). At the end of this line check you will know that n-2 is now in it's sorted position as the second biggest number and will not have to be checked again.

Continue these line searches until you are only left with position 0 and position 1. If you don't know how many numbers are in the line then these positions can also be known as n-(n) and n-(n-1).

Step 1: Create an array of a number variable to hold the line of numbers.
Step 2: Create a FOR...LOOP starting at position n-1 and decreasing by 1 for each line search.
Step 3: Create a FOR...LOOP nested in the previous FOR...LOOP to run through the numbers in the array until you reach the position of the last unsorted number which will be controlled by the outer FOR...LOOP .
Step 4: Create an IF statement to compare the two positions in the array and swap them if required.

[helma]

Complexity is O(n2) for arbitrary data, but approaches Θ(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better since at least one item is moved forward or backward to its place in the list with each pass. Gnome sort optimizes the moving forward and backward instead of blindly looping through all items.

Since at least one item is moved into its final place for each pass, an improvement is to decrement the last position checked on each pass.

The name "sinking sort" comes from elements sinking down to their proper position. Contributed by Ken Tata (Ken.Tata@onsemi.com) 22 December 2000. After LK.
-----------
Breast Augmentation | Breast Enlargement