部分的に順序付けられたリストから順序付けられていない要素を見つける方法？

Question

私はListを持っていますが、ほとんどの要素はフィールドtitleに基づいて注文されています。いくつかの要素は順序付けられていません。どの要素がソートされていないかを特定する必要があります。

クラスはListの要素を定義するために使用される次のとおりです。

public class Doc { 
    String docOid; 
    String title; 

    private Doc(String docOid, String title) { 
     this.docOid = docOid; 
     this.title = title; 
    } 
} 

私が書かれているロジックはこれです：私は視覚的に結果を検証していたときに実行された後

//List<Doc> docs = given partially ordered list 
List<String> oids = new ArrayList<>(); 

for (int i = 0; i < docs.size(); i++) { 
    Doc doc = docs.get(i); 
    Doc faildDoc = null; 

    for (int j = 0; j < i; j++) { 
     Doc prevDoc = docs.get(j); 

     if (prevDoc.title != null && doc.title != null) { 
      int compare = collator.compare(prevDoc.title, doc.title); // For comparing I have used Collator 

      if (compare > 0) { 
       faildDoc = prevDoc; 
       break; 
      } 
     } 
    } 

    if (faildDoc != null) { 
     if (!oids.contains(faildDoc.docOid)) { 
      oids.add(faildDoc.docOid); 
      System.out.println(faildDoc.docOid); 
     } 
    }      
} 

ロジックが正しい結果を出さないことが分かります。

どのような提案も非常に役に立ちます。続き

は、現在の結果のサンプルです：

User Guide Metered Smart //<--Ordered 
User Guide, Network Management Card //<--Ordered 
User Guide. GPRS Modem //<--Ordered 
Simulation sub-base //<--Un ordered 
Vent Hood Installation //<--Ordered 
Vented Pullbox Installation //<--Ordered 

サンプルが正しく注文された場合、それは次のようになります。

Simulation sub-base 
User Guide Metered Smart 
User Guide, Network Management Card 
User Guide. GPRS Modem 
Vent Hood Installation 
Vented Pullbox Installation 

だから私は

Simulation sub-base //<--Un ordered 

ことを見つける必要があります

は発注されていません。

Answer 1

リスト内の欠陥を見つけるのに2つのループは必要ありません。正しい要素から次の正しい要素に移動できます。ここでは、擬似コードで概説している：

lastCorrect = list.get(0); 
for (int i = 1; i < list.size(); i++) { 
    current = list.get(i); 
    if (inCorrectOrder(lastCorrect, current)) { 
     lastCorrect = current; 
    } else { 
     defects.add(current); 
    } 
} 

ソリューションに関するいくつかの注意事項：1、ゼロではない

lastCorrectで

1. i開始は、それが常に正確であるので、最初は最初の要素れる
2. lastCorrectは、現在および現在の要素の順序が正しい場合にのみ移動されます。
3. 末尾にすべての並べ替えのない要素が含まれます

Answer 2

これは「順序付けられていない」要素を意味するものではありません。例えば、このようなシーケンスでは、「C」要素が「順序付けられていない」かどうかはわかりません。

A E F A B C D 

私はあなたに2つの方法を提案できます。

最初は非常に過激です。リストのコピーを作成してソートし、古いリストの各要素と新しいリストの同じ位置にある要素とを比較する必要があります。要素が異なる場合、要素は順序付けられていません。

あなたの特定のアルゴリズムで

（私はかなりあなたがそれを達成したい正確に理解していないが）、あなたはおそらくあなたのif文で符号を変更、または標準Stringコンパレータを使用する必要があります。

int compare = doc.title.compareTo(prevDoc.title);