配列でJavaで並べ替えリストを実装する際の問題

Question

私が書いたクラスのaddメソッドに問題があるようです。配列を使用してSortedListを作成したいのですが、問題が何であるかわかりません。これは私のコードです：私は私のリストに2つの整数を追加する場合

public class SortedList { 

    private Integer[] elements; 
    private int size; 
    private int capacity; 

    public SortedList(int cap) { 

     elements = new Integer[cap]; 

     if (cap > 0) 
     { 
      cap = capacity; 
     } 
     else 
      capacity = 10; 

    } 

    public boolean isEmpty() 
    { 
     return size == 0; 
    } 

    public boolean isFull() 
    { 
     return size == capacity; 
    } 

    public int size() 
    { 
     return size; 
    } 

    public void doubleCapacity() 
    { 
     capacity = capacity * 2; 
    } 

    public void add(Integer el) 
    { 
     if(this.isEmpty()) 
     { 
      elements[0] = el; 
      size++; 
     } 

     else if(this.isFull()) 
     { 
      this.doubleCapacity(); 
      for(int i = 0; i<this.size(); i++) 
      { 
       if(el >= elements[i]) 
       { 
        elements[i+2] = elements[i+1]; 
        elements[i+1] = el; 
       } 

       else 
       { 
        elements[i+1] = elements[i]; 
        elements[i] = el; 
       } 
      } 
      size++; 
     } 
     else 
     { 
      for(int i = 0; i<this.size(); i++) 
      { 
       if(el >= elements[i]) 
       { 
        elements[i+2] = elements[i+1]; 
        elements[i+1] = el; 
       } 
       else 
       { 
        elements[i+1] = elements[i]; 
        elements[i] = el; 
       } 
      } 
      size++; 
     } 

    } 

    public String toString() 
    { 
     String s = ""; 
     s = s + "<SortedList["; 
     for(int i = 0; i < this.size(); i++) 
     { 
      s = s + elements[i]; 
      if(i < this.size()-1) 
       s = s + ","; 
     } 
     s = s + "]>"; 
     return s; 
    } 


    public static void main(String[] args) 
    { 
     SortedList sl = new SortedList(5); 
     sl.add(3); 
     //sl.add(2); 
     sl.add(4); 
     sl.add(5); 
//  sl.add(6); 
     System.out.println(sl.toString()); 
    } 



} 

私のコードは動作しますが、私は数字3,4,5を追加しようとすると、私は3,5,5-を取得...

何が問題なのですか？ありがとう..

Answer 1

パブリッククラスSortedListの{

private Integer[] elements; 
private int size=0; 
private int capacity; 

public SortedList(int cap) { 

    elements = new Integer[cap]; 

    if (cap > 0) 
    { 
     capacity = cap; 
    } 
    else 
     capacity = 10; 

} 

public boolean isEmpty() 
{ 
    return size == 0; 
} 

public boolean isFull() 
{ 
    return size == capacity; 
} 

public int size() 
{ 
    return size; 
} 

public void doubleCapacity() 
{ 
    capacity = capacity * 2; 
} 

public void add(Integer el) throws Exception{ 
    elements[size] = el; 
    size++; 
    if(size>capacity){ 
     throw new Exception("Size Exceeded"); 
    } 
} 

public String toString() 
{ 
    sort(); 
    String s = ""; 
    s = s + "<SortedList["; 
    for(int i = 0; i < this.size(); i++) 
    { 
     s = s + elements[i]; 
     if(i < this.size()-1) 
      s = s + ","; 
    } 
    s = s + "]>"; 
    return s; 
} 

public void sort(){ 
    for (int i=0; i <size()-1; i++) { 
     if (elements[i] > elements[i+1]) { 
      // exchange elements 
      int temp = elements[i]; 
      elements[i] = elements[i+1]; 
      elements[i+1] = temp; 
     } 
    } 
} 

public static void main(String[] args) 
{ 
    try { 
     SortedList sl = new SortedList(5); 
     sl.add(3); 
     //sl.add(2); 
     sl.add(6); 
     sl.add(5); 

// sl.add（6）。 System.out.println（sl.toString（））; } catch（Exception ex）{ Logger.getLogger（SortedList.class.getName（））。log（Level.SEVERE、null、ex）; }}

}

Answer 2

あなたの挿入コードは機能しません。

elements[i+1] = elements[i]; 
elements[i] = el; 

elements[i+1]の古い値はどうなりますか？

Answer 3

以前の解決策に以下の変更をお勧めします。 toString（）でsortを呼び出すだけであれば、ソートされていない複数の要素が連続している場合にリストがすぐに順不同になります（これでtoString（）からsort（）を削除できました）。これは本質的に迅速な挿入の並べ替えであり、すぐにリストをスワップすることができなくなると終了します。繰り返しになりますが、dtyが示唆するように、挿入ポイントを見つけるためのバイナリ検索がより高速に選択できます。

public void doubleCapacity(){

capacity = capacity * 2; 
Integer temp[] = new Integer[capacity]; 
for (int i = 0; i < size; i++){ 
    temp[i] = elements[i]; 
} 
elements = temp; 

}

public void add(Integer el){

if(size+1>capacity){ 
    doubleCapacity(); 
} 
elements[size] = el; 
size++; 
sort(); 
} 

public void sort(){

//Iterates down the list until it's sorted. 
for (int i=size()-2; i >= 0 && (elements[i] < elements[i+1]); i--) { 
     // exchange elements 
     int temp = elements[i]; 
     elements[i] = elements[i+1]; 
     elements[i+1] = temp; 
} 

}