The idea behind the algorithm is simple: repeatedly compare adjacent elements in an array and swap them if they are not in sorted order. The algorithm repeats the above process until all the elements in the array are sorted. In each iteration of the algorithm, the algorithm compares all pairs of adjacent elements. The adjacent elements are swapped if they are not in sorted order.
Example:
Let the initial array be [5, 4, 9, 3, 7, 6].
First iteration:
Compare the elements in index 1 and 2: 5, 4. They are not in sorted order. Swap them.
Array = [4, 5, 9, 3, 7, 6].
Compare the elements in index 2 and 3: 5, 9. They are in sorted order. Don’t swap.
Array = [4, 5, 9, 3, 7, 6].
Compare the elements in index 3 and 4: 9, 3. They are not in sorted order. Swap them.
Array = [4, 5, 3, 9, 7, 6].
Compare the elements in index 4 and 5: 9, 7. They are not in sorted order. Swap them.
Array = [4, 5, 3, 7, 9, 6].
Compare the elements in index 5 and 6: 9, 6. They are not in sorted order. Swap them.
Array = [4, 5, 3, 7, 6, 9]
The array after the first iteration is [4, 5, 3, 7, 6, 9].
The below table describes the complete sorting process, including other iterations. For brevity, only the steps in which swapping occurs are shown.
First iteration:
[5, 4, 9, 3, 7, 6]
[4, 5, 9, 3, 7, 6]
[4, 5, 3, 9, 7, 6]
[4, 5, 3, 7, 9, 6]
[4, 5, 3, 7, 6, 9]
Second iteration:
[4, 3, 5, 7, 6, 9]
[4, 3, 5, 6, 7, 9]
Third iteration:
[3, 4, 5, 6, 7, 9]
Source code: Bubble Sort
for i in range(0, n):
for j in range(0, n-1):
# If the pair is not in sorted order
if arr[j] > arr[j+1]:
# Swap the pair to make them in sorted order
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
if __name__ == "__main__":
arr = [5, 4, 9, 7, 3, 6]
n = len(arr)
arr = bubble_sort(arr, n)
print (arr)
Explanation: The algorithm has two loops. The first loop iterates over the array n times and the second loop n-1 times. In each iteration of the first loop, the second loop compares all pairs of adjacent elements. If they are not sorted, the adjacent elements are swapped to make them in sorted order. The maximum number of comparisons required to assign an element to its right position in sorted order is n-1 because there are n-1 other elements. Since there are n elements and each element takes maximum n-1 comparisons; the array gets sorted in O(n^2) time. Hence, the worst-case time complexity is O(n^2). The best time complexity in this version of bubble sort is also O(n^2) because the algorithm does not know that it is completely sorted. Hence, even though it is sorted, the algorithm keeps comparing the elements resulting in the time complexity of O(n^2).
Part 2 (Optional): Optimised Bubble Sort
The above algorithm can be optimised if we could stop comparison when all the elements get sorted. This can be done by using an additional flag variable that says the algorithm when to stop.
not_sorted = True
while(not_sorted):
not_sorted = False
for i in range(0, n-1):
# If the pair is not in sorted order
if arr[i] > arr[i+1]:
# Swap them
arr[i], arr[i+1] = arr[i+1], arr[i]
# Remember that the array was not sorted
# at the beginning of the iteration
not_sorted = True
return arr
if __name__ == "__main__":
arr = [5, 4, 9, 7, 3, 6]
n = len(arr)
arr = optimised_bubble_sort(arr, n)
print (arr)
In the above algorithm, the flag variable not_sorted remains true as long as a swap occurs in an iteration of the inner for loop. This optimised version of bubble sort requires one additional iteration after the array is sorted to check whether the array is sorted or not.
The best-case time complexity of this algorithm is O(n). This occurs when all the elements of the input array are already in sorted order, and it requires one iteration to check if the array is in sorted order or not.
from Linux Hint https://ift.tt/3wEDK1W
0 Comments