Naive Selection via Sorting
You'll learn how to solve selection problems by sorting first—a simple but not always optimal approach.
The Core Idea
The selection problem asks you to find the k-th smallest (or largest) element in an unsorted array. The most straightforward solution? Sort the entire array, then simply index into position k-1 (for zero-indexed arrays).
For example, if you want the 3rd smallest element from [7, 2, 9, 1, 5], sort it to get [1, 2, 5, 7, 9], then return array[2] which is 5.
Why It Works
Sorting guarantees that elements are arranged in order. Once sorted, finding the k-th element becomes trivial—it's just a direct array access at index k-1.
Time Complexity Analysis
Since we're using a comparison-based sorting algorithm (like Quicksort, Mergesort, or Heapsort), the time complexity is O(n log n) where n is the array size. The actual selection step after sorting is just O(1).
This means even if you only need one element, you're still paying the cost of ordering all elements.
When It's Acceptable
This approach is perfectly reasonable when:
- You need multiple k-th elements (e.g., median, quartiles)
- The array is already sorted or nearly sorted
- Simplicity matters more than optimal performance
- The dataset is small enough that O(n log n) is negligible
Think of it like organizing an entire deck of cards just to find the 10th card—overkill for a single query, but efficient if you'll be asking "what's the 5th? 20th? 35th?" multiple times.
Key Takeaway: Naive selection via sorting solves the selection problem in O(n log n) time by sorting first then indexing—simple and effective for multiple queries, though better O(n) algorithms exist for single selections.