Chapter 2: Algorithms & Logic - Sorting and Search

Program performance varies significantly depending on how data is sorted and searched. Modern search engines and recommendation systems are built upon advanced sorting and search algorithms.

1. Data Sorting

Sorting is the process of arranging data according to a specific criterion (ascending or descending order).

Key Principle: Divide & Conquer

This approach involves breaking down a complex problem into smaller, manageable sub-problems. Quick Sort and Merge Sort use this principle to achieve efficient speeds of $O(n \log n)$.

2. Data Search

Search is the process of finding specific data within a collection.

(1) Linear Search

Compares each element one by one from the beginning.

• Features: Can be used even if data is not sorted.
• Performance: $O(n)$ (Time increases proportionally with data size).

(2) Binary Search

Reduces the search range by half repeatedly based on the ==midpoint== of sorted data.

• Features: Data MUST be sorted.
• Performance: $O(\log n)$ (Can find data among 1 million items in just 20 comparisons).

3. Why Algorithm Efficiency Matters

When data increases 1,000 times, an $O(n)$ algorithm becomes 1,000 times slower, but an $O(n^2)$ algorithm becomes 1,000,000 times slower. Choosing an algorithm is not just a coding technique but a critical design element that determines the “limits” of a system.

Key Checklist

• Which sorting method divides and sorts data based on a ‘Pivot’ value? (Answer: Quick Sort)
• What is the search method that repeatedly halves the search range by checking the midpoint of sorted data? (Answer: Binary Search)
• What is the time complexity of Binary Search for $n$ data items? (Answer: $O(\log n)$)