Sắp xếp một mảng dựa trên các thành viên của mảng khác trong C++

Question

vấn đề của tôi là tiếp theo (là một ví dụ đơn giản để hiển thị các vấn đề):

tôi có:

int* array1; 
double* array2. 

array1=new int[10]; 
array2=new double[10]; 
array1=filledWithIntegers(random); 
array2=filledWithDoubles(random); 

// Ở đây tôi muốn sắp xếp mảng1 dựa trên giá trị mảng2. Tôi đang cố gắng sử dụng chức năng qsort của stdlib. qsort (mảng1,6, sizeof (int), so sánh);

Điểm chính là cách thực hiện hàm so sánh cho mảng thứ tự1 dựa trên mảng2.

Không thể sử dụng cấu trúc dữ liệu thư viện std, nó phải được thực hiện trực tiếp trong các con trỏ mảng.

Cảm ơn.

Answer 1

Thay vì sắp xếp các số nguyên array1, sắp xếp các chỉ số của họ sử dụng array2[index] để so sánh các mặt hàng, và sau đó sắp xếp lại array1 phù hợp với các hoán vị mà bạn nhận được trở lại từ sắp xếp.

Đây là một quick demo:

#include <stdio.h> 
#include <stdlib.h> 

int array1[] = {1, 7, 3, 9, 5}; 
double array2[] = {1.1, 7.7, 3.3, 9.9, 5.5}; 

int compare (const void * a, const void * b) { 
    double diff = array2[*(int*)a] - array2[*(int*)b]; 
    return (0 < diff) - (diff < 0); 
} 

int main(void) { 
    int perm[5], i; 
    int res[5]; 
    for (i = 0 ; i != 5 ; i++) { 
     perm[i] = i; 
    } 
    qsort (perm, 5, sizeof(int), compare); 
    for (i = 0 ; i != 5 ; i++) { 
     res[i] = array1[perm[i]]; 
    } 
    for (i = 0 ; i != 5 ; i++) { 
     printf("%d\n", res[i]); 
    } 
    return 0; 
} 

Answer 2

có. Bạn cần nhóm hai mảng vào một mảng của cặp, và sau đó xác định hàm so sánh.

sự so sánh chức năng có thể là:

bool compare(const pair<int,double>& t1, const pair<int,double>& t2){ 
    return (t1.second < t2.second); 
} 

Answer 3

Vâng, bạn chỉ cần sử dụng vị trí của các yếu tố đến chỉ số mảng khác trong chức năng so sánh của bạn (đảm bảo tiêu chuẩn mà các đối số con trỏ của hàm so sánh luôn chỉ vào mảng được sắp xếp):

int compare(const void *a, const void *b) 
{ 
    unsigned int i = (const int*)a - array1; 
    unsigned int j = (const int*)b - array1; 
    if(array2[i] < array2[j]) 
     return -1; 
    if(array2[i] > array2[j]) 
     return 1; 
    return 0; 
} 

Điều bất lợi là hàm so sánh cần biết rõ các tham số bổ sung.

Tôi sẽ đặt câu hỏi về việc sử dụng qsort dù sao, vì câu hỏi của bạn được gắn thẻ C++. Mặc dù std::sort có cùng một vấn đề, bạn có thể tiếp cận nhiều hơn nữa tính tổng quát/trừu tượng bằng cách sử dụng một hàm so sánh đóng gói các mảng phụ thuộc.