Bubble Sort Algorithm

After first sort. The highest number has bubbled to the end of the array.

After first sort. The highest number has bubbled to the end of the array.

The Bubble Sort arranges the numbers in ascending order. To do this first it compares the first element with the element on it’s right; if the first element is larger; the two elements swap. It then moves onto the second element and repeats the comparing process. It continues this until the (n-1)th element; by this time, the largest number should be in the nth element. The largest number bubbles to the top! See Image above for a more visual explanation.

Now the largest number is in the nth element, we can say it has been sorted. Now we have a slightly smaller array to sort.

The second sort begins with the first element, compares, swaps if necessary, up to the (n-2)th element. It doesn’t need to check the last element because it’s already sorted. The third sort begins with the first element, compare, swaps if necessary, up to the (n-3)th element. The fourth, fifth, sixth sort continue in the same way until the array is sorted.

The total number of comparisons is equal to n(n-1)/2. This can be simplified to n^2/2 – n/2, where n^2 dominates. The bubble sort is simple and effective for small arrays, but this is a very long process as n increases.

Here’s an example of using it in a program:

</pre>
int main(){

 //Array I want to sort.
 int a[7] = {1,5,9,6,2,3,8};

 //Finding size of array
 int s = sizeof(a)/sizeof(*a);

 //Bubble Sort
 for (int i=0; i<s; i++)
 {
 for (int j=0; j<s-1; j++)
 {
 if (a[j]>a[j+1])
 {
 int temp = a[j+1];
 a[j+1] = a[j];
 a[j] = temp;
 }
 }
 }
 for (int i=0; i<s; i++){
 cout << a[i];
 }
}
<pre>
Advertisements

One thought on “Bubble Sort Algorithm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s