java - ソートアルゴリズムが機能していません

Question

オブジェクトをジェネリック クラスに追加するときに、昇順で並べ替える必要があります (文字列を使用しています)。

選択ソートを使用していますが、機能していません。

これが正しい方法かどうかはわかりませんので、ご意見をいただければ幸いです。

OrderSet クラス

public class OrderSet<T extends Comparable> implements Set<T> {

    private T[] items;
    private int size;

    public OrderSet()
    {
        items = (T[]) new Comparable[5];        
    }

    @Override
    public void add(T s)
    {
        if(size >= items.length)
        {
            items = grow(items);
        }

        for(int i = 0; i < items.length; i++) 
        {
            if(items[i] == null)
            {
                items[i] = s;
                size++;
                break;
            }
        }

        if(size > 1)
        {
            for (int i = 0; i < size-1; i++)
            {
                for(int j = 1; j < size; j++)
                {
                    T tmp;
                    if (items[i].compareTo(items[j]) > 0)
                    {
                        tmp = items[i];
                        items[i] = items[j];
                        items[j] = tmp;
                    }                    
                }                
            }
        }
    }

    @Override
    public void show()
    {        
        for(T a : items)
        { 
            if(a != null)
                System.out.print(a+", ");            
        }
    }

    public T[] grow(T[] a)
    {
        T[] newA = (T[]) new Comparable[a.length+5];
        System.arraycopy(a, 0, newA, 0, a.length);
        return newA;
    }

}

主要

public class Main {

    public static void main(String[] args) throws IOException
    {
        OrderSet<String> s1 = new OrderSet<>();
        WordCount s2 = new WordCount();

        Scanner input = new Scanner("the boy plays in the park with dog");
        while (input.hasNext()) 
        {
            String w = input.next();
            s1.add(w);
        }

        s1.show();

        System.out.println();
    } 
}

Answer 1

あなたがしているように見えるのは、アイテムを追加するときのバブルソートです。選択ソートの一般的な形式は次のとおりです。

for(int i = 0; i<arr.length - 1; i++)
{
   int smallest = i;
   for(int j = i + 1; j< arr.length; j++)
   {
       if(arr[j].compareTo(arr[smallest]) > 0)
           smallest = j;
   }
   if(smallest < arr.length && smallest != i)
       swap(arr[i], arr[smallest]);
}

最大のものを最後のインデックスにスワップすることもできますが、これも同様に機能するはずです。swap は、実際のスワッピングの単なるプレースホルダー疑似コードであることに注意してください。

Answer 2

間違っているのはソートアルゴリズムだと思います。Ardentsonata の言う通り、Bubblesort アルゴリズムを使用していますが、間違いがあります。

for (int i = 0; i < size-1; i++) {
    for(int j = 1; j < size; j++){
        T tmp;
        if (items[i].compareTo(items[j]) > 0) {
            tmp = items[i];
            items[i] = items[j];
            items[j] = tmp;
        }                    
    }                
}

問題は 2 番目のループの開始値です。他の要素があるかどうかを確認する必要があります。ただし、既に並べ替えた要素を除いて、現在並べ替えたい要素よりも大きい場合があります。したがって、2 番目のループにはこの頭が必要です。

for(int j = (i+1); j < size; j++)

したがって、実際に配列をソートします。

そうしないと、2 番目のスロットに何かを切り替えた後、次の反復で元に戻すため、値の切り替えを制御できませんでした。

それが役立つことを願っています!

Answer 3

この場合、文字列比較の概念を使用することをお勧めします

class City {

public static void main (String args[])
{ 
int i,j;
String temp;
String s[] = new String[6];
for(i=0; i<6; i++)
 s[i]=args[i];
for(i=0;i<6;i++){
  for(j=0;j<6-i-1;j++){
 if(s[j].compareTo(s[j+1])>0)
 {
   temp=s[j];
   s[j]=s[j+1];
   s[j+1]=temp;
 } 
}
 }
 for(i=0; i<6; i++)
 {
 System.out.println(s[i]);
}
}}

Answer 4

SortedSet< T >を実装するjava.util.TreeSet< T >を使用します。