I'm in college right now and I've been wondering...do professional programmers actually think about sorting algorithms on a day-to-day basis? How relevant is this knowledge when it comes to actually making something?
That said, most of the reason we teach sorting algorithms is to teach algorithms in general, and particularly the consequential lesson that "There are often many methods to doing something that work; these methods are often different in extraordinarily consequential ways; the right method for certain problems -- even ones which look trivial on the outside! --may require literally years of R&D to develop."
In that type of environment, you need to do a lot of thinking about basic algorithm science, including exploring the many types of sorting algos.
(Here's some code I'm working on right now in that vein, which helps to perform efficient percentile calculations in a smart contract https://github.com/drcode/ethereum-order-statistic-tree)
For instance, adding an index to a database table is something I regularly do for performance, and the reason is based on principles I learned in college. The runtime complexity of an indexed table is way better. Any monkey coder can add the index too, the difference is that I know what's going on under the hood (finding things in a ordered tree data structure are way faster than scanning through the whole table).
I was grumpy learning some things in college early on, and the more I advance my career, the more I appreciate the things I learned even if I don't code them up, or even use them, on a regular basis.
I'm not sure if I've ever run into anyone who said "The things I learned in college have turned out to be pretty much worthless in my professional career. I wasted a lot of time learning irrelevant information." It's interesting that the majority of every CS education is always valuable, to every person, with no exceptions.
OTOH, I'm not sure full coursework is needed for that. Just make your way through Sedgwick's algorithms book in a month or two and you're in the top 1% probably.
For straight up sorting, yes.
But, some other algorithms have exactly the same structure as sorting.
As a toy example, take the famous skyline problem. See https://briangordon.github.io/2014/08/the-skyline-problem.ht... for the details:
"You are given a set of n rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the x position of the left edge, the x position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night."
One approach to solving the problem is equivalent to merge sort: you write a merge function that merges two lists of in-order non-overlapping rectangles, and go from there.
A related problem (not the same problem, but amenable to the same sort of approaches), for example, comes up when displaying overlapping appointments in a calendar timeline view.
Not many out of the box libraries would have find N min out of a stream/iterator...draw the moving median, moving min/max and so on. You won't find a red/black tree with linked next nodes to do the task efficiently. So sometimes there is that.
When you study sorting you really do it because:
1) It's a simple, frequent and clear problem that everybody understands
2) People just need to think about it for a while to figure out a correct algorithm normally O(n^2) and think about optimizations from there (that will probably still make it O(n^2)).
3) You can study different techniques to solve that problem: like divide-and-conquer (mergesort), using a data structure (heapsort), divide-and-conquer+randomization (quicksort), not going for comparisons but using the structure of the data (radixsort).
4) You can learn to apply big-O notation for efficiency and compare different algorithms
5) You can study the limits of a problem (not an algorithm) like the omega(n log(n)) limit of comparison sorts and the omega(n) limit of sorting in general).
This also happens with the less clear but also rich problem of the Minimum Spanning Tree that has 2 famous algorithm (Prim and Kruskal) that can be implemented with different data structures having a great impact in efficiency.
So the real problem is that sometimes teachers just focus on teaching sorting but don't explain (and sometimes they don't have it clear either) that it's not sorting but a framework of mind what you want to give them. Sorting is normally already implemented in the popular and not so popular programming languages libraries.
What I suspect generally that I cannot prove (yet): When teachers teach things that are easy to teach but not directly important to learn, students are distracted by the surface irrelevance.
Of course the underlying concepts and designs of sorting are important to understand. But, that the GP asked, "Do professional programmers actually think about this? Is this relevant?" means the curriculum has a problem. The problem is: students are asking meta-questions that should've been answered by the "why?" mentioned above.
In sum, I agree with the parent, especially with:
> So the real problem is that sometimes teachers just focus on teaching sorting but don't explain (and sometimes they don't have it clear either) that it's not sorting but a framework of mind what you want to give them.
It's easy (possibly... lazy? Again, this is what I suspect that I cannot prove) for a CS department to declare "Students will learn [list of topics] by examining and implementing sorting algorithms."
By contrast, it's a hard to 1. interest students by presenting them with problems not fossilized exercises. 2. ensure to students' parents and taxpayers and employers that they know the "basics|fundamentals|theory"
So, in this case, programmers would use this stuff when a sort takes up too much time or too much RAM for what it's meant to do. Then you need to know what big-O is and how to fix it.
It seems a bit odd to spend all this time preparing for things that don't happen every day, but, really, that's what people pay the big bucks for: Someone who can smooth over life's little difficulties, at least in that specific realm.
http://www.joelonsoftware.com/articles/fog0000000319.html
Someone who hasn't thought about sorting algorithms is likely to implement a "Shlemiel the painter" solution without even realizing that their problem is fundamentally sorting related.
Software engineers (like engineers in other fields) are in the business of taking stuff made by scientists and building things out of it that businesses and consumers use (like spotify and bridges and dialysis machines). They wouldn't do much in the realm of specific algorithm design, it's mostly about research and system architecture.
I had always believed that I wouldn't need to know the CS theory because I was able to write code that worked and didn't find it too complicated. When I decided to become a developer I learned by launching a few websites, which performed horribly, but I didn't realize until I got a few users. It took me a while to even figure out what was wrong, but eventually I learned about Big-O and realized my algorithms were far from optimal. Started scrambling to teach myself all CS theory I could find online, just so I could build things properly. Then there is a phase where you are constantly worried there is something else from CS school you are missing which will cause your software to blow up, but eventually you get more confident (with shipped code/and a better understanding of CS theory).
So in the end, I think the CS theory in school saves you from a lot of head banging and ignorance after you graduate. However, you will probably do a lot of this in your undergrad, so I guess it all balances out in the end!
For example, I remember one developer (who know works at Amazon funny enough), who used dual for loops to iterate through data and find values in multiple places in our application. This caused a noticeable UI slow down. I ended up just loading this data in a Hashmap and it became instantaneous.
It then becomes a game of ensuring adequate access paths and the like and using a query analyzer to see if what you put in executes as you like. I am more than amazed at the tricks a good query engine can pull but readily take advice it offers when a new index/access path is required.
Since this covers the sorting the next issue is, making sure the project requests are asking for the right data. A lot of time we gain efficiency by analyzing what they want and making their request better fit that (see Bob, you really didn't need that million record request when all you wanted were this set here)
Skiena's Algorithm Design Manual is great for the former approach, and has a cookbook feel to it, since most of it is just an index of different algorithms to use for different situations.
Generally speaking though, I do think about Big-O notation when writing something that isn't trivial. If I do have to implement some particular known algorithm, then I typically look to the language itself for a solution. Failing that I look for a suitable library, and only after exhausting those potential solutions do I write my own.
The same goes for data-structures. For example, I might need a set of unique values, but, when I code, I would choose an enum-set or a hash-set based on what problem I'm solving.
Graph algorithms, and linear algebra complexities, on the other hand, I've had to worry about a bunch.