Implement Bubble sort easily in your program

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.

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 " ".

Code

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

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.