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
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;
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)));
$ 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 Programming Language Examples