-2

I have a 2D array with 2 rows and it has very large numbers (upto 10^9) in it. I am trying to sort the array based on 0th row.

Eg : I have an array : A[5][2]={{1,0},{3,1},{2,2},{6,3},{5,4}} where 2nd row is index of the element.

Now I want to sort the array with retaining the original index.

After sorting A should be:

 A[5][2]={{1,0},{2,2},{3,1},{5,4},{6,3}}

I did the following :

long long a[n+1][2];

    for (long long i = 0; i < n; i++) 
    {
        cin>>a[i][0];
        a[i][1]=i;
    }



    qsort(a, n, sizeof a[0], compare);

And the compare function is :

int compare ( const void *pa,const void *pb )
{
    int *a = (int*)pa;
    int *b = (int*)pb;
    if(a[0] == b[0])
        return a[1] - b[1];
    else
        return a[0] - b[0];
}

It is working for small values of numbers. For large values,I am getting runtime error (SIGSEGV).

Can someone help in correcting the error ? Or is there a more efficient way to do this ?

Note : I had tried long long in compare function but it was giving conversion error.
error: invalid conversion from 'll (*)(const void*, const void*) {aka long long int (*)(const void*, const void*)}' to '__compar_fn_t {aka int (*)(const void*, const void*)}' [-fpermissive]

EDIT : Actually I could work away with only the index after sorting.

Buckster
  • 41
  • 12
  • 1
    Maybe because you mix `long long` and `int`? –  Jan 07 '17 at 20:16
  • Just want to notice that's better to use size_t instead of long long in the for-loop. – realvictorprm Jan 07 '17 at 20:17
  • Show the conversion error. –  Jan 07 '17 at 20:18
  • 2
    Might be better off tagging this question as C as you are using a lot of C and no C++ – user4581301 Jan 07 '17 at 20:23
  • @MichaelO. I had everything in `long long` – Buckster Jan 07 '17 at 20:23
  • @user4581301 the rest of the code of my program is in C++ only. I wanted to use it with C++ STL sort as it is faster but it wasn't compatible. – Buckster Jan 07 '17 at 20:24
  • 1
    @Buckster Why isn't `std::sort` compatible? Maybe you are not aware how to use it correctly. – PaulMcKenzie Jan 07 '17 at 20:39
  • @PaulMcKenzie I tried using compare function but it was throwing errors. – Buckster Jan 07 '17 at 20:44
  • 1
    @Buckster Whatever `qsort` can do, `std::sort` can do, and do it much better. You tagged this question as `C++`, and usage of `qsort` in a C++ program is not recommended. – PaulMcKenzie Jan 07 '17 at 20:50
  • @Buckster, qsort cannot sort 2 dimensional arrays in the way you want to – realvictorprm Jan 07 '17 at 20:53
  • 1
    @Buckster Fix your array declaration (you have your rows and columns mixed up). In addition, you use parentheses where you should be using curly braces to initialize the array. – PaulMcKenzie Jan 07 '17 at 20:56
  • @PaulMcKenzie Then can you please tell me how to use it. I tried using `std::sort(a,a+n,compare);` – Buckster Jan 07 '17 at 20:59
  • @PaulMcKenzie It was just for example. The array input is given by user. – Buckster Jan 07 '17 at 21:01
  • @Buckster First, why are you sorting the first row in addition to reindexing the second row? There is no need to sort the first row -- keep it the same, as the second row indexes the first row. The only row that you should be changing is the second. – PaulMcKenzie Jan 07 '17 at 21:02
  • @PaulMcKenzie How would I sort the the second row on basis of first row ? If you have a working code, please tell me. Thanks in advance. – Buckster Jan 07 '17 at 21:10
  • I posted an answer with an example. – PaulMcKenzie Jan 07 '17 at 21:14
  • 2
    Possible duplicate of [Sort a 2D array in C++ using built in functions(or any other method)?](http://stackoverflow.com/questions/20931669/sort-a-2d-array-in-c-using-built-in-functionsor-any-other-method) – PeterSW Jan 07 '17 at 21:26
  • @PeterSW thanks for referencing that. After the question has been edited it's clearly a duplicate – realvictorprm Jan 08 '17 at 00:05

2 Answers2

2

First, your array is declared incorrectly (the sample code below shows the correct declaration).

Second, I would recommend leaving the first row alone, and only sort the second row of indices. Since the second row is being used as the indexer, there is no need to sort the first row.

Third, using qsort in a C++ is not recommended.

  1. qsort is not typesafe. You have to cast void pointers to the types that you are sorting with qsort. If the cast is done incorrectly, then your program has runtime issues.
  2. qsort cannot be used on non-POD types (anything that isn't C compatible).
  3. C++ compiler optimizers do a much better job optimizing for speed std::sort than qsort.
  4. std::sort is just plain easier to use.

Here is a working example:

#include <algorithm>
#include <iostream>

int main()
{
    int A[2][5] = { {1,3,2,6,5},{0,1,2,3,4} };

    // sort the index row, not the "data" row
    std::sort(A[1], A[1] + 5, 
              [&](int n1, int n2){ return A[0][n1] < A[0][n2]; });

    // output results
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 5; ++j)
        {
            if (i == 0)  // if this is a data row
                std::cout << A[i][A[1][j]] << " ";
            else // this is an index row
                std::cout << A[i][j] << " ";
        }
        std::cout << "\n";
    }
}

Live Example

The std::sort works on the second row, not the first row. Then the compare lambda sorts the second row based on the data in the first row.

The output loop shows how to index the first row, given the second row. For example, to get the sorted third number in the first row:

A[0][A[1][2]]

Since A[1][2] is the index of the third sorted number, the third sorted number is A[0][A[1][2]]

Edit:

If you are trying to use a dynamic two dimensional array, then use std::vector, as this example shows

PaulMcKenzie
  • 34,698
  • 4
  • 24
  • 45
  • http://ideone.com/8c7w1K : I tried it with user driven input. There is compilation error on comparison function. – Buckster Jan 07 '17 at 22:04
  • `long long int a[2][n+1];` -- This is not valid C++. You cannot use variables to define the array's size. You are giving `std::sort` things that are not real C++, which is why the error mentions "N3639". Dynamic arrays in C++ are done using `std::vector`. – PaulMcKenzie Jan 07 '17 at 22:06
  • @Buckster Please see my edit and the link to code using the vector. – PaulMcKenzie Jan 07 '17 at 22:41
-1

I don't know the purpose, so I can be wrong, but maybe you should use structure or class with two fields: index and number, overload <, <=, ==, >, >= operators and use array of objects, and just use sort method.

Тарас Федак
  • 1
  • 1