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