• Post Reply Bookmark Topic Watch Topic
  • New Topic

What's with all these sorting techniques ?  RSS feed

 
Shubham Semwal
Ranch Hand
Posts: 176
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,
Why are there so many sorting techniques - selection sort, insertion sort, bubble sort, quick sort, merge sort, heap sort etc etc etc.
I'm very confused trying to learn how to do these. And then there are complexities and all. Is learning them really required ? How much should I learn ?
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There are many different scenarios in which you would do sorting. Some algorithms do better than others in certain scenarios while they do worse than others in different scenarios. Insertion, Selection, and Bubble sort are relatively simple algorithms that are good enough for smaller sets of data. For larger sets of data, you'll want to use more sophisticated algorithms, like QuickSort and MergeSort.

How many of them should you learn? Well, if you're going to be a programmer, it's good to be at least familiar with the more common algorithms and the scenarios for which they are well-suited. How to learn them? Study and practice.

Here are some good starting points for study:
https://en.wikipedia.org/wiki/Sorting_algorithm
http://www.sorting-algorithms.com/
 
Campbell Ritchie
Marshal
Posts: 56584
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, you do have to know about them. At least some of them. You may not have to implement a sorting algorithm, because there are methods like this, this, this and this. You need to know why you use merge sort instead of quick sort. You need to know what to say when they as you to implement BogoSort as an interview exercise.
You can find nice little tutorials easily enough. Here are a couple: 1 2.
This tutorial may be easier to understand. But less intellectual.
 
Shubham Semwal
Ranch Hand
Posts: 176
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What's annoying is that sometimes the loops start at 0->arrayLength, sometimes at 1->arrayLength-1.
Sometimes inner loop traverses in forward direction and then other times it starts at i(looping var.) and starts traversing backward.
And then there's the infamous recursion which throws me completely off track.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To me the main reason for teaching all of these different sorts isn't so you learn all the different sorting techniques (though that is useful)
It is used to demonstrate how to compare different algorithms.

How do you tell in the real world which approach is better than another?

Comparing all the sorting/searching algorithms provides a great platform for teaching that. Big O notation for instance.
The idea is that you can then expand this to algorithms OTHER than sorting/searching.

Of course in the real world, you just call Collections.sort() and be done with it. 99% of the time, that will be all that is needed.
But the algorithm analysis skills might just come in useful one day.
 
Tushar Goel
Ranch Hand
Posts: 934
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you are working in a project where performance and memory matters most then knowing algorithm is your friend.

Secondly, it also teaches you how to solve certain problems. For an example, Merge sort uses divide and conquer approach, so
if you know how to use divide and conquer technique then you may use it to solve some other problem in which solution is not so
obvious.

Thirdly, if you learn algorithm then you start seeing the problem with different angles. Like solving a problem is important but solving
it better way by saving resources and time is more important.
 
Tim Holloway
Saloon Keeper
Posts: 18799
74
Android Eclipse IDE Linux
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A lot of people think that HeapSort and QuickSort are "THE BEST" sorting algorthms. But they aren't. "THE BEST" is a juvenile conceit. Every algorithm has its best and worst cases. You can apply a compression algorithm to some data and that algorithm would actually result in a larger amount of data that what you started with - take a look next time you use a command-line ZIP program and you'll see that it tries different algorithms to see which one works best for each file.

Heap and Quick sorts are optimal for large amounts of completely random data. They will do abominably when applied to data that is entirely or nearly entirely ordered and they carry so much overhead that if the data set is small enough they won't be any faster than a dumber sort.

My classic example was an old mainframe app I used to be responsible for. It was the central control and distribution point for every form of output from the shop's application systems and it ran hundreds of times a day, so the more efficient it was, the better. This particular system got a whole bunch of items in its input that were mostly, but not completely in order - there was a knot in the data where some of the high-key items were produced about 75% through the data stream being fed to my app.

That's a worst-case scenario for Heap and Quick sorts. It's also a bad case for the simple Bubble sort, since the out-of-sequence data was deep enough into the set that a lot of bubble passes would be required.

The optimal sort for that particular data set was the Shell-Metzner sort. Like the Bubble sort, it works well on pre-ordered data, but has the advantage that the out-of-sequence data can "leapfrog" up the chain in a binary fashion.

There was another advantage unique to the times and conditions. Back then you couldn't just grab a sort algorithm and plug it in. You had commercial sorts, but they were large stand-alone apps, not suitable for trivial inclusion in other programs. And while COBOL had limited sorting support, the systems I worked on weren't suitable for coding in COBOL; I was constrained to use Assembly Language (stuff like C wasn't generally available for mainframes back then). A Bubble Sort was about 1 page of code and maybe a day to implement, so our assembly language apps typically did bubble sorts. A Shell sort ran me about 3 pages of code and 2 days work - a worthwhile investment. Anything more sophisticated would have probably run 5 pages minimum and a week of labor. And while the "Git 'R Dun!" philosophy wasn't an overriding concern back then when machines were more expensive than humans, I had enough other things to do that I wasn't of a mind to add extra work if I could avoid it!
 
Shubham Semwal
Ranch Hand
Posts: 176
3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is the program I've been studying -



How to understand what's happening in the subsequent recursion calls ? What's the best way to understand these king of flows ?
 
Chris Barrett
Bartender
Posts: 321
24
Eclipse IDE Firefox Browser
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Shubham Semwal wrote:What's the best way to understand these kind of flows ?

For me, I like to sit down with paper and pen and draw out what is happening. Take a small data set. Draw out what is happening. Figure out what is passed recursively to the next iteration. Repeat again for the next recursive iteration. Putting real numbers to the lowerIndex, higherIndex and pivot will make the process much easier to understand.

Time consuming? Yes. Will you be forced to think? Absolutely! But, thinking leads to understanding. I also find just holding a pencil and drawing out the steps helps the learning and retention process. Probably a right brain/left brain activation thing.
 
Knute Snortum
Sheriff
Posts: 4287
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The Wikipedia article on Quicksort has a cool animation that I found useful.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!