1. ## Binaryy Sorting

Hi,

what is actually binary sorting?

How can it be performed in linked lists?

2. Well how to explain binary sorting... Hm... If it's not one thing, it's the other.

Quzah.

3. In a word: search.

Try doing a search on the board: http://cboard.cprogramming.com/searc...earchid=531620

Or perhaps a search on cprogramming.com/tutorial.html for "binary": http://www.cprogramming.com/tutorial/lesson18.html

Or you could just wait for me to do it for you . . .

4. Binary search you split the array in half on each loop, and discard the half that can't have the object you are looking for. That's why it's faster.

You have to have a sorted array to do a binary search

For a linked list, you probably would use functions built into the list, and create a binary sort algorithm with them. (note the linked list has to be sorted)

5. Originally Posted by sankarv
Hi,

what is actually binary sorting?

How can it be performed in linked lists?
This is Binary Sorting:

Remember when you were a kid and you played "guess the number between 1 and 10", game?

The kids usually tried to think of their friend's "lucky" number, maybe a 7 or a 3, but otherwise (say your friend had no lucky number), you might just try and "cut the numbers in half, each try", and get your friend to tell you if your guess was too high or too low.

I'm thinking of a number between 1 and 10:

guess #1: 5 ==> Too low. All #'s below 5 are removed from the possibles set.
Low comes up to 6, and is our new "floor" of the possibles set of numbers.

guess #2: 7 ==> Too low All #'s below 7 are removed from the possibles set.
Low rises to 8. High index is still at 10.
guess #3: 9 ==> (could be eight, but it can't be 8.5, because this is all integers) Too high
Numbers 9 & 10 is removed from the possibles set. High index comes down to 8.
guess #4: 8 ==> Gotta be it!

If the answer was not found, the next loop would put the index low above the index high, causing the program to exit the while loop.

It doesn't seem too efficient in a range from 1 to 10, but in a larger range, it quickly shows it's efficiency in a very BIG way.

Consider a range of 1 to 1,000,000. In your first guess of 500,000 you eliminate roughly 500,000 possibles from the set that can contain the answer you're seeking. :P
Guess # Possibles remaining
=======================
1: 500,000
2: 250,000
3: 125,000
4: 62,500
5: 32,250
6: 15,625
7: 7,812
8: 3,906
9: 1,953
10: 976
11: 488
12: 244
13: 122
14: 61
15: 30
16: 15
17: 7
18: 3
19: 2
20: 1

(Numbers are approximate, not actual)

Imagine being able to search through a set of a million numbers, in only 20 comparisons!

Many times the answer will be found before this worst case example.

All of this is done in a simple while loop with just a few lines of code inside it. It runs VERY fast.

Binary search can be used to search through ANY data that you can put into sorted order, and move two indicies (usually called low and high), through.

Do you know how to move an index (a variable which you can assign to a specific place on the linked list), through a linked list?

If so, it's a cinch - if not, you'll have to learn that, first.