Bubble sort in python

 Sorting is nothing  but arranging the number in ordered list. There are 5 types of sorting

1) Bubble sort

2) Selection sort

3) Insertion sort

4) Merge sort

5) Quick sort

In this post lets see briefly about bubble sort

Algorithm:

1. Start from the first element

2. Check two adjacent(nearest) element in the list

3. If second element is great than first number or first number is greater than second number then swap the position(small num should be arranged first)

4. Repeat this for entire list

5. Repeat this until no swap needed

Best time complexity: 0[n]

Average time complexity: 0[n^2]

Worst time complexity: 0[n^2]

Lets see the working with example:

Take list [61, 3, 43, 25, 16]

1) Iteration : 61, 3, 43, 25, 16
     Swap= true

  here 61 is greater than 3 so swap continue this for entire list

[3, 61, 43, 25, 16]

[3, 43, 61, 25, 16]

[3, 43, 25, 61, 16]

[3, 43, 25, 16, 61]

2) Iteration : 3, 43, 25, 16, 61
    Swap= true

Here 43 is greater than 25 so swap and continue

[3, 25, 43, 16, 61]

[3, 25, 16, 43, 61]

3) Iteration : 3, 25, 16, 43, 61
     Swap = true

Here 25 is greater than 16 so swap and continue

[3, 16, 25, 43, 61]

4) Iteration : 3, 16, 25, 43, 61
     Swap = false

So the sorted list is [3, 16, 25, 43, 61]

Another simple example:

List= [51, 2, 4, 15, 6]

1) Iteration: 51, 2, 4, 15, 6
    Swap= true

[2, 51, 4, 15, 16]

[2, 4, 51, 15, 16]

[2, 4, 15, 51, 16]

[2, 4, 15, 16, 51]

2) Iteration: 2, 4, 15, 16, 51
     Swap= false

Sorted list is [2, 4, 15, 16, 51]

Code for bubble sort:

list = [54,23,32,76,89,90,12,9]

print(list)

swapped = False

while(swapped == False):

    for i in range(0,len(list)-1):

        if list[i]>list[i+1]:

            temp= list[i]

            list[i]= list[i+1]

            list[i+1]= temp

            swapped= True

    if swapped== False:

                break

    swapped=False

print("sorted list is",list)

Output :

[54, 23, 32, 76, 89, 90, 12, 9]

sorted list is [9, 12, 23, 32, 54, 76, 89, 90]