sorting large numbers

What do the numbers represent? What will they be used for? What kind of structure are they stored in (linked list, vector, etc)?

The more high-level information you can provide about the situation, the better we'll be able to help you.

Radix sort and quick sort are the fastest algorithms I know of but which one the fastest is depends on many things (what Extrarius said) Usually hybrid algorithms are faster, but more complex.

Quote:

Original post by Extrarius What do the numbers represent? What will they be used for? What kind of structure are they stored in (linked list, vector, etc)? The more high-level information you can provide about the situation, the better we'll be able to help you.

The numbers do not represent anything in particular (they are just large numbers). =) The container used is not specified, so I guess a standard array would do it.

Sounds like a clear cut quicksort case, especially if your list is reasonably short. Radix sort is O(n * k) where k is the number of digits, and big numbers obviously has a lot of digits. Implementations of radix sort already have big constant factors, and multiplying them by a big k doesn't seem to be the way to go.

Actually it depends. If you're using radix bit sort then it depends on how many bits there are (32 usually, or 16 or 64...) But ye qsort is probably gonna be faster. You could hash sort it then qsort... basically switch it up a bit so it's as fast as possible :) (which algo to use at which place in the sorting depends)

Quote:

Original post by Joakim_ar Sounds like a clear cut quicksort case, especially if your list is reasonably short. Radix sort is O(n * k) where k is the number of digits, and big numbers obviously has a lot of digits. Implementations of radix sort already have big constant factors, and multiplying them by a big k doesn't seem to be the way to go.

I think your definitly right.

Thanks for the input, guys! I think i'll go with a quicksort for this one.

I don't know much about sort algorithms (bubble sort is my limit [smile]) but I would have thought that if you don't care about the type of container, it might be more efficient to use a container that maintains sorted order on insertion, like a binary tree or whatever, rather than waiting till the list is assembled then sorting it.

Just a thought on a subject I know very little about.

If I have a very long list of 16-bit values instead, would a radix sort be better?

Quote:

Original post by EasilyConfused (...) if you don't care about the type of container, it might be more efficient to use a container that maintains sorted order on insertion (...)

Quote:

Original post by Extrarius What do the numbers represent? What will they be used for? What kind of structure are they stored in (linked list, vector, etc)?

Each algorithm has been design for a particular purpose. If you're sorting entities equaly distributed against a specified range, you might prefer radix and its derivatives (I know of "byte-sort" if you're interested.) Totally random sets are best sorted with quick-sort.

Quote:

Original post by DarkZoulz If I have a very long list of 16-bit values instead, would a radix sort be better?

I made a graph. Apparently, the answer to your question is no.



The bottom is the number of elements. The side is the number of comparisons. Radix sort is using 16 bit values.

How do you calculate the number of comparisons for radix sort (considering it's not a comparison-based sort)?

Quote:

Original post by Extrarius How do you calculate the number of comparisons for radix sort (considering it's not a comparison-based sort)?

Yeah, i'd like to know that too :) I've actually tested both a very fast qsort (30% faster than standard c qsort) against a radix count sort, and the radix count sort came out on top for 32 bits. This is because the compiler can optimize it because they consist of simple loops. For 16 bits, radix count sort will be twice as fast.

Greetings.

EDIT: I posted my source on my site. Here are the links for my fast qsort (it doesn't use swaps), and my int32 radix count sort. I also have a radix count sort for signed floating points, if someone would be interested.

QuickSort
RadixCountSort

Limitz, ye I'm interested :) How'd you do that? All I know how to do is a bit sort. (and you don't wanna use bit ops to sort float data)

Quote:

Original post by biscuitz Limitz, ye I'm interested :) How'd you do that? All I know how to do is a bit sort. (and you don't wanna use bit ops to sort float data)

If you look at the bit structure of a float you will see that if you union it with an UINT then union->FLOAT < union2->FLOAT <=> union->UINT < union->UINT... except for the signs.

Now to get the signs right i figured this out:

lets say:

typedef union {	float 		FLOAT;	unsigned int	UINT;	unsigned char BYTE[4];} xfloat;

now i would do an encoding pass, to xor the bits in negative numbers so they will get sorted high to low, and lose the sign bit. And i will add the sign bit to all positive numbers, so they will be higher than the negative numbers.

void negXorEncode(xfloat *base, int len){	register int i=0;	register unsigned int* fp;	register xfloat* xf;	xf = base;	for (i=0; i<len; i++, xf++)	{		fp = &(xf->UINT);		if (*fp & 0x80000000) *fp ^= 0xFFFFFFFF;		else *fp |= 0x80000000;	}}

Now we'd call radix count sort and after that's done the encoded floats are in their right place and we just need to decode them.

void negXorDecode(xfloat *base, int len){	register int i=0;	register unsigned int* fp;	register xfloat* xf;	xf = base;	for (i=0; i<len; i++, xf++)	{		fp = &(xf->UINT);		if (*fp & 0x80000000) *fp &= 0x7FFFFFFF;		else *fp ^= 0xFFFFFFFF;	}}

Now the floats are sorted.

So by just adding 1 loop over n elems before the sort and 1 after we sort signed floats fast and still maintain O(n);

Sorry for the lack of readbility, but the pointers make it another few percent faster ;)

I figured this out myself, has anyone seen a better method?

Greetings.

Besides, graphs like that are rather meaningless unless they are based on real-world test data. The algorithms (and indeed, different implementations of the same algorithm) have completely different constant factors which are not reflected in their big-Oh complexity.

std::sort.

Oh, you meant 'fastest' in terms of computer time rather than programmer time?

std::sort. Unless you "know something" about the data, which you clearly don't here ("the numbers are big" is not information that can help you sort them; if anything, it's an indication that a radix sort might be a bad idea), or think you can write something better than your compiler vendors can (in which case, (a) you shouldn't have to be posting on forums asking something like this, and (b) why aren't you working for them instead?).

Quote:

Original post by Sharlin Besides, graphs like that are rather meaningless unless they are based on real-world test data. The algorithms (and indeed, different implementations of the same algorithm) have completely different constant factors which are not reflected in their big-Oh complexity.

That's true i can only say for that matter that with my random dataset my implementation of radix count sort beat my implementation of quick sort.
However, if you take a large enough number O(n) will eventually beat O(n lg n). But the number of elements could be HUGE before you will see an increase in performance.

And then you still have to keep in mind that some implementations are more easily optimized by the compiler than others (the for loops in radix count are way faster than the recursive calls made by qsort). O was made to look at an algorithm from a standpoint that doesn't take into account the time it will take for the processor to perform the instruction.

Greetings.

Quote:

Original post by Zahlman std::sort. Oh, you meant 'fastest' in terms of computer time rather than programmer time? std::sort. Unless you "know something" about the data, which you clearly don't here ("the numbers are big" is not information that can help you sort them; if anything, it's an indication that a radix sort might be a bad idea), or think you can write something better than your compiler vendors can (in which case, (a) you shouldn't have to be posting on forums asking something like this, and (b) why aren't you working for them instead?).

I usually get my sorters to run faster then my compiler's. (Or is MingW just crap? Never tested in with MS compiler though). ;)

I think you can always go faster, for instance: Do you have a sort function for each type? qsort asks for void* and element_size and a function pointer, which are things you can do without if you create your own. Reduce function calls and calculations to cast void* into your type.

std::sort takes its (optional) ordering function object as a template parameter, which allows it to be fully inlined. As a result std::sort usually outperforms qsort by a margin, probably the same margin you're managing to outperform it by.

Σnigma