Bubble sort algorithm - In this article, we will learn about one of the sorting algorithms - Bubble sort. Time complexity of this algorithm is O(n^2) and space complexity being O(1).
Bubble Sort Algorithm
for i = 0 to [length(array) - 1] begin # To keep track of whether a swap has happened flag = 0 # Last 'i' elements will always be sorted for j = 0 to [length(array) - i - 1] begin # Check if array[j] > array[j+1], Swap if True if array[j] > array[j+1] begin swap array[j] and array[j+1] flag = 1 endif endfor if flag == 0 begin break endif endfor return array
Example
Consider the following list-
Here, length of the array is 8, hence there outer loop, which we will refer to as a pass, will be executed 8 times, while inner loop will be executed (8 - 0 - 1) times. Lets see the first pass.
Pass 1-1:
i = 0, j = 0 array[0] = 5, array[0+1] = 3 array[0] > array[1] Result - 5 and 3 will be swapped.
Pass 1-2:
i = 0, j = 1 array[1] = 5, array[1+1] = 7 array[1] < array[2] Result - Nothing happens
Pass 1-3:
i = 0, j = 2 array[2] = 7, array[2+1] = 1 array[2] > array[3] Result - 7 and 1 will be swapped
Pass 1-4:
i = 0, j = 3 array[3] = 7, array[3+1] = 4 array[3] > array[4] Result - 7 and 4 will be swapped
Pass 1-5:
i = 0, j = 4 array[4] = 7, array[4+1] = 8 array[4] < array[5] Result - Nothing happens
Pass 1-6:
i = 0, j = 5 array[5] = 8, array[5+1] = 2 array[5] > array[6] Result - 8 and 2 will be swapped
Pass 1-7:
i = 0, j = 6 array[6] = 8, array[6+1] = 6 array[7] > array[7] Result - 8 and 6 will be swapped
Observation - After once complete pass, it can be observed that, the largest element in the array is bubbled up to the last position in the array. In another words, after one pass, one element in the array is sorted. Also, if no swap happens, it can be concluded that the array is sorted and we can break out of the loop. To keep track of this, we have introduced variable
flag
in the algorithm.Similarly, after subsequent passes, array will look like -
After the 5th pass, there will be no swapping. Hence there is no need for more iterations and the process can be stopped.
Python Implementation:
def bubble_sort(array): n = len(array) for i in range(n): flag = 0 for j in range(n-i-1): if array[j] > array[j+1]: array[j], array[j+1] = array[j+1], array[j] flag = 1 if flag == 0: break my_array = [5, 3, 7, 1, 4, 8, 2, 6] bubble_sort(my_array) print my_array
Output:
[1, 2, 3, 4, 5, 6, 7, 8]
0 comments:
Post a comment