Algorithm Bubble Sort Insertion Sort Selection Sort Complete Guide

Bubble Sort

Concept: Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Step-by-Step Example:

Let's sort an array [5, 3, 8, 4, 2] using Bubble Sort.

1. Initial Array: [5, 3, 8, 4, 2]
2. First Pass:
   • Compare 5 and 3; since 5 > 3, swap them → [3, 5, 8, 4, 2]
   • Compare 5 and 8; no swap needed → [3, 5, 8, 4, 2]
   • Compare 8 and 4; since 8 > 4, swap them → [3, 5, 4, 8, 2]
   • Compare 8 and 2; since 8 > 2, swap them → [3, 5, 4, 2, 8]
3. Second Pass:
   • Compare 3 and 5; no swap needed → [3, 5, 4, 2, 8]
   • Compare 5 and 4; since 5 > 4, swap them → [3, 4, 5, 2, 8]
   • Compare 5 and 2; since 5 > 2, swap them → [3, 4, 2, 5, 8]
   • Compare 5 and 8; no swap needed → [3, 4, 2, 5, 8]
4. Third Pass:
   • Compare 3 and 4; no swap needed → [3, 4, 2, 5, 8]
   • Compare 4 and 2; since 4 > 2, swap them → [3, 2, 4, 5, 8]
   • Compare 4 and 5; no swap needed → [3, 2, 4, 5, 8]
   • Compare 5 and 8; no swap needed → [3, 2, 4, 5, 8]
5. Fourth Pass:
   • Compare 3 and 2; since 3 > 2, swap them → [2, 3, 4, 5, 8]
   • Compare 3 and 4; no swap needed → [2, 3, 4, 5, 8]
   • Compare 4 and 5; no swap needed → [2, 3, 4, 5, 8]
   • Compare 5 and 8; no swap needed → [2, 3, 4, 5, 8]

At this point, the array is sorted.

Python Code for Bubble Sort:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Track if any swapping happens
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # Swap if the element found is greater than the next element
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # If no two elements were swapped by inner loop, then break
        if not swapped:
            break
    return arr

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

Insertion Sort

Concept: Insertion Sort builds the final sorted array one item at a time. It takes each element from the input and finds the appropriate position within the already sorted part of the array.

Step-by-Step Example:

Let's sort an array [5, 3, 8, 4, 2] using Insertion Sort.

1. Initial Array: [5, 3, 8, 4, 2]
2. Insert 3:
   • Take 3; insert it before 5 since 3 < 5 → [3, 5, 8, 4, 2]
3. Insert 8:
   • 8 is already in the correct position → [3, 5, 8, 4, 2]
4. Insert 4:
   • Take 4; insert it between 3 and 5 since 3 < 4 < 5 → [3, 4, 5, 8, 2]
5. Insert 2:
   • Take 2; insert it at the beginning since 2 < 3 → [2, 3, 4, 5, 8]

Array is now sorted.

Python Code for Insertion Sort:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        # Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example usage
array = [5, 3, 8, 4, 2]
sorted_array = insertion_sort(array)
print("Sorted array:", sorted_array)

Selection Sort

Concept: Selection Sort divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items. It repeatedly selects the smallest (or largest, depending on the sorting preference) element from the unsorted sublist, swaps it with the leftmost unsorted element (putting it in sorted order), and moves the sublist boundaries one element to the right.

Step-by-Step Example:

Let's sort an array [5, 3, 8, 4, 2] using Selection Sort.

1. Initial Array: [5, 3, 8, 4, 2]
2. Find Minimum and Swap:
   • Find the minimum element; it is 2.
   • Swap 2 with the first element (5) → [2, 3, 8, 4, 5]
3. Find Next Minimum and Swap:
   • Find the next minimum element in [3, 8, 4, 5]; it is 3.
   • No need to swap as 3 is already in the correct position → [2, 3, 8, 4, 5]
4. Find Next Minimum and Swap:
   • Find the next minimum element in [8, 4, 5]; it is 4.
   • Swap 4 with 8 → [2, 3, 4, 8, 5]
5. Find Next Minimum and Swap:
   • Find the next minimum element in [8, 5]; it is 5.
   • Swap 5 with 8 → [2, 3, 4, 5, 8]

Array is now sorted.

Python Code for Selection Sort: