Classic Algorithms - Sorting

Classic Algorithms - Sorting Overview

• Introduction to Sorting Algorithms
  • Sorting algorithms are essential in computer science with applications in various domains such as:
  • Computer games
  • Network routing software
  • Artificial Intelligence
  • Operating systems
  • Bin packing algorithms
• Importance of Sorting
  • Sorting simplifies the process of searching, finding min/max values, counting duplicates, and more.
  • Essential for effective data management.

Definition of Sorting

• Formal Definition: Sorting is reordering elements of an array.
  • Let x be an input array of length n:
  • y is a permutation of x, satisfying $yi < y{i+1}$ for all $i = 0, …, n-1$.
• Examples of sortable items include:
  • Integers
  • Character vectors
  • Names and addresses

Sorting Algorithms Covered

1. Bubble Sort
2. Quick Sort
3. Radix Sort
4. Brief discussion on other sorting algorithms

Detailed Look into Bubble Sort

• Description:

  • Simple sorting algorithm that works by repeatedly comparing adjacent items and swapping them if they are in the wrong order.
  • Continues until no swaps are needed, indicating that the list is sorted.

• Best-Case Complexity:

  • O(n) when the array is already sorted.
  • Only requires comparisons with no swaps.

• Worst-Case Complexity:

  • O(n^2) when the array is sorted in reverse order, leading to maximum swaps.

• Steps (Algorithm):

  • Initialize NoSwaps to False
  • While NoSwaps is False:
  1. Set NoSwaps = True
  2. For i = 0 to n-2:
     • Compare $xi$ and $x{i+1}$: swap if $xi > x{i+1}$.
     • Set NoSwaps = False if a swap occurs.
  • Output sorted list.

Quick Sort

• Nature: Divide and conquer algorithm.

• Process:

  • Select a pivot element.
  • Partition the array into elements less than and greater than the pivot.
  • Recursively apply Quick Sort on the partitions.

• Complexities:

  • Best/Average: O(n log n)
  • Worst: O(n^2) with poor pivot selection.

Radix Sort

• Description: Non-comparison based sorting method, suitable for integers and strings.
• Procedure:
  • Start with the least significant digit, sort the data into buckets.
  • Repeat for every digit.
• Complexity: O(nb), where n is the number of elements and b is the number of bits.

Summary of Sorting Algorithm Complexities

• Comparison of Algorithms:
  

• Used in various real-world systems for efficient data management and retrieval:
  • Faster search operations
  • Organizing records
  • Optimizing databases

Next Steps

• Upcoming topics will focus on classic graph-based algorithms.
• There will be no lectures during the reading week.
• Planned laboratory sessions for testing the sorting algorithms discussed.