Bubble sort

In this tutorial I will be explaining about the worst sorting algorithm mentioned by the great computer scientists in the world during the ACM AM Turing centenary ceremony celebration.

Bubble sort works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. It only uses comparisons to operate on elements, it is a comparison sort.

Lets see an example here:

Input list:

[8, 7, 5, 4, 3, 2, 1]

While sorting:

[87, 5, 4, 3, 2, 1]
[7, 85, 4, 3, 2, 1]
[7, 5, 84, 3, 2, 1]
[7, 5, 4, 83, 2, 1]
[7, 5, 4, 38, 2, 1]
[7, 5, 4, 3, 2, 81]
[75, 4, 3, 2, 1] [8]
[5, 74, 3, 2, 1] [8]
[5, 4, 73, 2, 1] [8]
[5, 4, 3, 72, 1] [8]
[5, 4, 3, 2, 71[8]
[54, 3, 2, 1] [7][8]
[4, 53, 2, 1] [7][8]
[4, 3, 52, 1] [7][8]
[4, 3, 2, 51[7][8]
[43, 2, 1] [5][7][8]
[3, 42, 1] [5][7][8]
[3, 2, 41[5][7][8]
[32, 1] [4][5][7][8]
[2, 3, 1] [4][5][7][8]
[21] [3][4][5][7][8]
[1] [2][3][4][5][7][8]

Sorted list:

[1][2][3][4][5][7][8]

Python code:

# /usr/bin/python
# A program to do bubble sort

def bubble_sort(inp_list):
    '''Bubble sort function'''
    j = len(inp_list)-1   # C * 1
    while j != 0:         # C * n
       for k in range(j):      # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
            if inp_list[k] > inp_list[k+1]: # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
                temp = inp_list[k]             # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
                inp_list[k] = inp_list[k+1]    # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
                inp_list[k+1] = temp           # C * (n-1) * (\latex{\sum\limits_{k=0}^j k})
        j = j - 1    # C * (n-1)
    return inp_list  # C * 1

def main():
    '''Main function'''
    inp =[]
    s = int(raw_input('How many elements would you like to enter: '))
    for x in range(s):
        inp.append(int(raw_input('Enter element #' + `x+1` + ': ')))
    print "Initial list: ", inp
    output_list = bubble_sort(inp)
    print "Sorted list: ", output_list

if __name__ == "__main__":
    main()

Best case (if the list is already sorted): O(n)
Worst case (if the list is sorted in descending order): C*n*\latex{\sum\limits_{k=0}^n k} = O(n^2)

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