Search:

Ah, so you have. I only now realized the output thames showed was from your program. Okay, the swap count makes sense then, because your code uses random pivot selection. This thread has meandered so...

That's not why I asked.

The reason I asked was because there are many variants of quicksort that do not cause any swaps to happen if the data is linear and ascending: ith data element being A*i+B,...

Is that the version of quicksort that moves (swaps) the pivot to the start/end first?

The CPU architectures have undergone some serious changes. We now have branch prediction, efficient caching algorithms, even speculative execution, on typical processors. I suspect the relative cost...

Obviously.

My code is a two-state state machine, where the first inner while loop locates the initial pair to swap. If none, it is done. Otherwise it continues into the actual swapping loop. The...

Really? My measurements disagree.

Using Athlon II X4 640 (with a stable time stamp counter), median cycle counts for test sorts for uniform random input were


# N ints, no padding, 100000...

Programming errors?

Verifying the functions work is a simple form of unit testing. When I fiddle with sort functions, I write a test harness: a main() that generates test cases, sorts them,...

Good points (and by Adak, as well). I think I'll switch to insertion sort, too.

Like I said earlier, the data I sort tends to be large enough for radix sorting, so I've never paid much attention...

Oh no, that's not what I meant. I meant that in post #2, you did not notice that thames' code will get stuck (never complete) if the pivot occurs more than once in the array.


No selection sort?...

Yes, that is the correct location, when you use a random pivot selection.

I don't think Adak noticed the issue with repeated pivots: your code sometimes gets stuck, if there are repeated numbers...

I'd like to point out a couple of things. First:


The above is wasteful. On every invocation, you'll reinitialize the random number generator, based on the current time in seconds. Because the...