ansaurus

Question

sort array of size n

Answer 1

+23 A:

Count the occurences of each number and afterward fill the array with the correct counts, this is O(n)

Andreas Brinck 2010-04-12 12:15:33

aka Counting Sort: http://en.wikipedia.org/wiki/Counting_sort

0xA3 2010-04-12 12:16:37

aka pigeonhole sort, aka radix sort.

roe 2010-04-12 12:18:20

@ Andreas the value of n may be quiet large so counting may be a bit troublesome in some cases

Grv 2010-04-12 12:23:18

@Grv Troublesome in what way? Like performance wise or that the count doesn't fit in an `int` or something?

Andreas Brinck 2010-04-12 12:25:03

@Grv: You're not going to get better than `O(n)` for sorting an array of size `n`.

Will Vousden 2010-04-12 12:26:10

@Andreas i was talking about the size of int in some compiler. if you use long int or others they may degrade performance, apart from that the solution is good cause i also think that it is the best complexity o(n)

Grv 2010-04-12 12:31:25

why would you use long int when you know the values are 0, 1 or 2?

jk 2010-04-12 12:37:37

@Will, One O(n) can be 100 times faster than another O(n).@Grv: No matter what sorting algorithm you use, you of course need to know if the array dimension fits in int.

PauliL 2010-04-12 13:00:35

@jk: the size of the ints used need to hold the counts, not the values 0, 1, or 2.

Michael Burr 2010-04-12 13:53:16

@PauliL: If the count of array elements exceeds the what will fit into a `size_t` variable, you'll likely have many more problems than figuring out a decent sort.

Michael Burr 2010-04-12 13:53:53

Answer 2

+2 A:

Sound's a lot like Dijkstra's Dutch National Flag Problem.

If you need a solution that doesn't use counting, check out http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

Gabe 2010-04-12 12:53:41

Answer 3

+2 A:

Untested C-style solution:

int count[3] = {0, 0, 0};

for (int i = 0; i < n; ++i)
    ++count[array[i]];

int pos = 0;
for (int c = 0; c < 3; ++c)
    for (int i = array[c]; i; --i)
        array[pos++] = c;

Fred 2010-04-12 15:53:42

`unsigned` or `size_t` would be more appropriate.

GMan 2010-04-12 17:36:48

Answer 4

+1 A:

Haskell two-liner:

count xs = Map.toList $ Map.fromListWith (+) [ (x, 1) | x <- xs ]

countingSort xs = concatMap ( \(x, n) -> replicate n x) (count xs)

> countingSort [2,0,2,1,2,2,1,0,2,1]
[0,0,1,1,1,2,2,2,2,2]

FredOverflow 2010-04-12 17:54:02

ansaurus

tags:

views:

answers:

sort array of size n

related questions