Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

First off, if this is in the wrong place I apologise. I wasn't too sure on which of the Stack Exchange sites to ask it.

I am studying Software Development at university, on a one year conversion course. My main programming language is Java. We have just finished studying searches and sorts. Focussing on the latter in particular, I had a hard time working through the intricacy of the code. Some, like an insertion sort, were obvious enough. Others, like the merge sort, I found extremely tricky to get my head around. I understand totally how they work, I just wouldn't want to implement my own.

I've been told most programmers don't create their own sorts/searches as the built in methods in Java are more reliable and generally faster. However, it's considered good practice to know these sorts.

When I look at a sort like the merge sort, or binary sort, I think to myself that I could never have come up with such solutions. They are too intricate and complicated.

This brings me to my question. Do most programmers use sorts like people use simple Maths formulae, e.g. the area of a triangle or circle, where you apply it almost mesmerically? As a programmer would you put any real effort into trying to develop new, or more efficient sorts? Or if you knew a sort was needed would you simply know which was better through the bigOh notation and then just copy and paste the same thing in, without ever really thinking about the coding behind it?

Note: if this question is not fit for Q&A (I did look at the FAQ and I think it is), please advise me where I could post. Thank you.

share|improve this question
6  
You don't get to call yourself a programmer until you can do this. ;) –  Yannis Rizos Feb 22 '13 at 0:00
2  
You don't have to come up with merge sort. You merely have to understand how it works. Unfortunately, they are often taught poorly. The best way to understand them is to sort a deck of playing cards with each kind of sort. –  Steven Burnap Feb 22 '13 at 0:01
1  
@StevenBurnap: I understand entirely HOW it sorts. It's just when I look at the code required, it takes me a very long time to go through it. I understand its bigOh notation, and I believe I could know WHEN to use it - given that, should I just copy and paste it in each time? How important is actually knowing what the code is, as long as I understand how it works? –  Andrew Martin Feb 22 '13 at 0:02
    
@YannisRizos: The epicness of that is too damn high! –  Andrew Martin Feb 22 '13 at 0:03
    
@AndrewMartin Well...a sort is just an algorithm, and most sorts aren't complex algorithms. If you have troubles going from code <-> algorithm for a sort, I'd question if you could do so with any other algorithm. –  Steven Burnap Feb 22 '13 at 0:06
show 4 more comments

4 Answers

Usually you don't have to understand all aspects of the actual implementation of a specific language/library/environment. It is also not a common task to implement those manually as implementations for any environment exist.

By learning the concepts of different search algorithms is a key part of any computer science curriculum, though. By this students learn many fundamental techniques for any algorithm and algorithm comparison. One also learns different approaches which can be used for other algorithms, too.

Looking at this from a practical purpose: Sorting is a common operation. Knowing sort algorithms helps to pick the best choice at hand. Even though the Java designers have made a good choice for general purpose (I'm, not deep into Java but think they have different implementations and pick one depending on the case ...) but if you know your data you probably might pick a better algorithm.

share|improve this answer
    
Thanks for this. Ironically, I actually understand the Maths behind each of them quite well and I feel I could choose the appropriate one in a given situation. I'd just currently feel a lot more relaxed copying and pasting a solution across, than actually coding it. Then again, I'm still a beginner - I suppose I'll get there with time. –  Andrew Martin Feb 22 '13 at 0:16
    
Well, ban "copy and paste" from your vocabulary immediately. You should never copy and paste code. Write a function that encapsulates it and call that. –  Steven Burnap Feb 22 '13 at 0:24
    
@StevenBurnap: True, that was extremely lazy wording. Programming 101 and all that - don't copy and paste! –  Andrew Martin Feb 22 '13 at 0:25
    
Coding it is a good exercise. When reading a "proper" implementation, meaning one actually used in a common library outside academics, you often have code which plays tricks for performance reasons while trying to cover all edge cases, reading this can be hard, but quite rewarding to understand the environment. Then again: Most of such tricks usually are a bad idea for general purpose code ("Premature optimization is the root of all evil") –  johannes Feb 22 '13 at 0:52
add comment

To be honest, I've been a software developer for more than 30 years and haven't had to write a sort function in at least 20 years. Yes, it's important to understand how they work, but frankly, I can't remember the last time I actually used a sort explicitly, it's generally implicitly done by the libraries or backend you are using.

share|improve this answer
    
Thanks - just the answer I wanted! –  Andrew Martin Feb 22 '13 at 0:18
    
Yeah, my experience is very much the same. However, I'm confident I could implement a sort routine from scratch fairly quickly. –  Steven Burnap Feb 22 '13 at 0:19
    
I suppose you implement them so often you'll get to a point where you realise you could just code it from experience. –  Andrew Martin Feb 22 '13 at 0:21
    
@AndrewMartin: Quite the opposite. As the answer states, there's generally never a need to write them. They exist in libraries already, or the libraries you're using already sort the data if needed. It's a very low-level thing. And if you did find your self in a place to need to write one, who cares if you can magically write the best version off the top of your head? I doubt anyone could. Just look it up. –  GManNickG Feb 22 '13 at 1:10
add comment

Folks obsess about sorting algorthims for the wrong reasons. The value of understanding mergesort or any other sort isn't simply being able to write your own sort function. Rather it's that sorts provide readily understandable examples of entire classes of algorithms. Mergesort and quicksort are both examples of a general approach called 'divide and conquer'. You probably will never need to re-write mergesort, but if you understand mergesort you have a much better chance of recognizing when a 'divide and conquer' approach can be used to solve problems you do face.

share|improve this answer
add comment

While I've never had to implement a standard sort outside of school, what does come up occasionally are situations where I need an algorithm that is just different enough that I can't use a standard one. In those situations, I have to figure out the best standard algorithm to start with, and modify it to suit my needs.

For example, I'm currently writing a calculator as a hobby project. To handle operator precedence, I'm using the Shunting-yard algorithm, but all the implementations I could find assume that the entire expression is available when you start running the algorithm, whereas I need to be able to sort of "pause" in the middle of the algorithm while the user is still in the process of punching buttons. Not a huge deviation from the standard implementation, but different enough that I had to have a really good understanding of how and why it works.

So, don't stress out about algorithms being difficult, but don't blow off the lessons either. It will get easier with time.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.