Сортировка двумерного массива в O (n)

Question

Мне задали вопрос в интервью для сортировки массива двойного измерения в O (n) времени. Как это возможно сделать в O (n). Может кто-то пролил некоторые свет на этом .. спасибо.

Вход:

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

Выход

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

Answer 1

Вы можете сортировать как простой массив.
E.g.

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


int cmp(const void *a, const void *b){ 
    return *(int*)a - *(int*)b; 
} 

#define ROW_SIZE 3 
#define COL_SIZE 4 

int main(void){ 
    int M[ROW_SIZE][COL_SIZE]={{3,5,7,1},{4,9,2,0},{9,3,6,2}}; 
    int c,r,*p; 

    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){ 
     for(c=0;c<COL_SIZE;++c){ 
      printf("%d ",*p++); 
     } 
     printf("\n"); 
    } 
    printf("\n"); 
    qsort(&M[0][0], ROW_SIZE*COL_SIZE, sizeof(int), cmp); 
    for(p=&M[0][0],r=0;r<ROW_SIZE;++r){ 
     for(c=0;c<COL_SIZE;++c){ 
      printf("%d ",*p++); 
     } 
     printf("\n"); 
    } 

    return 0; 
} 

Answer 2

Не знаю, что вы на самом деле означает двойной массив размерности, но есть алгоритмы сортировки, специфичные для некоторых ситуаций, которые могут достичь O (п). Примером этого является Counting sort, если вы хотите отсортировать массив с 1000 целыми числами в диапазоне от 1 до 1000, он может сортировать в O (n).

EDIT: Тот факт, что это многомерный массив, не меняет логику сортировки. Вы можете преобразовать индекс (используя сортировку) на двумерный индекс, как это:

array[i/N][i % N]; 

где N является размером первого измерения.