الفرز والبحث
Finding Things Fast
When you search Google, results appear in under a second - ranked from most to least relevant. When Netflix recommends films, it sorts thousands of titles by how likely you are to enjoy them. Behind every fast lookup and every ranked list sits a sorting or searching algorithm.
Why Sorting Matters
Sorted data is powerful data. Once a list is in order, you can:
- Search it efficiently using binary search (we'll get to this shortly).
- Find duplicates - they'll be sitting right next to each other.
- Identify the top-N results - just grab the first N items.
- Merge datasets - combining two sorted lists is much faster than combining unsorted ones.
Bubble Sort - Simple but Slow
Bubble sort repeatedly steps through the list, comparing adjacent items and swapping them if they're in the wrong order. Larger values "bubble" to the end.
[5, 3, 8, 1, 2]
↕
[3, 5, 8, 1, 2] → swapped 5 and 3
[3, 5, 1, 8, 2] → swapped 8 and 1
[3, 5, 1, 2, 8] → swapped 8 and 2
... keep going until no swaps needed
Time complexity: O(n²) - for each of n items, you might compare against every other item. With 1,000 items, that's up to 1,000,000 comparisons. With 1,000,000 items? A trillion comparisons. Not practical for AI workloads.
If bubble sort takes roughly n² comparisons, how much slower would it be to sort a million items compared to a thousand? Think about the ratio: (1,000,000)² vs (1,000)². That's a million times slower - just for having a thousand times more data.
Merge Sort - Divide and Conquer
Merge sort takes a cleverer approach: split the list in half, sort each half, then merge the two sorted halves together.
[5, 3, 8, 1, 2, 7, 4, 6]
split
[5, 3, 8, 1] [2, 7, 4, 6]
split split
[5, 3] [8, 1] [2, 7] [4, 6]
↓ ↓ ↓ ↓
[3, 5] [1, 8] [2, 7] [4, 6]
merge merge
[1, 3, 5, 8] [2, 4, 6, 7]
merge
[1, 2, 3, 4, 5, 6, 7, 8]
Time complexity: O(n log n) - dramatically faster. For a million items, that's about 20 million comparisons instead of a trillion. This is the kind of algorithm that makes real AI systems possible.
Discussion
Sign in to join the discussion