Why do we study Sorting and Searching in Computer Science?
When studying data structure and algorithms, this took me a couple of years to understand but finally, I have figured it out. It is the aha moment if you figure it out.
Algorithms are part of the title (DSA) and usually include the most fundamental algorithms such as quick sort, merge sort, bubble sort, binary search, etc. I have often wondered why we study these concepts sort and search and the reason is very amusing and makes everything clear in the world of data structures and algorithms. This article tries to bring clarity to why we study fundamental algorithms and their application. Once you figure this part out some of the grey areas of DSA will be figured out.
Sorting lies at the heart of many algorithms, sorting data is one of the first things any algorithm designer should try in the quest for efficiency.
Sorting behaves more like a data structure than an algorithm and we then look into fundamental algorithms like heapsort, merge sort quick sort, and distribution sort.
The reason we study sorting and searching
- sorting is the basic building block that many other algorithms are built around, by understanding sorting, we obtain the amount of power to solve other problems.
- most ideas used in the design of algo appear in the context of sorting, such as divide and conquer data structures, and randomized algorithms
- computers have spent more time sorting than anything.
- sorting is combinatorial in practice
- sorting is the most thoroughly studied problem in computer science.
Application of Sorting
An import algorithm design technique is to use sorting as a basic building block because many other problems become easy once a set of items is sorted.
consider the following application
- Searching — Binary search tests whether an item is in a dictionary in O(log n) time, provided the keys are all sorted, Search preprocessing is perhaps the single most important application of sorting.
- Closest pair — given a set of n numbers, how do you find the pair of numbers that has the smallest difference between them, once the numbers are sorted the closest pair of numbers must lie next to each other somewhere in a sorted order.
- Element uniqueness — are there any duplicates in a given set of n items, now we can check adjacent pairs
- frequency distribution- we can easily find the middle number or lowest if the data is sorted
- selections — if the items are sorted and we are asked to find the kth largest element in the array we can do so in constant time or the median
- convex hulls — once you have x coordinates sorted the points can be inserted from the left to right into the hull, the total time is linear after the sorting has been done.
New to trading? Try crypto trading bots or copy trading