Thread: Binaryy Sorting

  1. #1
    Registered User
    Join Date
    Sep 2006
    Posts
    16

    Binaryy Sorting

    Hi,

    what is actually binary sorting?

    How can it be performed in linked lists?

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well how to explain binary sorting... Hm... If it's not one thing, it's the other.


    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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 . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Registered User
    Join Date
    May 2006
    Posts
    57
    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. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote 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.

    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

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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?
    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).
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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 ; )
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 08:05 PM