c# - 要素を比較せずに並べ替える

Question

配列 5 の指定されたサイズに 5 つの数値が含まれている場合、比較せずに最小から最大の順に並べ替えます (ヒント、アクセス時間 O(n)

私はたくさん検索しようとしましたが、どうすればできるのかわかりませんでした。O(n) は、どのアルゴリズム/データ構造かを意味します。私は知りません。

Answer 1

Counting sortが必要だと思います。線形時間はありますが、メモリが必要で、初期配列の最小/最大値に依存します

Answer 2

カウンティングソートはあなたのためにこれを行いますが、私がインタビューを受けてその場にいたら、おそらく以下のようなことをするでしょう.

ここでの重要なアイデアは、N が最大である N 個の要素を含むターゲット配列へのインデックスとして、実際の並べ替えられていない整数値をそれぞれ使用することです。並べ替える値の。

元の配列で複数回発生した離散値を保持する必要がある場合は、単純なクラスを使用して値と発生回数の両方を記録しているため、実際の配列を再構築できます。

したがって、並べ替えられていない配列を 1 回ウォークし、各値をターゲット配列の対応するインデックスに入れるだけで、(空の要素は無視して) 値を互いに比較することなく、最小から最大の順に並べ替えることができます。

(私は個人的に、このような答えが「ああ、Counting Sort を使用してください」などのインタビューの質問のファンではありません。この質問をするインタビュアーが、新しい問題を解決するためにどのようなアプローチをとったかを知りたいと心から願っています。 、厳密に正解したかどうかに関係なく）

以下のパフォーマンスは O(n) であり、線形時間で実行されることを意味します (1 要素には X の時間がかかり、10 要素には 10 倍の時間がかかります) が、最大要素が大きい場合は多くのメモリを使用できます。場所の並べ替えは、プリミティブでのみ機能し、本番コードで見たいとは思わないものです:)

void Main()
{
   //create unsorted list of random numbers
    var unsorted = new List<int>();
    Random rand = new Random();
    for(int x=0;x<10;x++)
    {
     unsorted.Add(rand.Next(1,10));
    }
    //create array big enough to hold unsorted.Max() elements
    //note this is indirectly performing a comparison of the elements of the array
    //but not for the sorting, so I guess that is allowable :)
    var sorted = new NumberCount[unsorted.Max()+1];
    //loop the unsorted array 
    for (int index=0;index<unsorted.Count;index++)
    {
   //get the value at the current index and use as an index to the target array
        var value = unsorted[index];
        //if the sorted array contains the value at the current index, just increment the count
        if (sorted[value]!=null && sorted[value].Value!=0)
        {
           sorted[value].Count++;
        }
        else
        {
        //insert the current value in it's index position
         sorted[value]=new NumberCount{Value=value,Count=1};          
        }
    }
    //ignore all elements in sorted that are null because they were not part of the original list of numbers.
    foreach (var r in sorted.Where(r=>r!=null))
    {
       Console.WriteLine("{0}, occurs {1} times",r.Value,r.Count);
    }
}

//just a poco to hold the numbers and the number of times they occurred.
public class NumberCount
{
  public int Value{get;set;}
  public int Count{get;set;}
}