Bubble Sort Algorithm

Bubble Sort Algorithm

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.

How Bubble Sort Works

1. Start at the beginning of the list.
2. Compare the first element with the second element.
3. If the first element is greater than the second, swap them.
4. Move to the next pair of elements and repeat the process until the end of the list is reached.
5. Repeat the entire process for the remaining elements until the list is sorted.

Each pass the biggest number will bubble to the top of the list

Pseudocode

Here is the pseudocode for a bubble sort algorithm:

BEGIN
    INPUT list
    SET n = length(list)
    REPEAT
        SET swapped = False
        FOR i = 1 to n-1
            IF list[i-1] > list[i] THEN
                SWAP list[i-1] and list[i]
                SET swapped = True
            ENDIF
        ENDFOR
        SET n = n - 1
    UNTIL swapped = False
END

Example in Python

Below is an example implementation of bubble sort in Python:

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
                swapped = True
        if not swapped:
            break

# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(numbers)
print("Sorted list is:", numbers)

Key Points

Use Cases: Suitable for small datasets or nearly sorted datasets.

Advantages

• Simple to understand and implement.
• Does not require additional memory (in-place sorting).

Disadvantages

• Inefficient for large datasets.
• Performs poorly compared to more advanced algorithms like quicksort or mergesort.

• Time Complexity: O(n^2), where n is the number of elements in the list.
• Space Complexity: O(1), as it uses a constant amount of extra space.