Quicksort

[chrisname]

I have a question about quicksort. From what I've read, the value you pick as your pivot can have an effect on the overall performance of the algorithm. So how do you pick a pivotal value? I guess the easiest method would be, given the size of the array, to choose the middlemost element (e.g. in an array of 25 elements, element 12 is your pivot); but it's probably not the most efficient way.

So how should I decide what element to pick as a pivot?

[helios]

the value you pick as your pivot can have an effect on the overall performance of the algorithm.

Sometimes. Always picking the median means that the performance depends on the data. This is bad if the source produces consistently worse-than-average data. Picking a random element removes the data as a factor, and the algorithm will always have an average complexity of O(n log n).

[chrisname]

Oh. It's as simple as generating a random number? I thought of that, but decided it would be better to ask. Thanks :)

[tummychow]

In general the pivot point can affect the execution, but a random point is generally fine. There's also that three-way median method, but no matter what pivot you choose, there is a list that can cause worst complexity for that method.

[chrisname]

Thanks helios, tummychow.

[blackcoder41]

hey everyone, take a look at this. http://www.youtube.com/watch?v=AqRPalHY2mM
very interesting, about quicksort and bubble sort

[chrisname]

That was actually very interesting. Thanks!

[blackcoder41]

love the robots eh.. lol ^^

wait, i think there is also a video about pointers.

edit:
http://www.youtube.com/watch?v=6pmWojisM_E&feature=related

[chrisname]

Oh god... that one is just annoying.

Anyway, I don't think there's much to know about pointers that I don't know already.