Python Tutorial

# Bubble Sorting Python Program

## What is bubble sort ?

• Bubble sort is repeatedly comparing pairs of adjacent elements and then swapping their positions if they exist in the wrong order.
• Bubble sorting can be used for collections of numbers, strings, characters etc.
• The basic idea behind bubble sort is to imagine that the records to be sorted are kept in an array held vertically. The records with lower key values are 'light' and bubble up to the top. We make repeated iteration over the array from bottom to top.
Example, consider sorted collection of elements

## Bubble Sort Time Complexity

Time complexity of bubble sort is O(n^2) in both worst and average cases, here complete array is iterated for each elements.

## Bubble Sort Python Program

```#!/usr/bin/python

def bubble_sort(list_vals):
temp = 0;
n = len(list_vals);
for k in range(0,  n-1):

# (n-k-1) to ignore the comparisons of elements
# which have already been compared in earlier iterations
for i in range(0, n-k-1):
if (list_vals[i] > list_vals[i+1]):
# here swapping of positions.
temp = list_vals[i];
list_vals[i] = list_vals[i+1];
list_vals[i+1] = temp;
return list_vals;

if __name__ == "__main__":
list_vals = [30, 10, 20, 70, 60, 80, 50, 40];
print("Collection before sorting: %s" % str(list_vals));
print("Sorting list elements: %s" % str(bubble_sort(list_vals)));
```
Output:
```\$ python bubble_sort.py
Collection before sorting: [30, 10, 20, 70, 60, 80, 50, 40]
Sorting list elements: [10, 20, 30, 40, 50, 60, 70, 80]
```

Python Tutorial