Ai-CompTech

AI Computing

Computer Science Fundamentals

Sorting Algorithms

Master efficient algorithms for sorting data

Intermediate 75 min read 0 examples 0 quiz questionsID: 6962f8f9
Lesson Content

Sorting Algorithms

Sorting is organizing data in ascending or descending order. Essential for searching, data analysis, and optimization.

Why Sorting Matters

  • Search Efficiency: Binary search requires sorted data
  • Data Analysis: Find median, percentiles, outliers
  • Optimization: Many algorithms need sorted input
  • User Experience: Display sorted results

Algorithm Comparison

| Algorithm | Best | Average | Worst | Space | Stable | |-----------|------|---------|-------|-------|----|--| | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |

Simple Sorting Algorithms

1. Bubble Sort

How it works: Repeatedly swap adjacent elements if in wrong order.

code
def bubble_sort(arr): n = len(arr) for i in range(n): swapped = False for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if not swapped: # Optimization break return arr # Example arr = [64, 34, 25, 12, 22] print(bubble_sort(arr)) # [12, 22, 25, 34, 64]

Time: O(n²) | Space: O(1) | Stable: Yes Use: Small datasets, nearly sorted data, educational

2. Selection Sort

How it works: Find minimum element, swap with first position, repeat.

code
def selection_sort(arr): n = len(arr) for i in range(n): min_idx = i for j in range(i+1, n): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr

Time: O(n²) | Space: O(1) | Stable: No Use: Small datasets, memory limited

3. Insertion Sort

How it works: Build sorted array one element at a time.

code
def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and arr[j] > key: arr[j+1] = arr[j] j -= 1 arr[j+1] = key return arr

Time: O(n²) average, O(n) best | Space: O(1) | Stable: Yes Use: Small datasets, nearly sorted, online sorting

Efficient Sorting Algorithms

4. Merge Sort

How it works: Divide array, sort halves, merge them.

code
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result

Time: O(n log n) always | Space: O(n) | Stable: Yes Use: Large datasets, linked lists, external sorting

Advantages: ✅ Guaranteed O(n log n) ✅ Stable ✅ Good for linked lists

Disadvantages: ❌ Extra space O(n) ❌ Slower than quicksort in practice

5. Quick Sort

How it works: Pick pivot, partition array, recursively sort.

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) # In-place version def quick_sort_inplace(arr, low, high): if low < high: pi = partition(arr, low, high) quick_sort_inplace(arr, low, pi-1) quick_sort_inplace(arr, pi+1, high) def partition(arr, low, high): pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i+1], arr[high] = arr[high], arr[i+1] return i + 1

Time: O(n log n) average, O(n²) worst | Space: O(log n) | Stable: No Use: General purpose, in-place sorting

Pivot Selection Strategies:

  • First/last element (bad for sorted data)
  • Middle element
  • Random element (good average)
  • Median-of-three (best)

6. Heap Sort

How it works: Build max heap, repeatedly extract maximum.

code
def heap_sort(arr): n = len(arr) # Build max heap for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # Extract elements from heap for i in range(n-1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) return arr def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest)

Time: O(n log n) always | Space: O(1) | Stable: No Use: Memory constrained, guaranteed O(n log n)

Choosing the Right Algorithm

Small data (< 50 elements): Insertion Sort General purpose: Quick Sort Guaranteed O(n log n): Merge Sort or Heap Sort Nearly sorted: Insertion Sort Stable sort needed: Merge Sort Memory limited: Heap Sort or Quick Sort External sorting: Merge Sort

Special Sorting Algorithms

Counting Sort

For integers in limited range.

code
def counting_sort(arr): max_val = max(arr) count = [0] * (max_val + 1) for num in arr: count[num] += 1 result = [] for i, c in enumerate(count): result.extend([i] * c) return result

Time: O(n + k) where k = range | Space: O(k)

Radix Sort

Sort by individual digits.

code
def radix_sort(arr): max_val = max(arr) exp = 1 while max_val // exp > 0: counting_sort_by_digit(arr, exp) exp *= 10 return arr

Time: O(d × n) where d = digits | Space: O(n)

Real-World Applications

  • E-commerce: Sort by price, rating, date
  • Social Media: Sort posts by time, likes
  • Databases: ORDER BY queries
  • Search Engines: Rank results
  • File Systems: Sort files by name, size, date
  • Data Analysis: Find top K elements

Practice Problems

  1. Sort array of 0s, 1s, 2s (Dutch National Flag)
  2. Merge K sorted arrays
  3. Sort array by frequency
  4. Sort colors (3-way partitioning)
  5. Find Kth largest element
  6. Sort linked list
  7. Custom comparator sorting