DBO Forums - Agreed

Agreed (reply)

kidtsunami — Sat, 26 Oct 2013 18:18:59 +0000

Insomniac definitely had a pretty tricky in place array sort in their code test.

I Vaguely Remember Doing This (reply)

Schooly D — Sat, 26 Oct 2013 15:52:46 +0000

This is probably the last time you'll ever write these sorting algorithms

Unless he decides to interview for a programming job within 5 years after graduation.

Yah, just use the libraries... (reply)

RC — Wed, 23 Oct 2013 23:18:49 +0000

A wise man once told me:

"A good programmer knows how to write good code,
but a great programmer knows how to steal good code."

;)

QuickSort conclusion (reply)

Samusaaron3 — Wed, 23 Oct 2013 23:04:57 +0000

Three randoms should work well. If you want to go all out, you could also implement switching to insertion sort once you're dealing with small arrays (around size 10 or so).

You can read up on it here: http://algs4.cs.princeton.edu/23quicksort/

Let me know if the median pivot works well!

QuickSort conclusions (reply)

marmot 1333 — Wed, 23 Oct 2013 21:27:33 +0000

Cool, I think I will.

How do you choose the three? Beginning, middle, end? Three randoms?

I Vaguely Remember Doing This (reply)

Blackt1g3r — Wed, 23 Oct 2013 21:23:38 +0000

This is probably the last time you'll ever write these sorting algorithms, enjoy it while it lasts. :)

QuickSort conclusions (reply)

Samusaaron3 — Wed, 23 Oct 2013 20:31:36 +0000

You should experiment using the median-of-three method for choosing a pivot, and see how much faster you might be able to make it go :)

Very cool to see your results!

QuickSort conclusions (reply)

GrizzNKev — Wed, 23 Oct 2013 20:18:01 +0000

I'm not into any complex sorting algorithms yet, but I did successfully complete the IPC assignment I mentioned in that thread with few issues. Now I know how to effectively share memory and communicate between processes to create a distributed workload. Yay!

It's like he's trying to tell me something! (reply)

Oholiab — Wed, 23 Oct 2013 19:06:23 +0000

I have absolutely no clue about which you speak. Further evidence that most people are way smarter than I am.

QuickSort conclusions

marmot 1333 — Wed, 23 Oct 2013 15:58:02 +0000

There was some interest in my Java-based Quicksort project but that thread got locked.

To update: I was using an algorithm out of my book that used the right-most value as pivot. This led to the partitions being extremely unbalanced (8191 vs 1 in case of 2^13) and led to stack overflows starting at 2^13.

So I just updated my algorithm to utilize randomized quicksort; it chooses a pseudo-random element in the array and uses that as pivot. This solved my stack overflows as I was able to sort up to 2^20 for sorted, reverse sorted, and shuffled arrays with no problem.

So I guess I was lucky, Sekhmet, because my quicksort was performing faster than heapsort on the largest set (2^20). Here's some sample output.


Starting a HeapSort with n sorted numbers, where n = 1048576
Time to sort 1048576 sorted entries with Heapsort was 1015 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Starting a HeapSort with n reversed numbers, where n = 1048576
Time to sort 1048576 reversed entries with Heapsort was 886 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Starting a HeapSort with n shuffled numbers, where n = 1048576
Time to sort 1048576 shuffled entries with Heapsort was 1483 milliseconds.
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
Starting a QuickSort with n sorted numbers, where n = 1048576
Time to sort 1048576 sorted entries with QuickSort was 396 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 1048576]
[(524288): 524289]
[(1048576): 1]
Starting a QuickSort with n reversed numbers, where n = 1048576
Time to sort 1048576 reversed entries with QuickSort was 400 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]
...
Before sorting the array is:
[(1): 857704]
[(524288): 190051]
[(1048576): 792221]
Starting a QuickSort with n shuffled numbers, where n = 1048576
Time to sort 1048576 shuffled entries with QuickSort was 481 milliseconds.
After sorting the array is:
[(1): 1]
[(524288): 524288]
[(1048576): 1048576]