実際に配列を再配置せずにマージソートを実行しようとしています。もう少しうまく説明しましょう。配列があるとします:
3
5
6
7
0
4
1
2
たとえば、5 (現在はインデックス 1) がインデックス 6 に移動された場合、5 が最初に格納された場所のインデックスをプログラムに記憶させる必要があります。元のインデックスを思い出すにはどうすればよいですか?
元の配列へのポインターの並列配列を作成します。オリジナルではなく、ポインターをソートします。インデックスの位置は変更されず、配列のソートされた「ビュー」が得られます。
できることは、すべての要素に構造体を使用し、それらの構造体オブジェクトの配列を作成することです。例えば-
typedef struct
{
int val;
int index;
}element;
配列をループし、valフィールドに値を入力し、もう一方のフィールドに元の位置を入力します。
並べ替えるときは、valフィールドで比較し、インデックスはそのままにします。これで元の位置が得られ、配列もソートできます。