Sorting Algorithms (Bubble, Selection, Merge, Quick)

Sorting is a fundamental operation in computer science with numerous applications in data processing, analysis, and more. In this tutorial, we will explore several popular sorting algorithms implemented in Python, including bubble sort, selection sort, insertion sort, merge sort, quick sort, counting sort, and radix sort. We'll also delve into their time and space complexities to understand the trade-offs involved.

Introduction

Sorting refers to arranging a collection of items (e.g., numbers or strings) in a specific order, either ascending or descending. Efficient sorting is crucial for optimizing performance in applications that require frequent data retrieval and manipulation. Python provides built-in sorting functions like sorted() and .sort(), but understanding the underlying algorithms helps you make informed decisions about when to use each method.

Bubble Sort

Bubble sort is a simple comparison-based algorithm where adjacent elements are compared and swapped if they are in the wrong order. This process is repeated until the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top of the list.

Implementation

1def bubble_sort(arr):
2  n = len(arr)
3  for i in range(n):
4      # Track if any swap happens
5      swapped = False
6      for j in range(0, n-i-1):
7          if arr[j] > arr[j+1]:
8              arr[j], arr[j+1] = arr[j+1], arr[j]
9              swapped = True
10      # If no two elements were swapped by inner loop, then break
11      if not swapped:
12          break
13  return arr
14 
15# Example usage
16arr = [64, 34, 25, 12, 22, 11, 90]
17sorted_arr = bubble_sort(arr)
18print(sorted_arr)

Time and Space Complexity

• Time Complexity:

  • Best Case: \(O(n^2)\)
  • Average Case: \(O(n^2)\)
  • Worst Case: \(O(n^2)\)

• Space Complexity: \(O(1)\) (in-place sorting)

Insertion Sort

Insertion sort builds the final sorted array one item at a time. It takes each element from the input data and finds the location it belongs within the already sorted part of the list, inserting it there.

Implementation

1def insertion_sort(arr):
2  n = len(arr)
3  for i in range(1, n):
4      key = arr[i]
5      j = i-1
6      # Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
7      while j >= 0 and key < arr[j]:
8          arr[j+1] = arr[j]
9          j -= 1
10      arr[j+1] = key
11  return arr
12 
13# Example usage
14arr = [12, 11, 13, 5, 6]
15sorted_arr = insertion_sort(arr)
16print(sorted_arr)

Time and Space Complexity

• Time Complexity:

  • Best Case: \(O(n \log n)\)
  • Average Case: \(O(n \log n)\)
  • Worst Case: \(O(n \log n)\)

• Space Complexity: \(O(n)\) (requires additional space for the temporary arrays)

Quick Sort

Quick sort is another divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Implementation

1def quick_sort(arr):
2  if len(arr) <= 1:
3      return arr
4  else:
5      pivot = arr[len(arr) // 2]
6      left = [x for x in arr if x < pivot]
7      middle = [x for x in arr if x == pivot]
8      right = [x for x in arr if x > pivot]
9      return quick_sort(left) + middle + quick_sort(right)
10 
11# Example usage
12arr = [3, 6, 8, 10, 1, 2, 1]
13sorted_arr = quick_sort(arr)
14print(sorted_arr)

Time and Space Complexity

• Time Complexity:

  • Best Case: \(O(n + k)\)
  • Average Case: \(O(n + k)\)
  • Worst Case: \(O(n + k)\)

• Space Complexity: \(O(k)\) (where k is the range of input values)

Radix Sort

Radix sort sorts numbers by processing individual digits. It starts from the least significant digit and moves towards the most significant digit, using a stable sub-sorting algorithm (like counting sort) to sort each digit.

Implementation

1def counting_sort_for_radix(arr, exp):
2  n = len(arr)
3  output = [0] * n
4  count = [0] * 10
5 
6  # Store count of occurrences in count[]
7  for i in range(n):
8      index = (arr[i] // exp) % 10
9      count[index] += 1
10 
11  # Change count[i] so that it contains the actual position of this digit in output[]
12  for i in range(1, 10):
13      count[i] += count[i-1]
14 
15  # Build the output array
16  i = n - 1
17  while i >= 0:
18      index = (arr[i] // exp) % 10
19      output[count[index] - 1] = arr[i]
20      count[index] -= 1
21      i -= 1
22 
23  # Copy the output array to arr[], so that arr now contains sorted numbers
24  for i in range(n):
25      arr[i] = output[i]
26 
27def radix_sort(arr):
28  # Find the maximum number to know the number of digits
29  max_val = max(arr)
30 
31  # Do counting sort for every digit. Note that instead of passing digit number, exp is passed.
32  # exp is 10^i where i is current digit number
33  exp = 1
34  while max_val // exp > 0:
35      counting_sort_for_radix(arr, exp)
36      exp *= 10
37  return arr
38 
39# Example usage
40arr = [170, 45, 75, 90, 802, 24, 2, 66]
41sorted_arr = radix_sort(arr)
42print(sorted_arr)

Summary

What's Next?

In the next topic, we will explore searching algorithms, including linear search and binary search. These algorithms are essential for efficiently finding elements within a dataset. Understanding both sorting and searching algorithms is crucial for optimizing data processing tasks in various applications.

Stay tuned for more tutorials on advanced topics in computer science!