How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspxDo beginners even need to learn sorting algorithms? Let’s face it most modern programming environments have a sort function built in. In the so-called real world just about the only people who write sorting algorithms have PhDs in math or computer scienceen-USTelligent Evolution Platform Developer Build (Build: 5.6.50428.7875)re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10234425Sun, 06 Nov 2011 21:27:45 GMT91d46819-8472-40ad-a661-2c78acb4018c:10234425Dan Neely<p>@Fábio Franco</p>
<p>Yikes! The insertion/selection sorts are only trivially more complex than a bubble sort; and I'd think either was almost as easy to recreate from scratch. For a higher performing sort, without access to any external references I'd probably go with a merge sort; I find it much simpler conceptually and it's only major liability vs quicksort is that it needs 2n memory to sort an array of size n.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10234425" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10234270Sat, 05 Nov 2011 14:07:02 GMT91d46819-8472-40ad-a661-2c78acb4018c:10234270Russell<p>Excuse me, Dr. Fred?! Recursion is "worse than useless"? Recursion is often an elegant solution to a problem such as traversing hierarchical structures. How would you calculate N!, hmm? Recursion works well. You'd better take another look a recursion. It sounds like you got your nose out of joint about this technique.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10234270" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10234090Fri, 04 Nov 2011 17:10:06 GMT91d46819-8472-40ad-a661-2c78acb4018c:10234090Outsourcing Nepal<p>Found exactly what i needed for my sorting class...</p>
<p> </p><div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10234090" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10234079Fri, 04 Nov 2011 16:22:23 GMT91d46819-8472-40ad-a661-2c78acb4018c:10234079Garth<p>I can see my idea of "beginners" is very differents from most commenters here. My idea of "beginners" are kids that would get something out of the Computer Science Unplugged sorting lessons. Now those are fun and won't scare a beginner.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10234079" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10234011Fri, 04 Nov 2011 14:09:24 GMT91d46819-8472-40ad-a661-2c78acb4018c:10234011Yves Daoust<p>Sorting is not just about sorting. It is a convenient place to explain some elementary algorithmic techniques such as array traversal, nested looping, recursion, in-place processing... And also to experience the basics of creating bugs by array overflow, wrong loop termination criteria, data overwriting...</p>
<p>So easy to state the problem, so easy to exercise creativity. An excellent opportunity to show students that it is allowed (and beneficial) to use one's brain!</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10234011" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10233714Thu, 03 Nov 2011 18:37:21 GMT91d46819-8472-40ad-a661-2c78acb4018c:10233714Gerold Lee Gorman<p>Teaching Quick Sort as the only way to sort is potentially dangerous. It is a well known fact that the Quick Sort algorithm sometimes will run in N squared time if given already nearly sorted data. This could have disastrous consequences if it happened unexpectedly in a mission critical application. </p>
<p>Consider the case of an already sorted array, which contains a list of drivers and their current position in an auto race, such as the Indy 500. Every now and then a driver will overtake another driver, requiring that the rank table be resorted. As long as only a few elements are out of place, and even then only by a few slots, it is it quite possible that in this case that either Bubble Sort or straight insertion will compete favorably as the fastest possible sort - whereas Quick Sort will quite likely choke and die if it isn’t running on a fast system - much to the annoyance of the television sports reporters and fans.</p>
<p>Now let's up the stakes. In pretty much any online stock trading environment, there is usually a nice big list of biggest gainers and losers of the day, most shares traded, etc, at any given time. It's kind of nice to see this kind of list updated in real time. Of course, ideally, given that a lot of people are possibly looking at the data, it might be worth while to re sort the list after every tick of the market, just in case something has moved. Again, Quick Sort fails miserably, and Bubble sort works admirably, because just as long as we resort previously sorted list after every trade, or few trades, we stay in good shape.</p>
<p>Now it would be unthinkable of course, to imagine a single unified system that attempts to track every single aircraft in the sky at any one time, its position, its destination, its anticipated arrival time, and of course, predicted airspace conflicts based on flight plan, current airspeed, etc - and where that that system relies heavily on either Quick Sort, or Insertion Sort or any other basic sorting algorithm as it is taught; for just those reasons discussed. Just imagine if a single change in flight plan, or whatever caused the master air traffic database to have to be re sorted over and over again by a O(N log N) which turns out to be O(N^2). Yeah, better hope that the list that we are trying to update isn’t "aircraft which are getting dangerously close to each other.”</p>
<p>IMHO - Quick sort, insertion sort, bubble sort and all of the rest have their places, usually in code that is under development, but not quite ready to ship. Otherwise I would prefer to look at the types of data on a case by case basis, and then to consider based on the nature of the data, where it comes from, how it might evolve over time, etc, I would decide whether or not to use one of the standard sorts, or whether or to use something more specialized, like a radix sort, or a heap sort, etc. Customizing a sort algorithm to an application, takes some work however, especially when you start contemplating using a variety of techniques like using radixes to hash the keys into multiple heaps, etc; and thus the standard libraries have this thing called Quick Sort, which can be quickly be put to the task during application prototyping.</p>
<p>After that - beware and be aware.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10233714" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10233658Thu, 03 Nov 2011 16:10:17 GMT91d46819-8472-40ad-a661-2c78acb4018c:10233658Dan Sutton<p>Tree sorts are a good one to teach: an efficient algorithm for these is minimalist to the point of Zen, and it's also highly recursive. Of course, once the students get the basics down, you then teach them how to rebalance the tree... then you go for B-trees... and so on... there's a lifetime of fiddling and optimization into which tree sorts can be extended, and in the meanwhile, you get to learn a whole lot of programming and algorithmic techniques. </p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10233658" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10233617Thu, 03 Nov 2011 14:47:17 GMT91d46819-8472-40ad-a661-2c78acb4018c:10233617Dr. Fred<p>We teach 7 sorts of sorts to illustrate that there is more than one way to skin a category. But recursion is worse than useless: an approach that exists solely to show how clever CS professors are. There is never any reason to solve a problem recursively, and the non-recursive algorithms tend to be much cooler anyway. </p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10233617" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10233581Thu, 03 Nov 2011 13:18:09 GMT91d46819-8472-40ad-a661-2c78acb4018c:10233581Fábio Franco<p>The only sorting algorithm I can remember is bubble sort. I've learned all sorts of sorting algorithms while also learning Big-O notation.</p>
<p>For instance, I can't reproduce the quick sort algorithm without looking somewhere else. I believe that something is worth teaching if it's going to be remembered.</p>
<p>Sorting algorithms are too specific the be remembered and given attention to. It can help if someone is actually gonna do some work with it, but that's rare. They are however good tools to help teaching something else, like data structures or as you said, the Big-O notation. They will be forgotten, but the concepts they require to be implemented will not. But then, it could be any other type of algorithm and it would have the same effect: "Imprinting fundamental concepts to the student's brain".</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10233581" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10233566Thu, 03 Nov 2011 12:15:49 GMT91d46819-8472-40ad-a661-2c78acb4018c:10233566Francis W. Porretto<p>If you want to teach recursion in the abstract, go ahead. If you want to teach top-down or object-oriented programming in the abstract, go ahead. Use whatever examples you find apposite. The question is really whether the examination of specific algorithms provides a benefit to the student.</p>
<p>Computers (apart from the peripherals they can control) are useful for two and only two reasons:</p>
<p>1. Their ability to do arithmetic;</p>
<p>2. Their ability to store and retrieve large amounts of data.</p>
<p>Everything else is a consequence of those two powers. As a rule, students best come to appreciate the second of those two powers by studying access methods -- which invariably involves the study of searching and sorting methods. Despite the many advances in "prefab" kits of data manipulation and access methods these past two decades, a true understanding of what's possible in a computer still requires an understanding of searching, sorting, and how they synergize.</p>
<p>Why yes, I DO believe introductory CS students should be required to learn a machine language! However did you guess?</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10233566" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10233562Thu, 03 Nov 2011 11:57:06 GMT91d46819-8472-40ad-a661-2c78acb4018c:10233562Chan Kar Heng<p>Many stuff mentioned here are good stuff.</p>
<p>Only one I have reservations on is on benefits of recursion.</p>
<p>It may just be a personal thing, but I'd prefer to stay away from recursion as it eats up program stack space.</p>
<p>90% of cases, it's not even a problem.</p>
<p>It's only a problem when handling really huge amounts of data...</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10233562" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10232746Wed, 02 Nov 2011 20:27:30 GMT91d46819-8472-40ad-a661-2c78acb4018c:10232746Charley Williams<p>Agree with your comment that the sorting problem helps students think about algorithms. Everyone understands what the problem is, so you spend zero time explaining that. Plus, they all THINK they know how to solve it. But ask them to write their detailed algorithm and turn that into a program -- they'll appreciate how difficult it can be to be very specific in recording the steps for a process they THOUGHT they fully understood! It's also a good exercise for beginners in how to model and represent the problem as a simple collection.</p>
<p>So we're not just teaching "sorting". Rather, we're really teaching algorithms, and sorting is just the easy-to-understand problem domain. Given this purpose, it makes perfect sense to start with the more intuitive bubble and insertion sorts first. Those are the algorithms that most beginning students will come up with in their first try. Then, once you challenge them by saying it costs $10 each time you swap two numbers, now you're motivating them to look for a better solution!</p>
<p>Also remember we have no reason to call it "Quick Sort" until we understand why bubble / insertion / etc. are the "Slow Sorts". Quick Sort is "quick" compared to what?</p>
<p>I like teaching searching and sorting because these are problems everyone knows, everyone understands how it's relevent to computers (i.e. sorting names in Excel, showing the high scores on a video game, web searches in Google -- sorry, in Bing :-) ). And it's quite easy to demonstrate (VISUALLY!) the big-Oh relationships -- for example, linear search O(n) vs. binary search O(log n) vs. hash table O(1)). And I think the basic algorithm-efficiency concepts are really important to CS, whether or not you present it using the formal big-oh notation.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10232746" width="1" height="1">re: How Many Sorting Algorithms Do Beginners Need To Learnhttp://blogs.msdn.com/b/alfredth/archive/2011/11/02/how-many-sorting-algorithms-do-beginners-need-to-learn.aspx#10232496Wed, 02 Nov 2011 14:54:04 GMT91d46819-8472-40ad-a661-2c78acb4018c:10232496Garth<p>Many years ago I made this observation - want to reduce the size of your Programming II class? Teach sorting algorithms in Programming I.</p>
<div style="clear:both;"></div><img src="http://blogs.msdn.com/aggbug.aspx?PostID=10232496" width="1" height="1">