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.

If the point of the 'lecture' is to explain binary searching, don't even mention the sorting algoritm. It's not 'on topic'. :)

Radix, Radix, Radix

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

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.

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

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?

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.

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]