🔟 Classic Sorting & Searching Algorithms in Python 🐍

 In this blog post, we’ll go through the most important sorting and searching algorithms in Python.

Each section includes:

✅ Intuition
🔄 Step-by-step working (Pass-by-pass)
🧠 Code (as written)
📤 Output

---

1️⃣ Bubble Sort

✅ Intuition:

Repeatedly compare adjacent elements and swap if needed. The largest element "bubbles" to the end after each pass.

🔄 Working (Pass-by-Pass):

Input: [5, 3, 8, 4, 2]

Pass 1:

• 5 > 3 → swap → [3, 5, 8, 4, 2]

• 5 < 8 → no swap

• 8 > 4 → swap → [3, 5, 4, 8, 2]

• 8 > 2 → swap → [3, 5, 4, 2, 8]

Pass 2:

• 3 < 5 → no swap

• 5 > 4 → swap → [3, 4, 5, 2, 8]

• 5 > 2 → swap → [3, 4, 2, 5, 8]

Pass 3:

• 3 < 4 → no swap

• 4 > 2 → swap → [3, 2, 4, 5, 8]

Pass 4:

• 3 > 2 → swap → [2, 3, 4, 5, 8]

🧠 Code:

def bubble_sort(arr):
    n=len(arr)
    for i in range(n):
        swapped=False
        for i in range(0, n-i-1):
            if arr[i]>arr[i+1]:
                arr[i],arr[i+1]=arr[i+1],arr[i]
                swapped=True
                if not swapped:
                    break
arr=[5,3,8,4,2]
bubble_sort(arr)
print("Sorted array: ", arr)

📤 Output:

Sorted array:  [2, 3, 4, 5, 8]

---

2️⃣ Selection Sort

✅ Intuition:

Find the minimum in the unsorted part and place it at the current index.

🔄 Working:

Input: [5, 3, 8, 4, 2]

Pass 1:
Minimum in [5, 3, 8, 4, 2] is 2 → swap with 5 → [2, 3, 8, 4, 5]

Pass 2:
Minimum in [3, 8, 4, 5] is 3 → already in place → [2, 3, 8, 4, 5]

Pass 3:
Minimum in [8, 4, 5] is 4 → swap with 8 → [2, 3, 4, 8, 5]

Pass 4:
Minimum in [8, 5] is 5 → swap → [2, 3, 4, 5, 8]

🧠 Code:

def selection_sort(arr):

    n=len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j]<arr[min_index]:
                min_index=j
        arr[i], arr[min_index]=arr[min_index],arr[i]
arr=[5,3,8,4,2]
selection_sort(arr)
print("Sorted array: ", arr)

📤 Output:

Sorted array:  [2, 3, 4, 5, 8]

---

3️⃣ Insertion Sort

✅ Intuition:

Take each element and insert it into its correct position in the sorted part of the array.

🔄 Working:

Input: [5, 3, 8, 4, 2]

Pass 1: Insert 3 into [5] → [3, 5, 8, 4, 2]

Pass 2: Insert 8 into [3, 5] → [3, 5, 8, 4, 2]

Pass 3: Insert 4 into [3, 5, 8] → [3, 4, 5, 8, 2]

Pass 4: Insert 2 into [3, 4, 5, 8] → [2, 3, 4, 5, 8]

🧠 Code:

def insertion_sort(arr):
    n=len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
arr=[5,3,8,4,2]
insertion_sort(arr)
print("Sorted array: ", arr)

📤 Output:

Sorted array:  [2, 3, 4, 5, 8]

4️⃣ Merge Sort

✅ Intuition:

Divide array into halves, sort recursively, and merge them.

🔄 Working (Overview):

Split: [5, 3, 8, 4, 2]
→ [5, 3] and [8, 4, 2]
→ Merge [3, 5] and [2, 4, 8] → Final: [2, 3, 4, 5, 8]

🧠 Code:

def merge_sort(arr):

    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
arr = [5, 3, 8, 4, 2]
merge_sort(arr)
print("Sorted array: ", arr)

📤 Output:

Sorted array:  [2, 3, 4, 5, 8]

---

5️⃣ Quick Sort

✅ Intuition:

Pick a pivot. Partition the array into <pivot, =pivot, >pivot. Recursively sort.

🔄 Working:

Pivot = 8 → Left: [5, 3, 4, 2], Middle: [8], Right: []
Pivot = 4 → Left: [3, 2], Middle: [4], Right: [5]
Final: [2, 3, 4, 5, 8]

🧠 Code:

def quick_sort(arr):

    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
arr = [5, 3, 8, 4, 2]
sorted_arr = quick_sort(arr)
print("Sorted array: ", sorted_arr)

📤 Output:

Sorted array:  [2, 3, 4, 5, 8]

---

6️⃣ Bubble Search (Linear Search)

✅ Intuition:

Scan each element one-by-one and return index if matched.

🔄 Working:

Search 4 in [5, 3, 8, 4, 2]
Found at index 3.

🧠 Code:

def bubble_search(arr, target):
    n = len(arr)
    for i in range(n):
        if arr[i] == target:
            return i
    return -1
arr = [5, 3, 8, 4, 2]
target = 4
result = bubble_search(arr, target)
if result != -1:
    print("Element found at index:", result)
else:
    print("Element not found")

📤 Output:

Element found at index: 3

---

7️⃣ First and Last Occurrence

✅ Intuition:

Scan array and track first and last positions of target.

🔄 Working:

Search 4 in [2, 3, 4, 4, 4, 5, 8]
First = 2, Last = 4

🧠 Code:

def find_first_and_last(arr, target):
    first = last = -1
    for i in range(len(arr)):
        if arr[i] == target:
            if first == -1:
                first = i
            last = i
    return (first, last)
arr = [2, 3, 4, 4, 4, 5, 8]
target = 4
first, last = find_first_and_last(arr, target)
print("First occurrence:", first)
print("Last occurrence:", last)

📤 Output:

First occurrence: 2
Last occurrence: 4

---

8️⃣ Kth Smallest Element

✅ Intuition:

Sort and return element at (k-1) index.

🔄 Working:

Sort → [2, 3, 4, 5, 8]
3rd smallest = 4

🧠 Code:

def kth_smallest(arr, k):
    if k < 1 or k > len(arr):
        return None
    arr.sort()
    return arr[k-1]
arr = [5, 3, 8, 4, 2]
k = 3   
result = kth_smallest(arr, k)
print("The", k, "th smallest element is:", result)

📤 Output:

The 3 th smallest element is: 4

---

9️⃣ Dutch National Flag (0s, 1s, 2s)

✅ Intuition:

Sort 0s, 1s, and 2s in-place using 3 pointers.

🔄 Working:

Input: [0, 1, 2, 0, 1, 2, 0]
Final: [0, 0, 0, 1, 1, 2, 2]

🧠 Code:

def dutch_national_flag(arr):
    low = 0
    mid = 0
    high = len(arr) - 1
    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1
        elif arr[mid] == 1:
            mid += 1
        else:
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1
    return arr
arr = [0, 1, 2, 0, 1, 2, 0]
sorted_arr = dutch_national_flag(arr)
print("Sorted array: ", sorted_arr)

📤 Output:

Sorted array:  [0, 0, 0, 1, 1, 2, 2]

---

🔟 Find Missing Number

✅ Intuition:

Use sum formula n(n+1)/2 and subtract from actual sum.

🔄 Working:

Input: [1, 2, 4, 5, 6]
Expected sum (1–6) = 21
Actual sum = 18
Missing = 21 - 18 = 3

🧠 Code:

def find_missing_number(arr):   
    n = len(arr)
    expected_sum = (n + 1) * (n + 2) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum
arr = [1, 2, 4, 5, 6]
missing_number = find_missing_number(arr)
print("Missing number is:", missing_number)

📤 Output:

Missing number is: 3

---

🎯 Conclusion
Each of these algorithms teaches you something fundamental about problem solving and time-space complexity. Practice understanding their step-by-step process, and you'll build a solid foundation for interviews and real-world coding.