Hi,
what is actually binary sorting?
How can it be performed in linked lists?
Printable View
Hi,
what is actually binary sorting?
How can it be performed in linked lists?
Well how to explain binary sorting... Hm... If it's not one thing, it's the other. ;)
Quzah.
In a word: search.
Try doing a search on the board: http://cboard.cprogramming.com/searc...earchid=531620
Or a google search on cprogramming.com: http://www.google.com/custom?domains...D%3A1%3B&hl=en
Or maybe a google search on aihorizon.com: http://www.google.ca/search?hl=en&q=...y+search&meta=
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 . . . :)
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)
This is Binary Sorting:Quote:
Originally Posted by sankarv
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.
I can't help you with linked list searching, however. I seldom use linked lists.
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.
Adak
That's the thing about binary searching: it requires random-access to the elements. A linear search can be performed on a linked list very easily, but a binary search is harder. A linked list isn't suited to binary searching. If you want to do a binary search, use a different data structure. Or you could count from the start of the linked list to find the elements you want, which would be pretty inefficient (although still more efficent than a linear search).Quote:
I can't help you with linked list searching, however. I seldom use linked lists.
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?
The OP wanted binary sorting, but you guys are giving stuff about binary searching. What gives...?
I know, there's no such thing as "binary searching". Just play along ; )
The fact that it was basically a "google for me" post which would have been answered by the OP putting a bit more effort in up front.