Bubble Sort Algorithm

Introduction to Bubble Sort

Bubble sort is a simple and intuitive sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. Although it is not suitable for large data sets due to its O(n^2) time complexity, it is often used for educational purposes to explain the concept of sorting algorithms.

Step-by-Step Process

Consider an array with the following elements:


[4, 1, 5, 6, 2, 3]

To sort this array using bubble sort, follow these steps:

  1. Compare Adjacent Elements: Starting from the first element, compare the current element with the next element in the array.
  2. Swap if Necessary: If the current element is greater than the next element, swap them to put them in the correct order.
  3. Move to the Next Pair: Move to the next pair of adjacent elements and repeat the comparison and swapping process.
  4. Repeat: Continue this process until you reach the end of the array. After each pass, the largest unsorted element will be moved to its correct position.
  5. Multiple Passes: Repeat the entire process for n-1 passes (where n is the number of elements in the array) until the array is completely sorted.

Let's apply these steps to the example array:

  • First Pass: [4, 1, 5, 6, 2, 3] -> [1, 4, 5, 6, 2, 3] -> [1, 4, 5, 6, 2, 3] -> [1, 4, 5, 2, 6, 3] -> [1, 4, 5, 2, 3, 6]
  • Second Pass: [1, 4, 5, 2, 3, 6] -> [1, 4, 5, 2, 3, 6] -> [1, 4, 2, 5, 3, 6] -> [1, 4, 2, 3, 5, 6]
  • Third Pass: [1, 4, 2, 3, 5, 6] -> [1, 2, 4, 3, 5, 6] -> [1, 2, 3, 4, 5, 6]
  • Fourth Pass: [1, 2, 3, 4, 5, 6]
  • Fifth Pass: [1, 2, 3, 4, 5, 6]

Pseudo Code for Bubble Sort

Below is the pseudo code for the bubble sort algorithm:


function bubbleSort(array)
    n = length(array)
    for i = 0 to n-1 do
        for j = 0 to n-1-i do
            if array[j] > array[j+1] then
                swap(array[j], array[j+1])
end function

Explanation:

  • Initialize: The function starts by determining the length of the array, n.
  • Outer Loop: The outer loop runs from 0 to n-1, representing each pass through the array.
  • Inner Loop: The inner loop runs from 0 to n-1-i, representing the comparison of adjacent elements in each pass. The range decreases with each pass because the largest elements are moved to their correct positions at the end of the array.
  • Comparison and Swap: Within the inner loop, adjacent elements are compared. If the current element is greater than the next element, they are swapped.

Python Program to Implement Bubble Sort

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# Example usage:
array = [4, 1, 5, 6, 2, 3]
print("Original array:", array)
sorted_array = bubble_sort(array)
print("Sorted array:", sorted_array)  # Output: [1, 2, 3, 4, 5, 6]

This Python program defines a function to perform bubble sort on an array. The function iterates through the array, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the array is sorted.