qsort

This is a discussion on qsort within the C Programming forums, part of the General Programming Boards category; Does anyone know how it works, I tried a little search on google, with little success. I found out though ...

  1. #1
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501

    qsort

    Does anyone know how it works, I tried a little search on google, with little success. I found out though that it does use recursion.
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,660

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Does anyone know how it works
    Like magic. The way it should be.

    >I found out though that it does use recursion.
    Prove it. qsort isn't required to implement quicksort, nor is it required to use recursion. In fact, a good implementation will probably write a partially or completely iterative sort for performance purposes and merge several sorting strategies into one to remove worst cases.
    My best code is written with the delete key.

  4. #4
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    prelude, you aren't being nearly as helpful as usual!

    Anyway, recursion can be used and is an implementation specific detail. I'll loosely explain quicksort but just because I have family over and I am trying to escape them.

    quicksort basically does this....

    take array, choose number which can be logical "half way" point. move all less than to the left of the halfway point. All greater than to the right of the halfway point. Then that gives you two smaller arrays to perform the same operation on. The recursion comes in because you're going to perform the operation again on increasingly smaller chunks of the array.

    As prelude says, recursion is never actually necessary and can actually be quite a bit slower than the alternative. You can simulate recursion with a stack full of informative stuff and looping. But you should try the algorithm the easy way first. Go ahead and use recursion. But in other things, listen to prelude.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >prelude, you aren't being nearly as helpful as usual!
    I know, but won't everyone be happy when I start posting like I used to again?
    My best code is written with the delete key.

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Don't go back Prelude

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. An interesting problem of qsort()
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 03-05-2008, 11:09 AM
  2. qsort() in Array of Pointer to String
    By vb.bajpai in forum C Programming
    Replies: 8
    Last Post: 06-16-2007, 04:18 PM
  3. trouble with qsort
    By qubit67 in forum C Programming
    Replies: 5
    Last Post: 04-29-2007, 10:23 PM
  4. Question About Using qsort
    By Zildjian in forum C Programming
    Replies: 3
    Last Post: 11-04-2003, 02:17 PM
  5. C++ link error with qsort
    By bvnorth in forum C++ Programming
    Replies: 7
    Last Post: 10-24-2003, 02:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21