クイックソートを複数のアレイで使用できますか？

Question

私は配列を線形に索引付けできるが、フードの下に複数の配列を使用して実装されている、Cでの高性能な待機のないベクトル実装をC言語で実装しています。今私はこのベクトルをソートする必要があります。明らかに、私は配列が単一のブロブのメモリではないので、qsort()標準関数を使うことはできません。

それはこのように実装されていないが、60スロットベクトルは次のように定義されたことをふり：私は（たとえば59の範囲0で指定されたインデックスの値を変えることができ、簡単なインライン関数を有する

struct vector { 
    int *buckets[4]; 
}; 

struct vector v; 
v.buckets[0] = calloc(4, sizeof (int)); 
v.buckets[1] = calloc(8, sizeof (int)); 
v.buckets[2] = calloc(16, sizeof (int)); 
v.buckets[3] = calloc(32, sizeof (int)); 

getval(8)は、ベクターがは、それが直線的にを保存ないが、直線をインデックス化することもできる。することができますクイックソートbuckets[1][4]とgetval(9)は、だから、など

をbuckets[1][5]を返します返しますこのベクトルをソートするようになっていますか？そうでなければ、他のソートアルゴリズムを見てください。

Answer 1

getval(index)とsetval(index, value)の同等物を持っている限り、ソートアルゴリズム（クイックソートを含む）はほとんど機能します。

ただし、連続したデータが必要なので、qsortを標準ライブラリから使用することはできません。そのため、独自のソート関数をコーディングするか、間接参照のレベルを導入する必要があります。インデックスの配列を作成し、qsortを使用してソートし、その結果として得られたインデックスの並べ替えを基になる配列ストレージに適用します。

Answer 2

qsortは、要素の配列を必要とするため、問題には適していません。これを使って各サブアレイをソートすることはできますが、ベクター構造内でこれらをマージする方法が必要になります。 radixソートは直接適用できません。

上記以外にも、挿入やバブルソートなどの効率的でないメソッドとは別に、最も効率的なソート方法では、データセットのサイズに比例した余分なスペースが必要です。潜在的に大量のスペースを割り当てる場合は、別の配列を割り当てたり、内容をコピーしたり、radix_sort、qsortなどの方法で並べ替えたり、ソートした内容を元のベクター構造にコピーしたりするのが最も簡単な方法です。