Bubble Sort

DESCRIPTION
This is one of the simplest comparison-based sorting algorithm.
It starts at the beginning of the input array A, and compares the first two elements (i.e., a_1,a_2), and if a_1 is greater than a_2 it swaps them.
Bubble Sort keeps doing this for each pair of adjacent elements until it reaches the end of the array. Once the first pass is completed, the algorithm then starts again with the first two elements, repeating until no swaps have occurred on the last pass.

COMPLEXITY ANALYSIS
This algorithm’s average and worst case time complexity is O(n^2), so it is rarely used to sort large, unordered data sets. In fact, Bubble Sort can be used to sort a small number of items or a list of items of arbitrary length that are nearly sorted (i.e., so that very few items are out of place).
Since the algorithm works in-place, no extra memory is needed, thereby its space complexity is constant O(1).

IMPLEMENTATION (Java)

public static void bubbleSort(int[] a) {

    if(a==null || a.length==1) {
        return; // simply return if the input array is either null or contains only one element
    }
    int size = a.length;
    int tmp;
    boolean toSwap = true;
    // loop until an entire scan of the array requires no swap
    while(toSwap) {
        toSwap = false;
        // linear scan of the input array
        for(int i=0; i < size-1; ++i) { 
            if(a[i+1] < a[i]) { // swap two adjacent elements if they are in the wrong order
                tmp = a[i];
                a[i] = a[i+1];
                a[i+1] = tmp;
                toSwap = true;
            }
        }
    }
}

IMPLEMENTATION (Python)


def bubble_sort(a):

    # base cases
    if not a or len(a) == 0:
        return
    if len(a) == 1:
        return
    else:
        to_swap = True
        # loop until an entire scan of the array requires no swap
        while to_swap:
            to_swap = False
            i = 0
            # linear scan of the input array
            while i < len(a) - 1:
                if a[i] > a[i+1]: # swap two adjacent elements if they are in the wrong order
                    tmp = a[i]
                    a[i] = a[i+1]
                    a[i+1] = tmp
                    to_swap = True
                i += 1
        return

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

%d bloggers like this: