ArrayList内の要素をソートするために必要なパスを確認する方法は？

Question

バブルソートを使用してarraylistの要素をソートするために必要なパス数を確認するにはどうすればよいですか？私はこれらの2つの方法を持っています。

public boolean checkInSortedOrder(ArrayList<QuakeEntry> quakes){ 
    boolean sorted = true;   
    for (int i = 1; i < quakes.size(); i++) { 
      if (quakes.get(i-1).compareTo(quakes.get(i)) > 0){ 
      sorted = false; 
     } 
} 

return sorted; 

上記のメソッドは、arrayListがソートされているかどうかをチェックします。 このメソッドはバブルソートを実行します。

public void onePassBubbleSort(ArrayList<QuakeEntry> quakeData, int numSorted){ 
    int j; 
    QuakeEntry temp; 
    for(int i=0; i<numSorted; i++){ 
    for(j=0; j<(quakeData.size()-i-1);j++){ 
     if(quakeData.get(j).getMagnitude()>quakeData.get(j+1).getMagnitude()){ 
      temp=quakeData.get(j); 
      quakeData.set(j,quakeData.get(j+1)); 
      quakeData.set(j+1,temp); 
     } 
     } 
     System.out.println("Printing Quakes after "+ i +" pass "); 
     for (QuakeEntry qe: quakeData) { 
     System.out.println(qe); 
    } 
    } 

} 

私はカウンタ変数を追加する必要があることを知っています。しかし、少しコードと混同しています。

Answer 1

つ単に以下のコードに示すように、指定されたリストをソートするために必要とされるどのように多くの最小パス確認するために、ブール値を使用することができます。

import java.util.*; 

public class BubbleSort { 

    private static final int TOTAL_ELEMENTS = 5; 

    private List <Integer> numbers; 
    private boolean isSorted; 
    private Random random; 

    public BubbleSort() { 
     random = new Random(); 
     isSorted = true; 
     numbers = new ArrayList <Integer> (TOTAL_ELEMENTS); 
     numbers.add (new Integer (1)); 
     numbers.add (new Integer (2)); 
     numbers.add (new Integer (3)); 
     numbers.add (new Integer (4)); 
     numbers.add (new Integer (5)); 
    } 

    private void performTask() { 
     int pass = 1; 
     while (pass <= numbers.size()) { 
      isSorted = true; 
      for (int i = 0; i <= (numbers.size() - pass - 1); ++i) { 
       System.out.println ("i: " + i + " pass: " + pass + "[ i ]: " + numbers.get (i) + " [ i + 1 ]: " + numbers.get (i + 1) ); 
       if (numbers.get (i).compareTo (numbers.get (i + 1)) > 0) { 
        System.out.println ("Entered if clause"); 
        Integer temp = numbers.get (i); 
        numbers.set (i, numbers.get (i + 1)); 
        numbers.set (i + 1, temp); 
        isSorted = false; 
        display(); 
       } 
      } 
      if (isSorted) { 
       break; 
      } 
      ++pass; 
     } 
     System.out.println ("Minimum passes: " + pass); 
     display(); 
    } 

    private void display() { 
     System.out.println ("Array content: "); 
     for (Integer number : numbers) { 
      System.out.println (number.intValue()); 
     } 
    } 

    public static void main (String [] args) { 
     new BubbleSort().performTask(); 
    } 
} 

Answer 2

最も左の反転の位置と右端の反転の位置は、配列を何回通過させなければならないかという最悪の場合のカウントを示します。

もちろん、取得する価値が過大評価である場合もあります。たとえば、配列が次のような場合もあります。この場合、1が十分である間に6回のパスが必要と考えられます。

2 1 4 5 6 8 7 

しかし、この方法では過小評価したことがない、と私は多くの場合、過大評価が過小評価よりも優れていると思われます。結局のところ、各パスの後でこれを行うことができます。反転が見つからない場合は、ただ停止することができます。

2番目のアプローチは、実際には、インプレースO（nlogn）アルゴリズムを使用して配列をソートし、必要なパスの数を宣言するための最初と最後のインデックスの最大の違いを見つけることです。しかし、あなたがO（nlogn）を自由に使うことができるのは、ほとんどの場合、あなたが最初にやるべきことでした。だから、私はこの方法でソートをシミュレートすることも選択肢ではないと考えています。

範囲情報がcounting sortを助けるように、ソートするデータについて他の知識がある場合は、おそらくそれが役に立つかもしれません。たとえば、要素に繰り返しがなく、範囲[1、N]にあることが分かっていれば、並べ替え手順をシミュレートして、繰り返し回数として使用する初期インデックスと最終インデックスの最大の違いを見つけることができます。しかし、そのような特別な情報は言及していないので、おそらくあなたを助けることにはならないでしょう。

ソートと追加情報のシミュレーションが利用できないため、以下のような未実装のJava実装を過大評価メソッドを使用することをお勧めします。

public int getNumberOfRepsNecessary(ArrayList<QuakeEntry> quakes){ 
    int leftmostInversion=-1, rightmostInversion = -1; 
    for (int i = 1; i < quakes.size(); i++) { 
     if (quakes.get(i-1).compareTo(quakes.get(i)) > 0){ 
      if(leftmostInversion == -1) { 
       leftmostInversion = i-1; 
      } 
      rightmostInversion = i-1; 
     } 
    } 
    if(leftmostInversion == -1) 
     return 0; 
    return rightmostInversion - leftmostInversion + 1; 
}