すでにO（n）の再帰ソートアルゴリズムを改善するには？

Question

私は割り当てに使用しているこの再帰ソートアルゴリズムを持っていて、私の先生は簡単な私のアルゴリズムの実行時間を改善する方法があると言った...しかし、私はそれが何であるか把握することはできませんすべて。私が間違っていない限り、アルゴリズムの複雑さはO（n）ですか？クラスで再帰的メソッドの複雑さを計算する方法を学んでいないので、私は確信していません。コードは次のとおりです。

public static void MyAlgorithm(int[] A, int n){ 
    boolean done = true; 
    int j = 0; 
    while (j <= n - 2){ 
     if (A[j] > A[j + 1]) { 
      swap(A,j,j+1); 
      done= false; 
     } 
     j++; 
    } 
    j = n - 1; 
    while (j >= 1){ 
     if (A[j] < A[j - 1]) { 
      swap(A,j-1,j); 
      done=false; 
     } 
     j--; 
    } 

    if (!done) 
     MyAlgorithm(A, n); 
    else 
     return; 
} 

私が考えることができるのは、if（done）returnを追加することだけです。最初のループの後で、それはプログラムが他のいくつかの操作を行うのを保存するだけです。ああ、スワップ方法は基本的にちょうどです：

public static void swap(int[] arr, int pos1, int pos2){ 
    int temp = arr[pos1]; 
    arr[pos1] = arr[pos2]; 
    arr[pos2] = temp; 
} 

ありがとうございます。

Answer 1

開始するには、比較を使用してO（n）でソートアルゴリズムを実行することはできません。原則として、すべてのソートアルゴリズムはAT LEAST O（n * log（n））時間を要します。

あなたが使用しているように見えるソートは、カクテルシェーカーソート、または双方向バブルソートに似ています。それはO（n^2）時間で実行されます。あなたは確かにあなたが使用する方法を研究し、それらを使用する理由を考慮する必要があります、また、大きなO表記で物事を適切に分類する方法を学びます。

あなたの先生は、あなたがMyAlgorithm（a、n-1）としてソートを呼び出す必要があると思います。最初のループでは配列全体をどのように通過するのでしょうか？これは、ループが終了すると、最後の要素が既にソートされていることを意味します。同様に、開始インデックスを追加して毎回増分することができます。例えば、改訂コード：

public static void MyAlgorithm(int[] A, int start, int n){ 
    boolean done = true; 
    int j = start; 
    while (j <= n - 2){ 
     if (A[j] > A[j + 1]) { 
      swap(A,j,j+1); 
      done= false; 
     } 
     j++; 
    } 
    j = n - 1; 
    while (j >= start+1){ 
     if (A[j] < A[j - 1]) { 
      swap(A,j-1,j); 
      done=false; 
     } 
     j--; 
    } 

    if (!done) 
     MyAlgorithm(A, start+1, n-1); 
    else 
     return; 
} 

その後は、使用して、これを呼び出すことができます。MyAlgorithm（my_arrayで、0、my_array.length）

これはまだ素晴らしいソートアルゴリズムではないことに注意してください、そしてあなたの場合大量のデータをソートする必要がある場合は、何かを高速に使用することを検討する必要があります。