A Simple Algorithm

Welcome to TheCodingCollege.com! In this article, we’ll explore a simple yet fundamental algorithm: Bubble Sort. It’s one of the easiest sorting algorithms to understand and a great starting point for learning about algorithms.

What is an Algorithm?

An algorithm is a step-by-step procedure for solving a problem or performing a task. It defines the logic behind how a problem is approached and solved in a systematic way.

Key Characteristics of an Algorithm:

  1. Input: Takes one or more inputs.
  2. Output: Produces the desired result.
  3. Finite Steps: Completes in a limited number of steps.
  4. Well-Defined: Each step is clear and unambiguous.

Bubble Sort Algorithm: A Simple Example

What is Bubble Sort?

Bubble Sort is a sorting algorithm that compares adjacent elements and swaps them if they are in the wrong order. It “bubbles” the largest (or smallest) element to the correct position in each iteration.

Steps of the Bubble Sort Algorithm:

  1. Start with an unsorted array.
  2. Compare each pair of adjacent elements.
  3. Swap them if the first element is larger than the second.
  4. Repeat the process for all elements, excluding the last sorted ones in each iteration.
  5. Stop when no swaps are needed, indicating the array is sorted.

Bubble Sort in Action

Example: Sorting the array [5, 3, 8, 6, 2] in ascending order.

Pass 1:

  • Compare 5 and 3 → Swap → [3, 5, 8, 6, 2]
  • Compare 5 and 8 → No swap → [3, 5, 8, 6, 2]
  • Compare 8 and 6 → Swap → [3, 5, 6, 8, 2]
  • Compare 8 and 2 → Swap → [3, 5, 6, 2, 8]

Pass 2:

  • Compare 3 and 5 → No swap → [3, 5, 6, 2, 8]
  • Compare 5 and 6 → No swap → [3, 5, 6, 2, 8]
  • Compare 6 and 2 → Swap → [3, 5, 2, 6, 8]
  • Compare 6 and 8 → No swap → [3, 5, 2, 6, 8]

Pass 3:

  • Compare 3 and 5 → No swap → [3, 5, 2, 6, 8]
  • Compare 5 and 2 → Swap → [3, 2, 5, 6, 8]
  • Compare 5 and 6 → No swap → [3, 2, 5, 6, 8]

Pass 4:

  • Compare 3 and 2 → Swap → [2, 3, 5, 6, 8]

Array is now sorted.

Bubble Sort Code Implementation

Here’s a simple implementation of Bubble Sort in Python:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # Last i elements are already sorted
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # Swap if elements are in the wrong order
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

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

Output:

Sorted Array: [2, 3, 5, 6, 8]

Why Learn Bubble Sort?

  • Easy to Understand: Ideal for beginners starting with algorithms.
  • Foundation for Advanced Sorting: Builds the basis for understanding more complex algorithms.
  • Practical for Small Data Sets: Though not efficient for large datasets, it’s useful for teaching.

Time Complexity of Bubble Sort

  • Best Case: O(n)O(n) (when the array is already sorted).
  • Worst Case: O(n2)O(n^2) (when the array is sorted in reverse order).
  • Space Complexity: O(1)O(1) (in-place sorting).

Conclusion

Bubble Sort is a simple algorithm that lays the foundation for understanding more complex sorting techniques. While it’s not the most efficient, mastering it is an essential first step in your DSA journey. Explore more beginner-friendly DSA tutorials and advanced topics at TheCodingCollege.com and level up your coding skills today!

Leave a Comment