Implement Bubble sort easily in your program
Tags: programming, datastructures, algorithms, python
Published: 2023-10-31 13:30:00

Bubble sort is a simple and basic sorting algorithm that repeatedly steps through the list to be sorted, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted. In this article, we will guide you through the implementation of the bubble sort algorithm in Python.

## How Bubble Sort Works

Step 1: Start by comparing the first two elements of the list. If the first element is greater than the second element, swap them. If not, leave them as they are.

Step 2: Move to the next pair of elements and compare them. Again, if the first element is greater than the second element, swap them. Otherwise, leave them as they are.

Step 3: Repeat this process for each adjacent pair of elements in the list, moving from left to right. Each time you compare and potentially swap elements, the largest element in the unsorted part of the list "bubbles" up to its correct position at the end.

Step 4: After completing one pass through the list, the largest element will have moved to its correct position at the end. Now, you can ignore this element and repeat the same process for the remaining unsorted part of the list.

Step 5: Continue these passes until the entire list is sorted. In each pass, the largest remaining element will bubble up to its correct position, gradually sorting the list from left to right.

Step 6: The process stops when no more swaps are needed, indicating that the list is fully sorted.

![Bubble sort](https://upload.wikimedia.org/wikipedia/commons/c/c8/Bubble-sort-example-300px.gif)

## Implementation Steps

Let's dive into the implementation of the bubble sort algorithm:

Step 1: Prompt the user to enter the size of the array by using the `input()` function and convert it to an integer using the `int()` function. Store the value in a variable named `n`.

Step 2: Create an empty list called `arr` to store the elements of the array.

Step 3: Use a `for` loop to iterate `n` times. Inside the loop, prompt the user to enter each element of the array using the `input()` function, convert it to an integer, and append it to the `arr` list.

Step 4: Initialize a counter variable, `counter`, to 1.

Step 5: Set up a `while` loop that will continue until the `counter` is less than `n`.

Step 6: Inside the `while` loop, use a nested `for` loop to iterate from 0 to `n-counter`. This loop will iterate over the unsorted part of the array.

Step 7: Within the nested `for` loop, compare each element with its adjacent element. If the current element is greater than the next element, swap them. Store the value of the current element in a temporary variable, `temp`, before swapping.

Step 8: Increment the `counter` by 1 after the nested `for` loop completes. This signifies that the largest element has been moved to its correct position at the end of the array.

Step 9: After the `while` loop completes, use a `for` loop to iterate over the sorted `arr` list and print each element, separated by a space, using the `print()` function with the `end` parameter set to `" "`.

![Bubble Sort lock system](https://miro.medium.com/v2/resize:fit:1400/1*-qR66X2iwdcjhaqq10y9JQ.gif)

## Code

```python
n=int(input("Enter size of array: "))
arr = []

for i in range(n):
    arr.append(int(input()))

print('Unsorted Array: ')
for i in arr:
    print(i, end=" ")

counter=1
while(counter<n):
    for i in range(n-counter):
        if(arr[i] > arr[i+1]):
            temp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = temp
    counter+=1

print('Sorted Array: ')
for i in arr:
    print(i, end=" ")
```

## Example

```bash
Enter the size of the array: 6
10
5
8
3
6
2
Unsorted Array: 10 5 8 3 6 2
Sorted Array: 2 3 5 6 8 10
```

## Time Complexity

The time complexity of the bubble sort algorithm is O(n^2) in the worst and average case. This means that the algorithm's performance decreases significantly as the number of elements increases. However, bubble sort performs well for small-sized arrays or partially sorted arrays.

## Conclusion

Bubble sort is a simple and intuitive sorting algorithm that can be easily implemented in Python. While it may not be the most efficient sorting algorithm for large datasets, it serves as a good starting point for understanding sorting algorithms and their implementations. By following the step-by-step guide provided in this article, you can successfully implement bubble sort in Python and sort your lists efficiently.