最適化されたバブルソート（Java）

Question

バブルソートを最適化できる方法を知りたいので、最初のパスの後であってもソートされている要素を見落としてしまいます。

Eg. [4, 2, 3, 1, 5, 6] --> [2, 3, 1, **4, 5, 6**] 

我々は、それが次のパスで、この3要素を見渡すことができますように私のコードを変更することができますどのように、[4,5,6]はソート順にすでにあることを確認？ （これはソートがより効率的であることを意味します） 再帰的メソッドを提案しますか？

public static void bubblesort(int[] a) { 
    for(int i=1; i<a.length; i++) { 
    boolean is_sorted = true; 

    for(int j=0; j<a.length; j++) { 
     if(a[j] > a[j+1]) { 
     int temp = a[j]; 
     a[j] = a[j+1]; 
     a[j+1] = temp; 
     is_sorted = false; 
     } 
    } 

    if(is_sorted) return; 
    } 
} 

ありがとうございます！

Answer 1

まず第一に、あなたはアウトオブバウンドアクセスがあります。j == a.length-1ため

for(int j=0; j<a.length; j++) { 
     if(a[j] > a[j+1]) { 

をするので、ループ条件はかなりj < a.length-1でなければなりません。バブルソートでは、あなたがk経過後、最大のk素子をアレイのk最後のエントリでソートされているので、従来のバブルソートは今

public static void bubblesort(int[] a) { 
    for(int i=1; i<a.length; i++) { 
    boolean is_sorted = true; 

    for(int j=0; j < a.length - i; j++) { // skip the already sorted largest elements 
     if(a[j] > a[j+1]) { 
     int temp = a[j]; 
     a[j] = a[j+1]; 
     a[j+1] = temp; 
     is_sorted = false; 
     } 
    } 

    if(is_sorted) return; 
    } 
} 

を使用して、それはまだだろうことを知っている

しかし、配列に長い要素の長いソートされたテールがある場合は、多くの不必要な繰り返しを行います。たとえば、が最初のk要素、k+1が100000000の順であるとします。標準のBubbleソートは、配列全体（ほぼ）にわたってk回通過します。

しかし、あなたはあなたの最後のスワップをした場所を覚えていれば、あなたはそのインデックスの後、順番に最大の要素があることを知っているので、

public static void bubblesort(int[] a) { 
    int lastSwap = a.length-1; 
    for(int i=1; i<a.length; i++) { 
    boolean is_sorted = true; 
    int currentSwap = -1; 

    for(int j=0; j < lastSwap; j++) { 
     if(a[j] > a[j+1]) { 
     int temp = a[j]; 
     a[j] = a[j+1]; 
     a[j+1] = temp; 
     is_sorted = false; 
     currentSwap = j; 
     } 
    } 

    if(is_sorted) return; 
    lastSwap = currentSwap; 
    } 
} 

は全体を通して1回だけで、上記の例を並べ替えるだろう配列は残り、残りは短いプレフィックスだけを通る。

もちろん、一般的にはそれほど多く買わないでしょうが、バブルのソートを最適化するのはむしろ無駄な作業です。

Answer 2

内部ループに変数 "size"を使用し、各サイクルで最新のスワップ要素に変更する必要があります。このようにして、内部ループは最新の「スワップ」要素まで移動し、スワップされていない残りの部分を渡します別名、彼らの正しいところに）。

do { 
     int newsize =0; 
     for (int i = 1; i < size; i++) { 
      if (a[i - 1] > a[i]) { 
       int temp; 
       temp = a[i - 1]; 
       a[i - 1] = a[i]; 
       a[i] = temp; 
       newsize =i; 
      } 
     } 
     size = newsize; 
    } while (size > 0); 

Answer 3

public static Integer[] optimizedbubbleSort(Integer[] input){ 
    long startTime = System.nanoTime(); 
    boolean swapped = true; 
    for(int pass=input.length-1; pass>=0 && swapped; pass--){ 
     swapped = false; 
     for(int i=0; i<pass; i++){ 
      if(input[i]>input[i+1]){ 
       int temp = input[i]; 
       input[i] = input[i+1]; 
       input[i+1] = temp; 
       swapped = true; 
      } 
     } 
    } 
    System.out.println("Time taken for OPTIMIZED bubbleSort: "+(System.nanoTime() - startTime)); 
    return input; 
} 

Answer 4

public static void BubbleSorter(params int[] input){ 
     int newSize = input.Length-1, size = 0; 
     bool swap; 
     do 
     { 
      swap = false; 
      for (int j = 0; j < newSize; j++) 
      { 
       if (input[j] > input[j + 1]) 
       { 
        int temp = input[j + 1]; 
        input[j + 1] = input[j]; 
        input[j] = temp; 
        swap = true; 
        size = j; 
       } 
      } newSize = size; 
     } while (swap); 

     DisplayArrayElements(input); 
    } 

Answer 5

すなわち私は、以前のループで発注されている配列の最初と最後に部品を除外して反復回数を削減する方法を考案しました。

static int[] BubbleSortOptimized(int arr[]) { 
    int start = 0, stop = arr.length - 1, control = 0; 
    boolean ordered, nsCaught; 
    while (true){ 
     ordered = true; 
     nsCaught = false; 
     for (int i = start; i < stop; i++) { 
      if (i > 1) { 
       if (!nsCaught && arr[i-2] > arr[i-1]){ 
        ordered = false; 
        start = i-2; 
        nsCaught = true; 
       } 
      } 
      if (arr[i] > arr[i+1]){ 
       int hold = arr[i]; 
       arr[i] = arr[i+1]; 
       arr[i+1] = hold; 
       control = i; 
      } 
     } 
     System.out.println(Arrays.toString(arr)); 
     if (ordered) return arr; 
     stop = control; 
    } 
} 

しかし@Daniel Fischerとして

は