c - 2D マトリックスをソートする方法

Question

インタビューでこんな質問をされました。乱数の 2D 配列 (数値は繰り返すことができます) が与えられ、それらを行と列の両方で並べ替える必要があります。つまり、すべての行と列を並べ替える必要があります。誰でもそれを効率的に行う方法を説明してもらえますか(時間とスペースの複雑さを最小限に抑えてください)。CまたはC++でコードを提供できる場合、それは本当に役に立ちます

Answer 1

これを使用して適応させてみてください...

void sort(int MyArray[8][8])
{
     for(int ir=0;ir<8;ir++)
     {
        for(int ic=0;ic<8;ic++)
        {
            for(int jr=0;jr<8;jr++)  
            {
                    for(int jc=0;jc<8;jc++)
                    {        
                      if(MyArray[ir][jr]>MyArray[ic][jc])
                       {
                         int temp=MyArray[ir][jr];
                         MyArray[ir][jr]=MyArray[ic][jc];
                         MyArray[ic][jc]=temp;
                       }
                    }
             }
        }
     }
}

単純なバブルソートです。O(n^4) で効果的に実行されます。クイックソートなどのアルゴリズムを作成すると、より効果的になります。2D 配列でクイックソートを試みるのを見たことがなく、考えたことさえありません。簡単なことではありません。試すことができるのは、すべてを単一の配列に追加し、それをクイックソートして、すべてを 2D 配列にコピーすることです。しかし、配列はより効果的になる前に非常に大きくする必要があります...誰かがここで2D配列のクイックソートまたはマージソートアルゴリズムを提供した場合。彼はメダルに値する！それはハードコアです