Day 21: Different Types of Sorting Algorithms in Python

Sorting is a fundamental concept in programming, and python supports multiple sorting techniques. Today, let's explore different sorting algorithms and their implementations!

1?? Bubble Sort (Brute Force)

• Compares adjacent elements and swaps them if needed
• Time Complexity: O(n2) (Not efficient for large datasets)

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]:
                arr[j],arr[j+1] = arr[j+1],arr[j]
    return arr
print(bubble_sort([64, 35, 27, 10, 21, 22, 90])        

? Simple but inefficient for large lists.

2?? Selection Sort

• Finds the minimum element and places it at the beginning
• Time Complexity: O(n2).

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]
    return arr
print(selection_sort([64, 35, 27, 10, 21, 22, 90]))        

? Better than Bubble Sort, but still O(n2).

3?? Insertion Sort

• Builds the sorted array one item at a time
• Time Complexity: O(n2), but efficient for small datasets.

def insertion_sort(arr):
    for i in range(1,len(arr)):
        key = arr[i]
        j=i-1
        while j>=0 and key < arr[j]:
            arr[j+1] = arr[j]
            j-=1
         arr[j+1] = key
      return arr
print(insertion_sort([64, 35, 27, 10, 21, 22, 90]))        

? Good for nearly sorted data.

4?? Merge Sort (Divide and Conquer)

• Recursively divides the list into halves and merges them
• Time Complexity: O(n log n)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

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

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

    return arr

print(merge_sort([64, 35, 27, 10, 21, 22, 90]))        

? Great for large datasets. Uses O(n) extra space.

5?? Quick Sort (Divide and Conquer)

• Picks a pivot, partitions the array, and sorts recursively
• Time Complexity: O(n log n) (Worst case: O(n2) if poorly implemented)

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)

print(quick_sort([64, 35, 27, 10, 21, 22, 90]))        

? Faster than Merge Sort in practice. In-place sorting.

6?? Heap Sort

• It uses a binary heap for sorting
• Time Complexity: O(n log n)

import heapq

def heap_sort(arr):
   heapq.heapify(arr)
   return [heapq.heappop(arr) for _ in range(len(arr))]

print(heap_sort([64, 35, 27, 10, 21, 22, 90]))        

? Efficient for priority queues

?? Which Sorting Algorithm Should You Use?

? For small datasets → Insertion Sort

? For large datasets → Merge Sort / Quick Sort

? For priority queues → Heap Sort

Which sorting algorithm is your favorite? Let me know in the comments! ????

#Python #SortingAlgorithms #100DaysOfCode