Sorting Algorithms–Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. The strategy followed by bubble sort is to compare adjacent elements in the input list (e.g. array) and interchange them if they are out of order.

Each time the algorithm passes through the input list, the highest valued element gets positioned at the right place i.e. at the end of the list. This behaviour of bubbling elements to right position after every pass is responsible for naming this sorting technique as ‘Bubble Sort’.

Let us apply the Bubble sort algorithm on a integer array. The concept can be extended to other type of data as well.

Algorithm: Bubble Sort

Input: An array of integer elements (input) and the size of the array (n)

Output: In-place sorted array.

Description: At the core, Bubble Sort compares two consecutive elements of the list and interchanges them if they are out of order.

Pseudo-code:

set swapped = true
set i = 0
while i < n-1 && swapped == true do
    swapped = false
    for j=0 to n-1-i do
        if input[j] > input [j+1] then
            swap input[j] and input[j+1]
            set swapped = true
        endif
    done
done

Performance:

The worst case performance of Bubble sort is categorized as O(n2) because the outer loop executes ‘n’ times, once for each element of the array. Each of these iterations cause the inner loop to execute ‘n-outer_loop_ counter’ times.

C++ source code for the above algorithm:

void bubbleSort(int input[], int n) {
    bool swapped = true;
    for (int i = 0; i < n - 1 && swapped == true; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (input[j] > input[j + 1]) {
                // Swap the values
                int temp = input[j];
                input[j] = input[j + 1];
                input[j + 1] = temp;
                // set swapped to indicate that elements were
                // swapped
                swapped = true;
            } // endif
        } // end of inner for
    } // end of outer for
} //end of method


References:

Advertisements

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