Bubble sort algorithm is a simple sorting algorithm that repeatedly compares adjacent elements in a list or array and swaps them if they are in the wrong order. It is called bubble sort because the smaller elements “bubble” to the top of the list or array.
How Bubble Sort Algorithm Works
Bubble sort algorithm works by repeatedly comparing adjacent elements in the list or array and swapping them if they are in the wrong order. The algorithm goes through the list or array multiple times until no more swaps are needed, which means the list or array is sorted.
Python Implementation of Bubble Sort Algorithm
Here’s an example of implementing the bubble sort algorithm in Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
In the above code, the bubble_sort function takes one argument, arr, which is the list or array to be sorted. The function uses two for loops to repeatedly compare adjacent elements in the list or array and swap them if they are in the wrong order. The outer for loop goes through the list or array multiple times, while the inner for loop compares adjacent elements in the list or array. The loop terminates when no more swaps are needed, which means the list or array is sorted.
Example of Bubble Sort Algorithm
Let’s say we have an unsorted list of numbers as follows:
arr = [5, 2, 8, 1, 9, 4]
We want to sort this list using the bubble sort algorithm. We can do this by calling the bubble_sort function with the list arr as an argument:
bubble_sort(arr)
After executing this code, the variable arr will contain the sorted list:
[1, 2, 4, 5, 8, 9]
Advantages and Disadvantages of Bubble Sort Algorithm
The bubble sort algorithm has the following advantages and disadvantages:
Advantages:
- Simple and easy to understand.
- Works well on small datasets.
Disadvantages:
- Inefficient for large datasets.
- Time complexity is O(n^2), where n is the number of elements in the list or array.
Conclusion
In conclusion, bubble sort algorithm is a simple sorting algorithm that repeatedly compares adjacent elements in a list or array and swaps them if they are in the wrong order. Although it is easy to understand, it is inefficient for large datasets and has a time complexity of O(n^2). It is useful for sorting small datasets or for educational purposes.
FAQs
- What is the time complexity of bubble sort algorithm?
- The time complexity of bubble sort algorithm is O(n^2), where n is the number of elements in the list or array.
- What is the difference between bubble sort and selection sort?
- Bubble sort and selection sort are both simple sorting algorithms, but bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order, while selection sort finds the smallest element in the unsorted part of the list or array and swaps it with the first element in the unsorted part. Selection sort is generally faster than bubble sort for larger datasets.
For complete list of topic on DATA STRUCTURE AND ALGORITHM click hear