Ordering an array

[RuiLoureiro]

Anyone knows a procedure
to order an array of 1 200 000 positive integers (dwords) ?
It should do it in some milliseconds
Thanks

[dedndave]

i have seen a few examples Rui
try searching the forum for "quick sort", "quicksort", "bubble sort"

[cork]

Try a quicksort, merge sort or radix sort.

Don't bother with a bubble sort on such a large array.

[RuiLoureiro]

Hi dedndave,
            Thanks i got one from this forum
            MergeSort: a procedure written by Jing that is elsewhere here

Hi cork,
            The same, thanks.
            I used that MergeSort in my algo 2 to solve that problem you
            know and i got 3153 cases in 140 ms (very vary fast !).
            So your algo is not correct.
Jing,
             Thanks

[MichaelW]

A bubble sort should be OK for this, it's just a matter of scheduling. With a good implementation running on a fast system, if you started it in the evening, by the next morning it would be done.

[ecube]

A bubble sort should be OK for this, it's just a matter of scheduling. With a good implementation running on a fast system, if you started it in the evening, by the next morning it would be done.

you being serious?  :bg

[cork]

Actually, a merge sort is preposterously slow when you could just allocate 512 MB of data and flag the bits using a count sort. One pass and your set of 32-bit numbers is sorted. :dance:

[RuiLoureiro]

MichaelW,
            If you say !!!
            So "bubble sorts" is good to eat with cheese, no ?  :green

[Rockoon]

Actually, a merge sort is preposterously slow when you could just allocate 512 MB of data and flag the bits using a count sort. One pass and your set of 32-bit numbers is sorted. :dance:

Thats assuming counts of 0 or 1 only.

Such a counting sort isn't quite so simple on arbitrary 32-bit data and just can't be done in O(n) time without at least (log2(n) * 2^32) bits of memory. In this case he needs at least 21 bits per counter (n = 1.2 million, log2(n) = ~20.19) to handle the case where the entire array is the same value.

You are right that these sorts are incredibly fast when you can use them, but in practice they just dont apply to arbitrary 32-bit data yet (very few people are sporting 11 or more gigs of memory)

With that in mind tho, its very quick to test if the sort can be done with this linear time method (a single pass collecting minval and maxval) could easily reveal that more than enough memory is available.

[cork]

Actually, a merge sort is preposterously slow when you could just allocate 512 MB of data and flag the bits using a count sort. One pass and your set of 32-bit numbers is sorted. :dance:

Thats assuming counts of 0 or 1 only.

Such a counting sort isn't quite so simple on arbitrary 32-bit data and just can't be done in O(n) time without at least (log2(n) * 2^32) bits of memory. In this case he needs at least 21 bits per counter (n = 1.2 million, log2(n) = ~20.19) to handle the case where the entire array is the same value.

Good point about assuming counts of 0 or 1. If the numer of duplicates is limited to a known range, you can optimize based on that. The general case, as you pointed out, isn't that attractive for 32-bit numbers.

Actually, a merge sort is preposterously slow when you could just allocate 512 MB of data and flag the bits using a count sort. One pass and your set of 32-bit numbers is sorted. :dance:

You are right that these sorts are incredibly fast when you can use them, but in practice they just dont apply to arbitrary 32-bit data yet (very few people are sporting 11 or more gigs of memory)

With that in mind tho, its very quick to test if the sort can be done with this linear time method (a single pass collecting minval and maxval) could easily reveal that more than enough memory is available.

Here's another idea.

If we are sorting 32-bit numbers and you were to do a standard count sort on that data, you'd require 512 MB if you assume counts of 0 or 1 (1 bit per). You'd require 1 GB if you assume counts of 0-3 (2 bits per). You'd require 1 1/2 GB if you assume counts of 0-7 (3 bits per), you're require 2 GB if you assume counts of 0-15 (4 bits per), etc. If you assume counts between 0 and 255 you'd require the full 4 GB (8 bits per).

Keeping the above in mind...

A 32-bit number can be from 0 to 2^32 - 1.

Let's do a count sort on the numbers from 0 to 2147483647. Write those results out to the final array.
Then do a count sort on the numbers from 2147483648 - 4294967295. Wrote those results out to the final array.

Doing so requires 1/2 the memory of a standard count sort, but the 2 times the number of passes of a count sort.

If we were to do a count sort on the first quarter of the range, then the second quarter of the range, then the third quarter of the range, we'd require 1/4 the memory that a standard count sort would take, but it would make 4 times the number of passes that a count sort would make.

Assuming you have a list of 32-bit numbers having no duplicates, you would require 512 MB for a single pass count sort. If you wanted to use less memory you could use two pass method, cutting your memory requirements down to 256 MB. If you want to use even less memory you could use the four pass method, cutting your memory down to a quite reasonable 128 MB.

If you require X bits to hold your count (instead of just 1 bit as in my example above), then you'd multiply X by 256 MB for the two-pass method. You'd multiply X by 128 MB for the 4 pass method.

Two pass method memory requirements:
  256 MB for counts from 0-1 (1 bit each)
  512 MB for counts from 0-3 (2 bits each)
  768 MB for counts from 0-7 (3 bits each)
  etc.

Four pass method memory requirements:
  128 MB for counts from 0-1 (1 bit each)
  256 MB for counts from 0-3 (2 bits each)
  384 MB for counts from 0-7 (3-bits each)
  etc.

[cork]

Another idea...

A 32 bit number has the range from 0 to 4294967295.

Given an array of 32-bit numbers to sort, split the range in half, then write numbers in the range 0 - 2147483647 to the left side of the array, putting numbers in the range 2147483647 - 4294967295, on the right side of the array. Sort of like partitioning with quicksort, except you use 1/2 the range as your median instead an arbitrary 3-way median that is unsually utilized by quicksort.

You could just look at the left bit. If 0 put on the left side of the array. If 1 put the number on right side of array.

This "dividing the range in half" can be done in-place, in one pass, using the same method that quicksort does (working inward from each side).

Now take the part of the array corresponding to the first half of the range and do the same thing, splitting into 2 subarrays. Do the same for the second half of the range. Now you have 4 sub-arrays, accomplished in 2 passes, and partitioned, in-place requiring no extra memory.

Arrays:
A = first 1/4 of the 32-bit range
B = second 1/4 of the 32-bit range
C = third 1/4 of the 32-bit range
D = fourth 1/4 of the 32-bit range

Now do a count sort on each 1/4 of the range, requiring just 1/4 of the memory that a regular count sort would take.
  Count sort on A, then write to final array
  Count sort on B, then write to final array
  Count sort on C, then write to final array
  Count sort on D, then write to final array

You could take this one more level, splitting the range into eighths, requiring 3 passes through the data.
Then a count sort on each 8th, requiring just one more full pass. That is 4 passes, yet you only use 1/8th the memory of a standard count sort. Not a bad tradeoff between memory and time.

---

If you take this to the extreme you get a binary quicksort, which is like a radix sort using 2 as the radix, and just sorting in-place in the array. I terminated that after a 2 or 3 passes, then do a count sort on each partition which is crazy fast.

---

[RuiLoureiro]

Hi cork,
        I dont know the theory behind these methods.
        What is "count sort" ? Could you post an algo to do it ?
        Did you see the MergeSort written by Jing ?
        Thanks

[Rockoon]

Hi cork,
        I dont know the theory behind these methods.
        What is "count sort" ? Could you post an algo to do it ?
        Did you see the MergeSort written by Jing ?
        Thanks

You simply count the number of times each value appears, then with just the frequency counts for each value, you can generate a sorted list of values. You can also do other things with such frequency counts, such as produce a list of values that only appear N times... find the median value in O(n) time, etc..

[cork]

Hi cork,
        I dont know the theory behind these methods.
        What is "count sort" ? Could you post an algo to do it ?
        Did you see the MergeSort written by Jing ?
        Thanks

Let's say you have an input array of 1,000,000 numbers, and each of the numbers can be between 0 and 255.

Remember, the only numbers possible are from 0 to 255.

First you create an output array of 256 32-bit integers.

Next, loop through your input array of 1,000,000 numbers. If the number is 55 then you'd add 1 to the 55th element in the output array. If the number is 27, you add 1 to the 27th element of the output array.

It is usually called a "count sort" or a "distribution sort".

[RuiLoureiro]

Rockoon & Cork:

                Okay ! Thanks both
                I understood