Bubble Sort with lists

• Simple sorting algorithm.
• Each pair of adjacent elements is compared and the elements are swapped if they are not in order.
• Inefficient for large datasets due to its O(n^2) time complexity.

#bubblesort.py

def bubble_sort(arr):
    n = len(arr)
    
    # Traverse through all elements in the list
    for i in range(n):
        ''' 
        Last i elements are already in place, so we decrease the range
        outer loop:
        iterates over the entire list. After each complete iteration of the outer loop, 
        the largest element among the unsorted elements gets placed at the correct position.
        '''
        for j in range(0, n-i-1):
            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                # compares each pair of adjacent elements.
                arr[j], arr[j+1] = arr[j+1], arr[j]
                # swaps the elements if they are in the wrong order.

# Example:
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Original array:", arr)

# OR
print("Sorted array:")
for i in range(len(arr)):
    print("%d" % arr[i])

Steps

1. define a function bubble_sort that takes an input list arr.
2. n = len(arr) calculates the length of the list.
3. The outer loop for i in range(n) iterates through each element of the list.
4. The inner loop for j in range(0, n-i-1) performs pairwise comparisons and swaps adjacent elements if they are in the wrong order.
5. After iterating through the entire list, the sorted array arr is printed out.

• sort the elements directly using their values.

Step 1. Initialization

• The algorithm starts at the beginning of the list and iterates through the list multiple times.

Step 2. Comparison and Swap

• For each pair of adjacent elements, compare them.
• If the element on the left is greater than the element on the right, swap them.

Step 3. Iterate through the List

• Continue this process for each element in the list.
• After each full pass through the list, the largest element gets “bubbled” to the correct position.

Step 4. Repeat

• Repeat the process for the remaining unsorted part of the list.
• Each pass through the list ensures that the next largest element is placed in its correct position.

Step 5. Optimization

• If during a pass, no swaps are made, the list is already sorted, and the algorithm can terminate early.

---

testing the code

Assertions: Inside each test function, we use assert statements to check if the actual result matches the expected result.

import pytest

def bubble_sort(arr):
    n = len(arr)
    
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # compares each pair of adjacent elements.
                arr[j], arr[j+1] = arr[j+1], arr[j]
                # swaps the elements if they are in the wrong order.

# Test cases
def test_bubble_sort_empty():
    arr = []
    bubble_sort(arr)
    assert arr == []

def test_bubble_sort_sorted():
    arr = [1, 2, 3, 4, 5]
    bubble_sort(arr)
    assert arr == [1, 2, 3, 4, 5]

def test_bubble_sort_unsorted():
    arr = [64, 34, 25, 12, 22, 11, 90]
    bubble_sort(arr)
    assert arr == [11, 12, 22, 25, 34, 64, 90]

def test_bubble_sort_duplicates():
    arr = [5, 5, 5, 5, 5]
    bubble_sort(arr)
    assert arr == [5, 5, 5, 5, 5]

• test_bubble_sort_empty tests the sorting of an empty list.
• test_bubble_sort_sorted tests the sorting of an already sorted list.
• test_bubble_sort_unsorted tests the sorting of a standard unsorted list.
• test_bubble_sort_duplicates tests the sorting of a list containing duplicates.
• To run the tests pytest bubblesort.py

Bubble Sort with lists #2

def bubblesort(list):

# Swap the elements to arrange in order
   for iter_num in range(len(list)-1,0,-1):
    # Outer Loop 
      for idx in range(iter_num):
         if list[idx]>list[idx+1]:
            temp = list[idx]
            list[idx] = list[idx+1]
            list[idx+1] = temp
list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

Step1. Outer Loop (for iter_num in range(len(list)-1,0,-1)

• len(list)-1: This calculates the last index of the list. The loop starts from this index.
• 0: This is the final value the loop will reach (we’ll stop at the first element).
• -1: This is the step size, indicating that the loop will iterate backward, decrementing the index by 1 in each iteration.

Explanation:

• This outer loop controls the number of passes the algorithm will make. In each pass, the largest element in the unsorted portion of the list “bubbles” up to its correct position.

Step2. Inner Loop (for idx in range(iter_num): iter_num: The current index in the outer loop. range(iter_num): This creates a range from 0 to the iter_num value (exclusive), effectively looping through elements in the current unsorted portion of the list.

Explanation:

• This inner loop compares adjacent elements and swaps them if they are in the wrong order. The process of comparing and swapping repeats until the end of the unsorted portion is reached.

Step3. Comparison and Swapping if list[idx]>list[idx+1] list[idx] and list[idx+1]:

• These access the elements at the current index (idx) and the next index (idx+1) within the list. if list[idx]>list[idx+1]:
• This condition checks if the element at idx is greater than the element at idx+1. If true, it means the elements are in the wrong order.

Step4. Swapping Elements (temp = …) temp = list[idx]:

• A temporary variable temp is used to store the value of the element at idx. list[idx] = list[idx+1]:
• The element at idx+1 is assigned to the position of idx. list[idx+1] = temp:
• The value that was initially at idx (stored in temp) is assigned to the position of idx+1.

How the Code Works (Step-by-Step):
list [19, 2, 31, 45, 6, 11, 121, 27]
  
Pass 1:
Compare: 19 and 2, swap (2, 19, 31, 45, 6, 11, 121, 27)
Compare: 19 and 31, no swap (2, 19, 31, 45, 6, 11, 121, 27)
Compare: 31 and 45, no swap (2, 19, 31, 45, 6, 11, 121, 27)
Compare: 45 and 6, swap (2, 19, 31, 6, 45, 11, 121, 27)
Compare: 45 and 11, swap (2, 19, 31, 6, 11, 45, 121, 27)
Compare: 45 and 121, no swap (2, 19, 31, 6, 11, 45, 121, 27)
Compare: 121 and 27, swap (2, 19, 31, 6, 11, 45, 27, 121)
Pass 2:
Compare: 19 and 2, swap (2, 19, 31, 6, 11, 45, 27, 121)
Compare: 19 and 31, no swap (2, 19, 31, 6, 11, 45, 27, 121)
Compare: 31 and 6, swap (2, 19, 6, 31, 11, 45, 27, 121)
Compare: 31 and 11, swap (2, 19, 6, 11, 31, 45, 27, 121)
Compare: 31 and 45, no swap (2, 19, 6, 11, 31, 45, 27, 121)
Compare: 45 and 27, swap (2, 19, 6, 11, 31, 27, 45, 121)
Pass 3:
Compare: 19 and 2, swap (2, 19, 6, 11, 31, 27, 45, 121)
Compare: 19 and 6, swap (2, 6, 19, 11, 31, 27, 45, 121)
Compare: 19 and 11, swap (2, 6, 11, 19, 31, 27, 45, 121)
Compare: 19 and 31, no swap (2, 6, 11, 19, 31, 27, 45, 121)
Compare: 31 and 27, swap (2, 6, 11, 19, 27, 31, 45, 121)
Pass 4,5,6 and done