6 ms·

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 th

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?

patio11 12y ago
Ask a simple question, get a simple answer: no. While there are some programmers who develop libraries, the majority will just consume well-understood sorting algorithms which are baked into their languages/standard libraries/etc of choice. If you find yourself coding mergesort and you are not in a job interview, a nightmare, or a nightmare of a job interview, you are probably doing something wrong. 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."
- aninhumer 12y ago
  Even ones that look trivial on the inside might take years of R&D to develop.
  - throwaway43 12y ago
    Any examples ?
    - CoreDumpling 12y ago
      http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
    - danieldk 12y ago
      http://mumble.net/~campbell/2014/04/28/uniform-random-float http://mumble.net/~campbell/2014/04/28/uniform-random-float
    - dhotson 12y ago
      Boyer-Moore (finding a string in another string) is a good example: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sear...
- drcode 12y ago
  I personally think distributed networks with smart contracts are going to be "a thing" soon, and in that kind of environment virtual cpu cycles are constrained to a level where an Intel 8080 processor looks like a speed demon. 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 https://github.com/drcode/ethereum-order-statistic-tree)
ilovecomputers 12y ago
No, but we do think about efficient computational solutions to our problems. These sorting algorithms are simply starting points for you to start thinking how algorithms solve problems, how to optimize them, how to construct data structures, and how to apply asymptotic analysis on your computational solutions. If all goes well with these algo courses, you should end up thinking like a computer scientist ;)
cbd1984 12y ago
In most complex jobs (that is, jobs with a theoretical component someone writes books about), the theory part mostly comes to the fore when something goes wrong, and you have to diagnose and fix the problem. 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.
gleenn 12y ago
I had a professor who told the class that if they ever wrote a sorting algorithm professionally, they should be fired. Depending on where you go, college is some cross between academia and training to get a job, and usually biased towards academia. While not directly relevant to daily programming, understanding time complexity and whats going on under the hood are very useful for understanding many things that I do use on a regular basis. 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.
- karmacondon 12y ago
  I realize that you chose one example off the top of your head, but it seems like an incredibly rare case. The majority of developers can understand "Queries involving this column are slow, it needs an index". Slightly more sophisticated developers can use an EXPLAIN statement (or it's equivalent) to see how many rows are being scanned and apply indexes where necessary. How many hours of coursework is it worth to obtain the knowledge "finding things in a ordered tree data structure are way faster than scanning through the whole table"? 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.
  - MichaelGG 12y ago
    Eh, you'd be surprised by the number of devs that simply don't know what indexes are, other than magic-go-fast-juice. I've seen people put a separate index on every column, so that "it'd be fast for all queries"...without thinking that most of their queries used at least two predicates. I've seen people go on to spend tons of time and money on things that fundamentally cannot work because they simply are incapable of thinking through the complexity of what their asking. The fact that modern systems are so fast can let someone get pretty far before hitting a brick wall. 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.
plinkplonk 12y ago
no, but you need the type of thinking that goes into predicting/implementing/evaluating/debugging the performance of a sorting algorithm (unless you are doing some kind of simple CRUD app for years, which is a perfectly fine way to make a living)
atmosx 12y ago
Nope, there are ready-made libraries for every fairly common language out there.
deleted 12y ago
[deleted]
dools 12y ago
In most universities there is a distinction between software engineering and computer science. Computer science deals more with things like writing and optimising compilers, and the interface between hardware and software, and writing an optimised sorting algorithm is a good introduction to that kind of thinking. 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.
GFK_of_xmaspast 12y ago
I've been doing this for a living for about 15 years now and have had to implement a sorting algorithm from scratch a couple times for special-case scenarios. Graph algorithms, and linear algebra complexities, on the other hand, I've had to worry about a bunch.
kmfrk 12y ago
You can generally use them to model a situation or improve it. For instance, if you're doing a dictionary, you'll be looking into a trie or Bloom filter, and it's generally like that I'm using it. 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.
deleted 12y ago
[deleted]
Shivetya 12y ago
The majority of my data work for the last dozen or so years has been via SQL and I am only concerned with sorting from a performance perspective, larger hardware (read minis and mainframes) usually have fully developed databases so the real work is done by the OS/db engine. 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)
kryptiskt 12y ago
In the same way that mathematicians seldom solve quadratic equations, programmers seldom implement sorting algorithms. They are still a hugely important building block, and if you don't know how they work you will have little hope of creating good algorithms for situations when the off-the-shelf libraries can't help you anymore. Loads of programmers don't aspire to technically challenging work though and they will likely do fine, every now and then littering with accidentally quadratic code.
afarrell 12y ago
I will occasionally think "okay, so this bit is obviously going to cause O(n^2) database queries. Lets fix that." and add in a select_related(). But most of my performance-improving comes after gathering actual data.
dbecker 12y ago
This blog post by Joel Spolsky makes a case for teaching low-level stuff that I find very compelling. http://www.joelonsoftware.com/articles/fog0000000319.html 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.
jagbolanos 12y ago
You make a good point and I think it's because sometimes the objective is not clear. 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.
- delish 12y ago
  I agree with the reasons the parent provided, especially that teachers teach the content without providing a "why?" 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"
stevebot 12y ago
Yes it does matter, though its not usually very grand. Think about it this way, most of those algorithms you learned in college took someone in academia years to write. The algorithms I write in my day-job are usually MUCH more simple. 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.
mattxxx 12y ago
It's very important, but I wouldn't implement a sort; I would be making sure that I'm using the right one for the moment. 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.
deleted 12y ago
[deleted]
Everhusk 12y ago
So I come from the other end of the spectrum. Studied non-CS in college, and after graduating I became a self-taught developer and am now working as a "professional programmer". 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!
evanmoran 12y ago
We don't think about sorting specifically, but we do think about performance and the structure of data all the time. How data is stored very much effects how quickly it can be retrieved. This is pretty universal – Twitter needs different storage then Google – you'll be surprised how often you think in these terms.
jonkiddy 12y ago
On a typical day, no I do not think about sorting algorithms in particular. 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.

patio11 12y ago

Ask a simple question, get a simple answer: no. While there are some programmers who develop libraries, the majority will just consume well-understood sorting algorithms which are baked into their languages/standard libraries/etc of choice. If you find yourself coding mergesort and you are not in a job interview, a nightmare, or a nightmare of a job interview, you are probably doing something wrong. 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."

aninhumer 12y ago
Even ones that look trivial on the inside might take years of R&D to develop.
- throwaway43 12y ago
  Any examples ?
  - CoreDumpling 12y ago
    http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
  - danieldk 12y ago
    http://mumble.net/~campbell/2014/04/28/uniform-random-float http://mumble.net/~campbell/2014/04/28/uniform-random-float
  - dhotson 12y ago
    Boyer-Moore (finding a string in another string) is a good example: http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sear...
drcode 12y ago
I personally think distributed networks with smart contracts are going to be "a thing" soon, and in that kind of environment virtual cpu cycles are constrained to a level where an Intel 8080 processor looks like a speed demon. 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 https://github.com/drcode/ethereum-order-statistic-tree)

ilovecomputers 12y ago

No, but we do think about efficient computational solutions to our problems. These sorting algorithms are simply starting points for you to start thinking how algorithms solve problems, how to optimize them, how to construct data structures, and how to apply asymptotic analysis on your computational solutions. If all goes well with these algo courses, you should end up thinking like a computer scientist ;)

cbd1984 12y ago

In most complex jobs (that is, jobs with a theoretical component someone writes books about), the theory part mostly comes to the fore when something goes wrong, and you have to diagnose and fix the problem. 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.

gleenn 12y ago

I had a professor who told the class that if they ever wrote a sorting algorithm professionally, they should be fired. Depending on where you go, college is some cross between academia and training to get a job, and usually biased towards academia. While not directly relevant to daily programming, understanding time complexity and whats going on under the hood are very useful for understanding many things that I do use on a regular basis. 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.

karmacondon 12y ago
I realize that you chose one example off the top of your head, but it seems like an incredibly rare case. The majority of developers can understand "Queries involving this column are slow, it needs an index". Slightly more sophisticated developers can use an EXPLAIN statement (or it's equivalent) to see how many rows are being scanned and apply indexes where necessary. How many hours of coursework is it worth to obtain the knowledge "finding things in a ordered tree data structure are way faster than scanning through the whole table"? 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.
- MichaelGG 12y ago
  Eh, you'd be surprised by the number of devs that simply don't know what indexes are, other than magic-go-fast-juice. I've seen people put a separate index on every column, so that "it'd be fast for all queries"...without thinking that most of their queries used at least two predicates. I've seen people go on to spend tons of time and money on things that fundamentally cannot work because they simply are incapable of thinking through the complexity of what their asking. The fact that modern systems are so fast can let someone get pretty far before hitting a brick wall. 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.

plinkplonk 12y ago

no, but you need the type of thinking that goes into predicting/implementing/evaluating/debugging the performance of a sorting algorithm (unless you are doing some kind of simple CRUD app for years, which is a perfectly fine way to make a living)

atmosx 12y ago

Nope, there are ready-made libraries for every fairly common language out there.

deleted 12y ago

[deleted]

dools 12y ago

In most universities there is a distinction between software engineering and computer science. Computer science deals more with things like writing and optimising compilers, and the interface between hardware and software, and writing an optimised sorting algorithm is a good introduction to that kind of thinking. 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.

GFK_of_xmaspast 12y ago

I've been doing this for a living for about 15 years now and have had to implement a sorting algorithm from scratch a couple times for special-case scenarios. Graph algorithms, and linear algebra complexities, on the other hand, I've had to worry about a bunch.

kmfrk 12y ago

You can generally use them to model a situation or improve it. For instance, if you're doing a dictionary, you'll be looking into a trie or Bloom filter, and it's generally like that I'm using it. 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.

deleted 12y ago

[deleted]

Shivetya 12y ago

The majority of my data work for the last dozen or so years has been via SQL and I am only concerned with sorting from a performance perspective, larger hardware (read minis and mainframes) usually have fully developed databases so the real work is done by the OS/db engine. 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)

kryptiskt 12y ago

In the same way that mathematicians seldom solve quadratic equations, programmers seldom implement sorting algorithms. They are still a hugely important building block, and if you don't know how they work you will have little hope of creating good algorithms for situations when the off-the-shelf libraries can't help you anymore. Loads of programmers don't aspire to technically challenging work though and they will likely do fine, every now and then littering with accidentally quadratic code.

afarrell 12y ago

I will occasionally think "okay, so this bit is obviously going to cause O(n^2) database queries. Lets fix that." and add in a select_related(). But most of my performance-improving comes after gathering actual data.

dbecker 12y ago

This blog post by Joel Spolsky makes a case for teaching low-level stuff that I find very compelling. http://www.joelonsoftware.com/articles/fog0000000319.html 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.

jagbolanos 12y ago

You make a good point and I think it's because sometimes the objective is not clear. 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.

delish 12y ago
I agree with the reasons the parent provided, especially that teachers teach the content without providing a "why?" 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"

stevebot 12y ago

Yes it does matter, though its not usually very grand. Think about it this way, most of those algorithms you learned in college took someone in academia years to write. The algorithms I write in my day-job are usually MUCH more simple. 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.

mattxxx 12y ago

It's very important, but I wouldn't implement a sort; I would be making sure that I'm using the right one for the moment. 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.

deleted 12y ago

[deleted]

Everhusk 12y ago

So I come from the other end of the spectrum. Studied non-CS in college, and after graduating I became a self-taught developer and am now working as a "professional programmer". 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!

evanmoran 12y ago

We don't think about sorting specifically, but we do think about performance and the structure of data all the time. How data is stored very much effects how quickly it can be retrieved. This is pretty universal – Twitter needs different storage then Google – you'll be surprised how often you think in these terms.

jonkiddy 12y ago

On a typical day, no I do not think about sorting algorithms in particular. 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.