.

Wednesday, July 22, 2015

Bubble Sort - using Python




Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.


Explanation

Let us take the array of numbers "7 6 5 4 3 2 1", and sort the array from lowest number
to greatest number using bubble sort. In each step, elements written in blue  are being compared.
 six passes will be required.

First Pass: swaps- 6
(7 6 5 4 3 2 1) --> (6 7 5 4 3 2 1)
(6 7 5 4 3 2 1) --> (6 5 7 4 3 2 1)
(6 5 7 4 3 2 1) --> (6 5 4 7 3 2 1)
(6 5 4 7 3 2 1) --> (6 5 4 3 7 2 1)
(6 5 4 3 7 2 1) --> (6 5 4 3 2 7 1)
(6 5 4 3 2 7 1) --> (6 5 4 3 2 1 7)

Second Pass: swaps -5
(6 5 4 3 2 1 7) --> (5 6 4 3 2 1 7)
(5 6 4 3 2 1 7) --> (5 4 6 3 2 1 7)
(5 4 6 3 2 1 7) --> (5 4 3 6 2 1 7)
(5 4 3 6 2 1 7) --> (5 4 3 2 6 1 7)
(5 4 3 2 6 1 7) --> (5 4 3 2 1 6 7)
(5 4 3 2 1 6 7) --> (5 4 3 2 1 6 7)

Third Pass: swaps - 4
(5 4 3 2 1 6 7) --> (4 5 3 2 1 6 7)
(4 5 3 2 1 6 7) --> (4 3 5 2 1 6 7)
(4 3 5 2 1 6 7) --> (4 3 2 5 1 6 7)
(4 3 2 5 1 6 7) --> (4 3 2 1 5 6 7)
(4 3 2 1 5 6 7) --> (4 3 2 1 5 6 7)
(4 3 2 1 5 6 7) --> (4 3 2 1 5 6 7)

Forth Pass: swaps - 3
(4 3 2 1 5 6 7) --> (3 4 2 1 5 6 7)
(3 4 2 1 5 6 7) --> (3 2 4 1 5 6 7)
(3 2 4 1 5 6 7) --> (3 2 1 4 5 6 7)
 (3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)
(3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)
(3 2 1 4 5 6 7) --> (3 2 1 4 5 6 7)

fifth pass: swaps - 2
(3 2 1 4 5 6 7) --> (2 3 1 4 5 6 7)
(2 3 1 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)
(2 1 3 4 5 6 7) --> (2 1 3 4 5 6 7)

sixth pass : swaps - 1
(2 1 3 4 5 6 7)--> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7) --> (1 2 3 4 5 6 7)
------------------------
__author__ = 'kamal'def bubblesort(alist):
    for numofpass in xrange(0, len(alist)-1):
        for i in xrange(0, len(alist)-1):
            if alist[i] > alist[i+1]:
                temp = alist[i]
                alist[i] = alist[i+1]
                alist[i+1] = temp

alist = [7, 6, 5, 4, 3, 2, 1]
bubblesort(alist)
print("----O-u-t-p-u-t-----")
print(alist)

Output--

----O-u-t-p-u-t-----
[1, 2, 3, 4, 5, 6, 7]

No comments :

Post a Comment

There was an error in this gadget