• Advertisement
Sign in to follow this  

What are some simple, yet efficient sorting techniques (not bubble sort)

This topic is 4837 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need to explain binary searching to a class, and how it's more efficient then just looping and using if statements. I understand binary searching completely, but I'll feel a little hypocritial using a bubble sort to do my sorting (inefficiency). Are there some good sorting techniques I can use? Nothing to complicated, as it's supposed to be to a non-technical class.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
If the point of the 'lecture' is to explain binary searching, don't even mention the sorting algoritm. It's not 'on topic'. :)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Radix, Radix, Radix

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
If the point of the 'lecture' is to explain binary searching, don't even mention the sorting algoritm. It's not 'on topic'. :)
Agreed

Share this post


Link to post
Share on other sites
Quote:
Original post by Vasant56
supposed to be to a non-technical class.

What type of class is it? If its not a data-structures class then I would just use bubble sort, or you could use selection sort as that's pretty easy to (goes through an array and inserts the smallest item near the beginning if I remember the data structures class I took).

Were the people in the class supposed to have programming experience? If not, then I would probably stick with bubble or selection sort. Data structures is usually for learning how the advanced sorts work, and then if you're using C++ you'll probably use the STL but its still good to know how to sort items.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
If the point of the 'lecture' is to explain binary searching, don't even mention the sorting algoritm. It's not 'on topic'. :)

I second this. Just draw a sorted list on the board, and walk through it. How it got sorted doesn't matter, so long as you make it clear that the list has to be sorted in advance. By ignoring the sorting question, you can spend more time on the searching question. The group will appreciate it, I promise.

If somebody asks how the list got sorted, tell them its the phone book. You get the book fully sorted, who cares what the phone company did before you got it?

CM

Share this post


Link to post
Share on other sites
Quote:
Original post by civguy
Quote:
Original post by Anonymous Poster
If the point of the 'lecture' is to explain binary searching, don't even mention the sorting algoritm. It's not 'on topic'. :)
Agreed

Just saw the above 4 posts now. I think you could explain binary search and a simple sort in the same class. I'm pretty sure my professor did back when I took my first real programming course.

I would at least recommend a teaching a version of bubble-sort. If the people in the class know something about computers, they should be able to understand both in the lecture depending on its length of time. How long do you have for it?

Share this post


Link to post
Share on other sites
Because it's supposed to be "non-technical", I also need to explain what an array actually is, and what not. Plus, for the length of my speech, and the simplicity of it (I can't go into huge detail). Essentially what I'm doing is:


Explaining an array
explaining how it's sorted
explaining how the binary search works, and how it's a quick and effective process.

Share this post


Link to post
Share on other sites
i think the best is ,in case somebody asks, and they isn't experienced programmers, is to explain insertion sort as it done by humans(including childs, including anyone who can sort things):

If i have many cards(i don't mean complete set of playing cards) or books and want to sort 'em,
i'm getting one card from unsorted group, then intuitively do binary search in sorted group for position where to insert the card. (actually, i and most people do better-than-binary search using brain as temporary cache). It's O(N log N) worst case complexity, and O(N) if already sorted.

Then say that it's not simple for computer to just insert and there's many other algorithms avaliable.

As about simplest O(N log N) sorting... probably merge sort is simplest O(N log N) sort on computer, even a child can understand on example. Say, you have 2 sorted groups of cards. You need to merge 'em together so result is also sorted. To do it you just get card from group with lover card on top, and put into sorted group.

It's probably not harder to explain than bubblesort. Because if you'll explain bubblesort, someone with sense of humour will ask you to sort 56 cards in that way, for example, and it's hella hard[grin][lol]. Probably only so retarded thing as computer might really sort something large enough using algorithm with O(N^2) complexity, and there's no human so stupid to use O(N^2) on >10 things.

[Edited by - Dmytry on October 24, 2004 5:39:37 PM]

Share this post


Link to post
Share on other sites
Radix sort is theoretically complexity N when you know the maximum value of your items, but if you run on a machine with a deep memory hierarchy (i e, multiple layers of cache, memory pages, and maybe even paging to disk), it usually loses big.

QuickSort is complexity N log N (like merge and heap sorts), but it also has as good memory locality as you will see in a sort. I guess that's why it's one of the most popular sorting algorithms. The only draw-back is that it's not a "stable sort," so if you want multiple keys, you have to evaluate all of them at the same time.

Googles for QuickSort will show up tons of references, I'm sure. It's very simple to implement, too.

Share this post


Link to post
Share on other sites
Quote:
Original post by hplus0603
Radix sort is theoretically complexity N when you know the maximum value of your items, but if you run on a machine with a deep memory hierarchy (i e, multiple layers of cache, memory pages, and maybe even paging to disk), it usually loses big.

QuickSort is complexity N log N (like merge and heap sorts), but it also has as good memory locality as you will see in a sort. I guess that's why it's one of the most popular sorting algorithms. The only draw-back is that it's not a "stable sort," so if you want multiple keys, you have to evaluate all of them at the same time.

Googles for QuickSort will show up tons of references, I'm sure. It's very simple to implement, too.

but looks somewhat magical to unexperienced programmers. Idea is simple, somehow pick some value and then sort/split array into part that is bigger than that value and part that is lower and then sort parts, but it's still hard to explain, especially because you have to "somehow" pick "some" value. I'm remembering first time i found quicksort in examples on my computer, totally uncommented thing. And i had no internet. And i had no books on subject. And i was a n00b. And it took some time(maybe hour,maybe hours) to fully understand WTF it works by doing some steps manyally! That "somehow" part obfuscated things alot.

Share this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
Quote:
Original post by Anonymous Poster
If the point of the 'lecture' is to explain binary searching, don't even mention the sorting algoritm. It's not 'on topic'. :)

I second this. Just draw a sorted list on the board, and walk through it. How it got sorted doesn't matter, so long as you make it clear that the list has to be sorted in advance. By ignoring the sorting question, you can spend more time on the searching question. The group will appreciate it, I promise.

If somebody asks how the list got sorted, tell them its the phone book. You get the book fully sorted, who cares what the phone company did before you got it?

CM


Better yet: If somebody asks how the list got sorted, offer to cover it in the next lecture :)

(I vote for MergeSort btw)

Share this post


Link to post
Share on other sites
Quote:
Original post by Vasant56
I need to explain binary searching to a class, and how it's more efficient then just looping and using if statements. I understand binary searching completely, but I'll feel a little hypocritial using a bubble sort to do my sorting (inefficiency).

Are there some good sorting techniques I can use? Nothing to complicated, as it's supposed to be to a non-technical class.
what on earth does the sorting algorithm have to do with the binary search ;) ??

i hardly beleive that a class would be distracted by how the sorting routine works if you're only teaching them aout the binary search, don't you?

hide the sort implementation. you dont want them distracted anyway!

eg.
// teaching binary search stuff!!
std::sort( mydata.begin(), mydata.end() ); // it sorts, you dont need to know how!
// do more teaching!

Share this post


Link to post
Share on other sites
Quote:
Original post by silvermace
what on earth does the sorting algorithm have to do with the binary search ;) ??


Quite alot, binary search only works properly with a sorted container, it takes advantage of this knowledge.

Anyways if your teaching c++ then using std::sort is implementated with a variation of quick sort known as introsort which has a better worst case complexity, std::stable_sort is implementated with merge sort and std::partial_sort is implementated with heapsort.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Quote:
Original post by silvermace
what on earth does the sorting algorithm have to do with the binary search ;) ??


Quite alot, binary search only works properly with a sorted container, it takes advantage of this knowledge.

Anyways if your teaching c++ then using std::sort is implementated with a variation of quick sort known as introsort which has a better worst case complexity, std::stable_sort is implementated with merge sort and std::partial_sort is implementated with heapsort.
what i meant was, he's not teaching how to sort, he's teaching how binary search works, so he should concentrate on the search not the setup (thats what i lecturer did, and it worked quite well)

appologies oh great snk_kid, for i have sinned with a bad explination! :)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you're just talking about sorting as a side note to binary search, I say don't do it. Spend the extra time talking about why binary search is fast, answering questions, doing examples, etc.

But if you have to talk about a sorting algorithm, I think insertion sort and selection sort are the easiest to understand and explain, because doing real world examples with them is easy. For example, sorting a hand of cards.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Quote:
Original post by silvermace
what on earth does the sorting algorithm have to do with the binary search ;) ??


Quite alot, binary search only works properly with a sorted container, it takes advantage of this knowledge.

While you should make note that the data needs to be sorted, and might even sugest a few different algorithms, if you are teaching binary search, then you shouldn't digress into sorting. Save it for a future lecture.
Quote:

Anyways if your teaching c++ then using std::sort is implementated with a variation of quick sort known as introsort which has a better worst case complexity, std::stable_sort is implementated with merge sort and std::partial_sort is implementated with heapsort.

You are not guaranteed this. Remember, the standard never dictates what specific algorithms do, just their performance constraints. Which in this case is "approximately N log N (where N = first - last) comparisons on the average."1

Thus, both quicksort and introsort, along with a whole slew of other sorts, satisfy this requirement. The difference is in the worst case bounds. But on that topic, the standard is silent.

1See ISO/IEC 14882-1998, Section 25.3.1.1 - 1

Share this post


Link to post
Share on other sites
Hmm, it always bothered me - average complexity of O(N log N) - what mean average? Average over all permutations of input data?
I think insertion sort is the best because it's done using binary search.

Share this post


Link to post
Share on other sites
Just say that the person who entered the data had already correctly sorted it themselves into order, before typing it in.

That'll make people think about how sorting is human and possible and not magic.

But then you can move on.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Some demos of sorting algorithms. Fun to watch AND!! you can see the relative speeds of the algorithms on a random input.

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

Share this post


Link to post
Share on other sites
I think quick-sort will do , its performence is O(n log n), what is considered as a fast one.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement