Сортировка массива на основе набора из 4 индексов в C

Question

У меня есть интересная проблема, с которой я боролся в течение последних 2 дней без конкретного решения. Я пытаюсь написать программу в C, который принимает следующий входной массив:

   1,1,5,5, 
       1,1,5,9, 
       2,2,6,2, 
       1,2,5,5, 
       1,3,6,6, 
       1,4,5,1, 
       4,1,5,6, 
       5,2,7,1, 
       1,1,6,0, 
       2,2,5,0, 

Шаг 1: группа выше массив на основе 3-го столбца, как это (ведро рода на кортеж из 4 элементов (т.е. каждая строка) , основываясь на значениях 3 колонки:

   2,2,5,5 
       1,1,5,9, 
       1,2,5,5, 
       1,4,5,1, 
       4,1,5,6, 
       2,2,5,0, 
       2,2,6,2, 
       1,3,6,6, 
       1,1,6,0, 
       5,2,7,1 

Шаг 2: Наконец сортировать элементы, основанные на 4-м столбце в каждом сегменте, как это:

Окончательный выход массива:

   2,2,5,0, 
       1,4,5,1, 
       2,2,5,5, 
       1,2,5,5, 
       4,1,5,6, 
       1,1,5,9, 
       1,1,6,0, 
       2,2,6,2, 
       1,3,6,6, 
       5,2,7,1 

Элементы в 1-й и 2-й колонках не играют никакой роли в вышеуказанном процессе сортировки.

Я пробовал различные методы, используя сортировку quicksort или bucket, а затем последующую quicksort. Ничего не получилось совершенно правильно. Может ли кто-нибудь предложить метод выполнения этого в C, используя соответствующие структуры данных.

Answer 1

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

int cmp(const void *x, const void *y){ 
    int (*a)[4] = (int(*)[4])x; 
    int (*b)[4] = (int(*)[4])y; 
    if((*a)[2]==(*b)[2]) 
     return (*a)[3] - (*b)[3]; 
    else 
     return (*a)[2] - (*b)[2]; 
} 

int main(void){ 
    int data[][4] = { 
     {1,1,5,5}, 
     {1,1,5,9}, 
     {2,2,6,2}, 
     {1,2,5,5}, 
     {1,3,6,6}, 
     {1,4,5,1}, 
     {4,1,5,6}, 
     {5,2,7,1}, 
     {1,1,6,0}, 
     {2,2,5,0} 
    }; 
    int size = sizeof(data)/sizeof(data[0]); 
    int i,j; 
    qsort(data, size, sizeof(data[0]), cmp); 
    //result print 
    for(i=0;i<size;++i){ 
     for(j=0;j<4;++j) 
      printf("%d ", data[i][j]); 
     printf("\n"); 
    } 
    return 0; 
} 

Answer 2

Дело в том, что вам не нужно делать несколько сортов; вы можете сделать одиночный сорт, основанный на двух полях вашего кортежа.

Просто используйте существующий алгоритм сортировки, но с сравнивая функции, которая выглядит следующим образом:

if (val[2] != otherval[2]) 
    return val[2] < otherval[2]; 
else 
    return val[3] < otherval[3]; 

Это будет использовать третий столбец для сортировки, если значения не равны, в этом случае он будет использовать четвёртый.

Или, если вы хотите сделать два отдельных вида, ПЕРВЫЙ вид по четвертой колонке, ТОГДА третий.

Answer 3

Это должно быть довольно просто. Стандартная функция qsort выполняет обратный вызов, который сравнивает два элемента. Просто напишите свой обратный вызов, чтобы ожидать, что элементы будут подмассивами и сначала сравните с помощью третьего элемента. Если третьи элементы равны, сравните с помощью четвертого элемента.