Reputation: 111

Looking for the fastest way to sort a list of 2000 items long consisting of three different values in C++

Basically the program will be given a list of items and they have to be sorted into three different "bins." Think of it as if you were sorting three colors of marbles. The items are all of type char. thanks for the help.

Upvotes: 1

Answers (5)

Benjamin Lindley

Reputation: 103713

Another option would be two calls to partition:

vector<char> v(2000);
...
std::partition(
    std::partition(
        v.begin(),
        v.end(),
        function_to_match_first_value()),
    v3.end(),
    function_to_match_second_value());

Upvotes: 3

Mark B

Reputation: 96261

I think this is perfect for bucket sort: Basically create a list of 256 int counts and each time you encounter a value in your list, increment the count for that value. Then iterate over the counts to put them back in order. This is O(n).

Upvotes: 3

Konrad Rudolph

Reputation: 545638

This isn’t really a classical “sorting” problem … since there are only a fixed number of possible values, this is known as a partitioning problem and there exists an efficient solution for the three-ways partition known as the Dutch flag sort, first proposed by Edsger Dijkstra.

This algorithm runs in O(n) and needs only a single pass over the array.

The algorithm can also be found rather trivially by developing the loop invariant.

Upvotes: 11