Efficient Sorting Algorithm

Printable View

11-12-2008
GCNDoug

Efficient Sorting Algorithm

I am trying to come up with an efficient sorting algorithm to sort a set of values from 0 to 30,000. There are no duplicate numbers in the set, and I want to use as little memory requirements as possible.

This is just a logical problem and I can write it in psudocode or C, C++ doesn't matter. I just wanted to get your opinions on which algorithm you feel would probably be the best for these circumstances.

In my opinion I am thinking quick sort. What do others think?

unction quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
11-12-2008
laserlight

If space is your primary concern then perhaps heap sort will be the best. On the other hand, the additional space consumption by quick sort is not that much anyway, and it is typically faster than heap sort, and is probably the algorithm implemented for std::sort (or a variant, like introsort).
11-12-2008
Angus

Quote:

Originally Posted by laserlight

If space is your primary concern then perhaps heap sort will be the best. On the other hand, the additional space consumption by quick sort is not that much anyway, and it is typically faster than heap sort, and is probably the algorithm implemented for std::sort (or a variant, like introsort).

If space consumption of a quick sort is not that much, then of what sort algorithm is?

I agree, though, that a heap sort is probably best. It is in the same class as quick sort (O(n ln n)) and the memory overhead is very small.
11-12-2008
bling

Quote:

Originally Posted by laserlight

If space is your primary concern then perhaps heap sort will be the best. On the other hand, the additional space consumption by quick sort is not that much anyway, and it is typically faster than heap sort, and is probably the algorithm implemented for std::sort (or a variant, like introsort).

there are in-place version of the quick sort. in real-world quicksort completely destroys everything else. i haven't run into any library that doesn't use quicksort as the default implementation.
11-12-2008
bling

Quote:

Originally Posted by Angus

...I agree, though, that a heap sort is probably best. It is in the same class as quick sort (O(n ln n))....

i'm probably just nit-picking at this point. theoretically quick-sort's worst case is O(n^2), so if you go by that you would never choose qsort. but if you do some actual sorts on real data and compare the results, you'll see that quicksort is usually at least 5-10 times faster than other O(n log n) algorithms.
11-12-2008
cpjust

Quote:

Originally Posted by laserlight

If space is your primary concern then perhaps heap sort will be the best. On the other hand, the additional space consumption by quick sort is not that much anyway, and it is typically faster than heap sort, and is probably the algorithm implemented for std::sort (or a variant, like introsort).

Although, if you're going to use quick sort, you might as well use std::sort() since it can inline code and become a LOT faster than qsort().
11-12-2008
laserlight

Quote:

Originally Posted by bling

there are in-place version of the quick sort.

Are you sure? I had the impression that the best space consumption for quick sort takes extra space proportional to log n.
11-12-2008
bling

Quote:

Originally Posted by laserlight

Are you sure? I had the impression that the best space consumption for quick sort takes extra space proportional to log n.

yes, you're correct. i read the wikipedia article wrong. "There is a more complex version which uses an in-place partition algorithm and can achieve the complete sort using O(nlogn) space use on average"
11-12-2008
CornedBee

There seems to be no zero-overhead radix sort, which is a shame.
11-12-2008
iMalc

Quote:

Originally Posted by GCNDoug

I am trying to come up with an efficient sorting algorithm to sort a set of values from 0 to 30,000. There are no duplicate numbers in the set, and I want to use as little memory requirements as possible.

This is just a logical problem and I can write it in psudocode or C, C++ doesn't matter. I just wanted to get your opinions on which algorithm you feel would probably be the best for these circumstances.

In my opinion I am thinking quick sort. What do others think?

unction quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))

By "come up with" I assume you simply mean simply "choose". Many sorting algorithms are efficient (in one way or another). Some are efficient in terms of memory usage, some are efficient in terms of minimising the number of swaps, some are efficient in terms of minimising the number of comparisons, and many are efficient in terms of Big Oh Notation.
With no duplicates you can choose non-stable algorithms without worry, and if your keys are integers then that opens it up to possibilities like radix sort as well, and since it's an array rather than a list, you've got more options that way too.
Basically there are a huge number of options for this, QuickSort, IntroSort, HeapSort, ShellSort, CombSort etc are all reasonable options to name a few.
But hell, if you don't specifically need to code something yourself, and just want to get the job done, simply use std::sort.
11-13-2008
laserlight

Quote:

Originally Posted by iMalc

But hell, if you don't specifically need to code something yourself, and just want to get the job done, simply use std::sort.

That reminds me: if you do choose to use heap sort in the end, then make use of std::make_heap and std::sort_heap instead of implementing heap sort yourself.