C++ std :: partial_sortに相当するC＃はありますか？

Question

私は多くの基準でソート可能なデータセットのページングアルゴリズムを実装しようとしています。残念ながら、これらの基準のいくつかはデータベースレベルで実装できますが、アプリケーションレベルで行う必要があります（別のデータソースと統合する必要があります）。ページング（実際には無限のスクロール）要件があり、すべてのページング呼び出しでアプリケーションレベルでデータセット全体をソートする際の苦痛を最小限に抑える方法を模索しています。

部分ソートを行う最良の方法は、ソートする必要がある部分のソートのみです。 .NETライブラリで利用できるC++のstd::partial_sort関数に相当するものはありますか？この問題を解決するにはどうすればよいですか？

EDITは：のは、私はいくつかの並べ替えの基準に従って、1000年要素集合の要素21-40を取得する必要がありましょう

：ここで私はのために行くよ何の例です。並べ替えを高速化するために、とにかく毎回データセット全体を処理しなければならないので（これはHTTP経由のステートレスWebサービスです）、データセット全体を並べる必要はありません。私は要素21-40が正しく注文されている必要があります。 3つのパーティションを作成すれば十分です。要素1-20、はソートされていません。（要素21より小さいすべて）。要素21-40,ソート;要素41-1000,はソートされていません（ただし要素40より大きいすべて）。

Answer 1

OK。私のコメントにあなたが言ったことに基づいて私が試してみたいことは次のとおりです。私は「第6回を通じて第4回」と言うと、何かを得ることができるようにしたい

：3、 2、1（ソートされていないが、適切な第四の要素よりも、すべての少ないです）。 4,5,6（ソート済み と同じ場所でソートされたリストになります）。 8、7、9 （ソートされていませんが、すべて6番目の適切な要素よりも大きい）。

はそれを容易にするために私たちのリストに10を追加できます：10、9、8、7、6、5、4、3、2、1

だから、何を行う可能性は使用していますquick select algorithmを検索して、i ^thおよびk ^th要素を検索します。あなたのケースでは、私は4であり、kは6です。もちろん、値4と6を返します。それはあなたのリストを2回通過するでしょう。だから、ランタイムはO（2n）= O（n）です。もちろん、次の部分は簡単です。私たちが気にするデータについては、下限と上限があります。私たちがする必要があるのは、上下限の間にある要素を探すリストをもう一度通すことだけです。このような要素が見つかると、それを新しいListに投げます。最後に、私たちが気にする要素を^thからk ^thに変更したリストを並べ替えます。

だから、私は合計ランタイムはO（N）+ O（（KI）、LG（KI））

static void Main(string[] args) { 
    //create an array of 10 million items that are randomly ordered 
    var list = Enumerable.Range(1, 10000000).OrderBy(x => Guid.NewGuid()).ToList(); 

    var sw = Stopwatch.StartNew(); 
    var slowOrder = list.OrderBy(x => x).Skip(10).Take(10).ToList(); 
    sw.Stop(); 
    Console.WriteLine(sw.ElapsedMilliseconds); 
    //Took ~8 seconds on my machine 

    sw.Restart(); 
    var smallVal = Quickselect(list, 11); 
    var largeVal = Quickselect(list, 20); 
    var elements = list.Where(el => el >= smallVal && el <= largeVal).OrderBy(el => el); 
    Console.WriteLine(sw.ElapsedMilliseconds); 
    //Took ~1 second on my machine 
} 

public static T Quickselect<T>(IList<T> list , int k) where T : IComparable { 
    Random rand = new Random(); 
    int r = rand.Next(0, list.Count); 
    T pivot = list[r]; 
    List<T> smaller = new List<T>(); 
    List<T> larger = new List<T>(); 
    foreach (T element in list) { 
     var comparison = element.CompareTo(pivot); 
     if (comparison == -1) { 
      smaller.Add(element); 
     } 
     else if (comparison == 1) { 
      larger.Add(element); 
     } 
    } 

    if (k <= smaller.Count) { 
     return Quickselect(smaller, k); 
    } 
    else if (k > list.Count - larger.Count) { 
     return Quickselect(larger, k - (list.Count - larger.Count)); 
    } 
    else { 
     return pivot; 
    } 
} 

Answer 2

あなたはList<T>.Sort(int, int, IComparer<T>)を使用することができます。

inputList.Sort(startIndex, count, Comparer<T>.Default); 

Answer 3

Array.Sort()あなたは、配列のサブセットを並べ替えることができますindexとlengthの引数を受け取るオーバーロードがあります。 Listについても同じです。

IEnumerableを直接ソートすることはできません。