アレイがある場合はO（n）でソートする動作

Question

最悪の場合実行時間O(n)で配列をソートすることができます。配列にはk ∈ ℕ>0（kは定数）の異なる要素のみが含まれていますか？

n要素を持つ配列を比較するには一定の時間が必要であると仮定します。

まず最初に、タスクを理解したいと思います。 私はその前提を理解しています。しかし、正確に何を意味するのですかk ∈ ℕ>0（kは定数です）異なる要素？

これは、配列があり、そのサイズがkであり、と書かれているので、配列のサイズは0にできませんか？あれは正しいですか？ もしそうなら、私はなぜ彼らがn要素ではなく配列と言うだけではないのかよく分かりません。

とにかく、それは私がそれを理解する方法だと私たちは、ソート/基数ソートなどをバケツを見てみるならば、それはO(n*logn)に行うことができるので、それは時間O(n)を実行し、最悪の場合には、この配列をソートすることはできませんと言うでしょう。

Answer 1

値を知っていれば、数値を「バケット」に入れて並べ替えることができます。それぞれの値に対して、バケットを作成し、そのバケットに反復処理を行うときにそのバケットに番号を追加します。

public class SortInBucket { 
    public static void main(String[] args) { 
     int[] x = {0,5,1,1,1,1,7,9,3,2,1,2,5,6}; 
     System.out.println("Result of sorting: " + Arrays.toString(sortInBuckets(x))); 
    } 

    public static int[] sortInBuckets(int[] arr) { 
     List<List<Integer>> sortedNumbers = new ArrayList<>(); 
     int[] sortedArr = new int[arr.length]; 
     // create buckets 0 - 9 
     for (int i = 0; i < 10; i++) { 
      sortedNumbers.add(new ArrayList<>()); 
     } 

     for (int i = 0; i < arr.length; i++) { 
      System.out.println("Found number " + arr[i] + " puting index " + i + " to bucket " + arr[i]); 
      sortedNumbers.get(arr[i]).add(i); 
      System.out.println("Bucket " + arr[i] + " is having " +sortedNumbers.get(arr[i]).size() + " numbers now."); 
     } 

     System.out.println(); 
     System.out.println("The sortedNumbers (list with buckets) looks like following: " +sortedNumbers); 

     //just going through buckets and adding its numbers to sortedArr 
     int sortedIndex = 0; 
     for (List<Integer> bucket : sortedNumbers){ 
      for (Integer num : bucket){ 
       sortedArr[sortedIndex] = arr[num]; 
       sortedIndex++; 
      } 
     } 

     return sortedArr; 
    } 
} 

以上持っているのコードを以下のように、すべての番号を持つあなたこれとは一度だけ、したがって、それは0-9から数字だけを持つ例えばO(n)

---

で行われ、あなたはそれを並べ替えることができますJFセバスチャンとSteve314で言及されたこの出力

Found number 0 puting index 0 to bucket 0 
Bucket 0 is having 1 numbers now. 
Found number 5 puting index 1 to bucket 5 
Bucket 5 is having 1 numbers now. 
Found number 1 puting index 2 to bucket 1 
Bucket 1 is having 1 numbers now. 
Found number 1 puting index 3 to bucket 1 
Bucket 1 is having 2 numbers now. 
Found number 1 puting index 4 to bucket 1 
Bucket 1 is having 3 numbers now. 
Found number 1 puting index 5 to bucket 1 
Bucket 1 is having 4 numbers now. 
Found number 7 puting index 6 to bucket 7 
Bucket 7 is having 1 numbers now. 
Found number 9 puting index 7 to bucket 9 
Bucket 9 is having 1 numbers now. 
Found number 3 puting index 8 to bucket 3 
Bucket 3 is having 1 numbers now. 
Found number 2 puting index 9 to bucket 2 
Bucket 2 is having 1 numbers now. 
Found number 1 puting index 10 to bucket 1 
Bucket 1 is having 5 numbers now. 
Found number 2 puting index 11 to bucket 2 
Bucket 2 is having 2 numbers now. 
Found number 5 puting index 12 to bucket 5 
Bucket 5 is having 2 numbers now. 
Found number 6 puting index 13 to bucket 6 
Bucket 6 is having 1 numbers now. 

The sortedNumbers (list with buckets) looks like following: [[0], [2, 3, 4, 5, 10], [9, 11], [8], [], [1, 12], [13], [6], [], [7]] 
Result of sorting: [0, 1, 1, 1, 1, 1, 2, 2, 3, 5, 5, 6, 7, 9] 

---

、トンを行うalghoritms彼はRadix sort（より一般化されたalghorithm）またはCounting sort（ "強い"ではなく、よりシンプルでこの例では使用可能）と呼ばれています。

Answer 2

アレイのサイズはnですが、重複する要素を含むことができます。アレイにはk個の固有の要素しかありません。 （つまり、n - kは配列内の重複数です）