O（ログn）余分なスペース（スタック）を持つ反復QuickSort

Question

こんにちは私はQuickSortをスタックで書いていますが、このalghoritmがO（n）余分なスペースやO（log n）作る。

誰かがこのコードを見て、余分なスペースがここでスタックをどのように使用するか教えてください、もしO（n）余分なスペースを使ってO（log n）ここで

はO（Nを記録）領域の使用状況を保証するために私のコード

public class QuickSortStack{ 

public static void quickSortStack(int[] tab, int L, int R) { 

    Stack<Integer> stack = new Stack(); 


    while (L < R || !stack.isEmpty()) { 

     if (L < R) { 
      int q = lomutoPartition(tab, L, R); 

      stack.push(R); 
      R = q - 1; 

     } else { 

      L = R + 2; 
      R = stack.pop(); 

     } 
    }//end of while 
}//end of QS method 

public static void main(String[] args) { 

    int[] test= {-4,2,-4,2,-12,5,-1,6,-9,0,9}; 

    Random random = new Random(); 
    int[] tab= new int[20]; 


    for (int i = 0; i < 20; i++) { 
     tab[i] = random.nextInt(50); 
     System.out.print(tab[i] + " "); 
    } 
    System.out.println(); 
    quickSortStos(tab, 0, tab.length - 1); 

    for (int x : tab 
      ) { 
     System.out.print(x + " "); 
    } 

} 
public static void swap(int[] tab, int i, int j) { 

    int tmp = tab[i]; 
    tab[i] = tab[j]; 
    tab[j] = tmp; 

} 

public static int lomutoPartition(int[] tab, int L, int R){ 

    int i = L-1; 
    int x = tab[R]; 


    for(int j = L; j < R; j++){ 

     if(tab[j] <= x){ 

      i = i+1; 
      swap(tab, i, j); 

     } 

    } 

    swap(tab, i+1, R); 
    return i+1; 

} 

Answer 1

である、あなたは小さいものと2つのパーティションとループの大きい方をプッシュする必要があります。これは、ログを超えないのスタックの深さを保証する、非末尾再帰は常に小さいパーティションである再帰的なソリューションと同等だ N.

あなたがそれを行うときは、両方の境界をプッシュする必要があります。それが最初のパーティションか2番目のパーティションかを示すブール値を返します。

Fwiwでは、反復解が再帰解より高速ではないという共通の経験があります。再帰的な実装は、（大規模なパーティションの）2番目の再帰をテールコール最適化する限り、安全です。ご使用の言語がTCOを保証しない場合は、手作業で簡単に行うことができます。