-1

What is the fastest method to sort two dimensional array? I am creating an application in c++ language and I have a two dimensional string array to store state name and city name. I want to sort that array and display it to list quickly. so, it must be faster.

The declaration will be as follows.

std::string state[STATE_SIZE]
std::string city[STATE_SIZE][CITY_SIZE]

Result Should Look Like This

state[0] = "AAA";
state[1] = "BBB";

city[0][0] = "ABC";
city[0][1] = "PQR";
city[0][2] = "XYZ";
city[1][0] = "ADC";
city[1][1] = "GSF";
city[1][2] = "UHA";

the city array should be sorted by state then city.

I have also read these post. but it just for single dimensional array.

Which is the best Method used for Sorting?

What sort algorithm provides the best worst-case performance?

Community
  • 1
  • 1
Shell
  • 6,818
  • 11
  • 39
  • 70
  • Do you want to sort it by city or by state? What data structures are you using, how are they linked. Could you add a code example of your existing structure? Is performance really a problem, e.g is it a bottleneck in your application? – MatthiasB Feb 26 '14 at 09:44
  • @MatthiasBonora `String data[state,city]` I want to sort it by state then city. – Shell Feb 26 '14 at 09:46
  • @Nimesh This is not valid c++, do you mean `std::string data[STATE_SIZE][CITY_SIZE]` ? Or, more likly `std::pair data` ? – MatthiasB Feb 26 '14 at 09:49
  • @MatthiasBonora yes. it is std::string data[STATE_SIZE][CITY_SIZE] – Shell Feb 26 '14 at 09:54
  • @Socialz is it possible in c++? you have referenced me C# answer. – Shell Feb 26 '14 at 09:59
  • 1
    Ah, my apologizes. I found a topic on [**cplusplus**](http://www.cplusplus.com/forum/beginner/69717/) website, which has a nice little tip for sorting, called `std::sort` (via `algorithm.h`). [**Read more here >**](http://www.cplusplus.com/forum/beginner/69717/) – ascx Feb 26 '14 at 10:02
  • 1
    you could sort it with a binary tree, depending on the size of your data it might be the right choice. If it is only very little it doesn't really make sense to implement some monstrous algorithm you could just "normally sort" it by comparing the first and then the second row – okaerin Feb 26 '14 at 10:17
  • @thebaconing the record may be more than 30,000. Do you have any example or reference link of binary tree sorting example. – Shell Feb 26 '14 at 10:26
  • `std::string data[STATE_SIZE][CITY_SIZE]` seems very strange (what are `STATE_SIZE` and `CITY_SIZE` in your example ? Did you mean `std::string states[STATE_SIZE], cities[CITY_SIZE];` with `STATE_SIZE == CITY_SIZE`), a vector of custom struct seems more appropriate... Add initialization code. – Jarod42 Feb 26 '14 at 10:26
  • @Jarod42 No `STATE_SIZE` AND `CITY_SIZE` will not be equal. Above example is just for the reference. – Shell Feb 26 '14 at 10:28
  • 1
    So, you have something like `std::string data[STATE_SIZE/* 2 */][CITY_SIZE /* 3 */] = {{"ABC", "PQR", "XYZ"}, {"ADC", "GSF", "UHA"}};` ? And you want in fact sort each row ? – Jarod42 Feb 26 '14 at 10:42
  • Sorry my question was not proper to understand. so, i have updated it. – Shell Feb 26 '14 at 10:56

2 Answers2

1

The best for your problem (especially with the amount of 30000+ records) would be to implement an AVL tree (a self balancing binary). I'd suggest you read something on wikipedia or some other site on how they work (especially the AVL tree). To give you an idea how to implement i did a random google search : C implementation of an AVL tree

okaerin
  • 789
  • 5
  • 23
1

Following may help: https://ideone.com/OjIlz4

int main(int argc, char *argv[])
{
    constexpr int STATE_SIZE = 2;
    constexpr int CITY_SIZE = 3;

    std::string data[STATE_SIZE][CITY_SIZE] =
    {
        {"ABC", "XYZ", "PQR"},
        {"UHA", "ADC", "GSF"}
    };
    std::string states[STATE_SIZE] = {"AAA", "BBB"};

    for (int i = 0; i != STATE_SIZE; ++i) {
        std::sort(data[i], data[i] + CITY_SIZE);
    }

    for (int i = 0; i != STATE_SIZE; ++i) {
        std::cout << states[i] << std::endl;
        for (int j = 0; j != CITY_SIZE; ++j) {
            std::cout << "    " << data[i][j] << std::endl;
        }
    }

    return 0;
}
Jarod42
  • 203,559
  • 14
  • 181
  • 302
  • He mentioned that he plans to sort 30000+ row, won't it be slow with std::sort? – okaerin Feb 26 '14 at 12:01
  • @thebaconing: As I understand, OP will sort only once. So, it will be `O(n log n)` (as AVL tree, but more cache friendly). – Jarod42 Feb 26 '14 at 12:07