Bubble Sort

[MMcCarthy]

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.

[jbiet]

please also explain about heap sort merge sort and all types of sorts in data structures

[Ganon11]

There's a wonderful article in the Java section about a generic heap sort - I imagine it wouldn't be too difficult to translate this into C++.