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.
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
>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.
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
>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.