Sorting Algorithms for a Novice

Question

So, .Net and Java has spoiled me not being "required" to learn any sorting algorithms, but now I am in a need to sort an array in a different languages the doesn't have this luxury. I was able to pick up on bubble sorting with little issue. However, some sources detest the use of bubble sorting becuase of the horrible performance with average and worst case scenario of n^2 comparrisons. Bubble sorting seems to get the job done, but about tackle a array that has +100,000 elements and has me worried that performance could be an issue at this degree. On the other, some of the other algorithms look pretty intimidating in terms of complexity. My question is, what would be a good follow up to bubble sorting in terms of better performance, but not going off into complexity wasteland in implementation?

As a side note, I am an analyst that the programs as needed, not a CS major. Needless to say, theres some holes that I have yet filled in my programming expertise. Thanks :)

Answer 1

There are many options, each with their own trade-offs. As you've discovered, Bubble Sort's trade-offs are that it's (a) simple, but (b) slow with even remotely large arrays.

• Quicksort is a good one, but you may run into memory issues.
• I've used Heapsort with much success, but it's not guaranteed to be stable (though I've never had problems).
• Bogosort is fun to implement and talk about, but entirely impractical.
• and so on...

Having a good understanding of the data to be sorted helps one decide which algorithm is best. For example:

• How large will the array be?
• Is there a chance it's already sorted or partially sorted?
• What kind of data does the array contain?
• How difficult/expensive is it to compare two elements in the array?
• How difficult/expensive is it to determine if the array is sorted?
• and so on...

There is no one sorting algorithm that's better than all others. Choosing what fits your needs is something that you'll pick up over time and with practice.

Answer 2

Take your time to learn Quicksort, it's a great algorithm and not that complicated if you go slow.

If you want some sorting algorithms just to get your feet wet(ter), I would recommend Insertion Sort and Selection Sort, they are generally better than Bubble Sort, and quick to understand and implement. Merge sort is also common in algorithm courses. You will have much better use of Quick Sort though.

You should also understand the difference between stable and non-stable sorting, if you don't already. A stable sort will not change the order of items with the same key, while a non-stable could.