要素の数をカウントできないソートアルゴリズム

Question

私は会社のインタビューでこの質問をテストしましたが、まず質問については明確ではありません。人々は私の疑いを明確にすることができますか？

質問：0、1、および2のみを含む整数配列をソートするプログラムを作成します。許可されていない要素を数えれば、O（n）時間の複雑さでそれを行うことが期待されます。

例アレイ：{2、0、1、2、1、2、1、0、2、0}

Answer 1

配列には値がほとんどないので、はの数だけ配列を再作成するために使用されます。また、値が0から連続しており、典型的なJavaのintループと一致するという事実を利用しています。

全体のソートアルゴリズムは、コードの3行のみが必要です。

public static void main(String[] args) 
{ 
    int[] array = { 2, 0, 1, 2, 1, 2, 1, 0, 2, 0 }; 

    // Line 1: Define some space to hold the totals 
    int[] counts = new int[3]; // To store the (3) different totals 

    // Line 2: Get the total of each type 
    for (int i : array) counts[i]++; 

    // Line 3: Write the appropriate number of each type consecutively back into the array: 
    for (int i = 0, start = 0; i < counts.length; start += counts[i++]) Arrays.fill(array, start, start + counts[i], i); 

    System.out.println(Arrays.toString(array)); 
} 

出力：なし時

[0, 0, 0, 1, 1, 1, 2, 2, 2, 2] 

たちはarray.lengthを参照していた、配列がいかに長くありませんケア。各要素を1回だけタッチして配列を反復し、必要に応じてこのアルゴリズムをO（n）にしました。

Answer 2

申し訳ありませんが、それはPHPの、それはO（N）と思われると容易とすることができますjavaで書かれています。

$arr = array(2, 0, 1, 2, 1, 2, 1, 0, 2, 0); 

$tmp = array(array(),array(),array()); 
foreach($arr as $i){ 
    $tmp[$i][] = $i; 
} 
print_r(array_merge($tmp[0],$tmp[1],$tmp[2])); 

Answer 3

「カウントが許可されていません」という意味に依存します。

これを行う簡単な方法は、新しい空の配列を作成し、次に0を探して新しい配列に追加することです。 1と2を繰り返し、O（n）時間でソートされます。

しかし、これは多かれ少なかれ基数的な並べ替えです。それは0を、次に1を、2を数えているようなので、これがあなたの基準に合っているかどうかはわかりません。

---

編集：私たちは、それぞれ0を交換し、0のための配列によってのみO（1）エクストラ（配列の先頭から始まる）当社の挿入ポイントのためのポインタを保持することによって、メモリ、およびスキャンでこれを行うことができますポインターがある場所の要素で、ポインターをインクリメントします。それから、1、2、そしてそれでもなおO（n）です。

Java実装：

import java.util.Arrays; 

public class Sort 
{ 
    public static void main(String[] args) 
    { 
     int[] array = {2, 0, 1, 2, 1, 2, 1, 0, 2, 0}; 
     sort(array); 
     System.out.println(Arrays.toString(array)); 
    } 

    public static void sort(int[] array) 
    { 
     int pointer = 0; 
     for(int i = 0; i < 3; i++) 
     { 
      for(int j = 0; j < array.length; j++) 
      { 
       if(array[j] == i) 
       { 
        int temp = array[pointer]; 
        array[pointer] = array[j]; 
        array[j] = temp; 
        pointer++; 
       } 
      } 
     } 
    } 
} 

出力を与える：

[0、0、0、1、1、1、2、2、2、2]

Answer 4

リンクリストに出力します。

• リストの先頭を覚えておいてください。
• 1秒が始まる位置を覚えておいてください。
• リストの最後を覚えておいてください。

アレイ全体を実行します。

• 0が発生した場合は、リンクリストの最初の位置に追加します。
• 1になった場合は、1の位置の後に追加します。
• 2に遭遇した場合は、リストの末尾に追加します。

HTH

楽

Answer 5

O（n）は、擬似コードで：

def sort (src): 
    # Create an empty array, and set pointer to its start. 

    def dest as array[sizeof src] 
    pto = 0 

    # For every possible value. 

    for val in 0, 1, 2: 
     # Check every position in the source. 

     for pfrom ranges from 0 to sizeof(src): 
      # And transfer if matching (includes update of dest pointer). 
      if src[pfrom] is val: 
       dest[pto] = val 
       pto = pto + 1 

    # Return the new array (or transfer it back to the source if desired). 

    return dest 

これは基本的に一致した場合に要素を追加し、ソースリスト上に三回反復されますこのパスで必要な値しかしそれはまだO（n）です。

同等のJavaコードは次のようになります。

出力

class Test { 
    public static int [] mySort (int [] src) { 
     int [] dest = new int[src.length]; 
     int pto = 0; 

     for (int val = 0; val < 3; val++) 
      for (int pfrom = 0; pfrom < src.length; pfrom++) 
       if (src[pfrom] == val) 
        dest[pto++] = val; 
     return dest; 
    } 

    public static void main(String args[]) { 
     int [] arr1 = {2, 0, 1, 2, 1, 2, 1, 0, 2, 0}; 
     int [] arr2 = mySort (arr1); 
     for (int i = 0; i < arr2.length; i++) 
      System.out.println ("Array[" + i + "] = " + arr2[i]); 
    } 
} 

：

Array[0] = 0 
Array[1] = 0 
Array[2] = 0 
Array[3] = 1 
Array[4] = 1 
Array[5] = 1 
Array[6] = 2 
Array[7] = 2 
Array[8] = 2 
Array[9] = 2 

---

しかし、潜在的な雇用主が私にこの質問を与えた場合には真剣に、私はそれから直線状態と思いますが私は彼らが望むならば質問に答えることができたが、正しい答えはArray.sortを使用することです。その場合、およびのみ、その方法と特定のデータセットでパフォーマンスの問題がある場合は、より高速な方法を調べることができます。

このように速い方法では、要件が何であるかにかかわらず、ほぼ確実に数えることになります。あなたは、開発者に恣意的な制限を課しているわけではありません。要件にはと指定する必要があります。は必須ではなく、です。

このように私にこの質問に答えた場合は、その場であなたを雇うでしょう。

Answer 6

この回答はではありません。は要素を数えます。

アレイには値がほとんどないので、各タイプの数がいくつあるかを数え、配列を再配置するために使用します。また、値が0から連続しており、典型的なJavaのintループと一致するという事実を利用しています。

public static void main(String[] args) throws Exception 
{ 
    Integer[] array = { 2, 0, 1, 2, 1, 2, 1, 0, 2, 0 }; 
    List<Integer>[] elements = new ArrayList[3]; // To store the different element types 

    // Initialize the array with new lists 
    for (int i = 0; i < elements.length; i++) elements[i] = new ArrayList<Integer>(); 

    // Populate the lists 
    for (int i : array) elements[i].add(i); 

    for (int i = 0, start = 0; i < elements.length; start += elements[i++].size()) 
     System.arraycopy(elements[i].toArray(), 0, array, start, elements[i].size()); 

    System.out.println(Arrays.toString(array)); 
} 

出力：

[0, 0, 0, 1, 1, 1, 2, 2, 2, 2] 

Answer 7

押し込み、一定の複雑さを持って引いて！

1. プッシュプライオリティキュー

2. に各要素（インデックス0に各要素を引い... N

：

Answer 8

あなたはca nは1回のパスでそれを行う、それを検出した各要素を配置することは、最終的な位置です：さらに別の理解不能な擬似コードであなたを爆破する代わりに

void sort012(int* array, int len) { 
    int* p0 = array; 
    int* p2 = array + len; 
    for (int* p = array; p <= p2;) { 
     if (*p == 0) { 
      std::swap(*p, *p0); 
      p0++; 
      p++; 
     } else if (*p == 2) { 
      std::swap(*p, *p2); 
      p2--; 
     } else { 
      p++; 
     } 
    } 
} 

Answer 9

、私はあなたに問題の名前をあげる：この問題が知られていますDutch national flag problem（最初はEdsgar Dijkstraによって提案されています）であり、3通りのマージによって解決できます（非常に非効率的ですが、これを解決する最初の答えのPHPコードを参照してください）。

3ウェイのより効率的な統合ソリューションは、BentleyとMcIlroyの論文「Engineering a Sort Function」に記載されています。これは、中央に並べ替えられていない値を、両端に1S、及び0及び2Sを有する中間体アレイ、の範囲を区切るために4つの指標を使用してイン間：

これを確立した後不変の場合、=部分（すなわち1）がスワップされて中央に戻されます。