0

whileを使用してバブルソートを作成しようとしています。以下にクラスを投稿しました。並べ替えで、9 の最後の int が表示されないのはなぜですか。

namespace BubbleSort {
    class Program
    {
        static void Main(string[] args)
        {
            int[] i = {9, 2, 7, 6, 1, 3, 5, 4, 8};
            int va = 0, vb = 0;

            //loop through all numbers in the array.
            while (va < i.Length)
            {
                //loop through all numbers in the array trailing the first loop by 1.
                while (vb < i.Length)
                {
                    //compare the two values.
                    if (i[vb] < i[va]) {
                        Console.WriteLine(vb);
                    }                    
                    vb++; //increment
                }                 
                va++; //increment
            }
            Console.ReadLine();
        }
    }
}

このアプローチは正しいですか？

4

5 に答える 5

2

要するに、いいえ。実際には何もソートしていません。コードで何が起こるかは次のとおりです。

  • vaとvbをゼロに設定し、2 つのwhileループに入ります。
  • 内側のループの最初の繰り返しはi[0]、配列内の各値と比較します
  • i[vb] < i[va]falsewhen vb == 0(9は より小さくないため) を返すため、9何も表示されません
  • vb増分されます
  • 内側のループの残りが完了します。配列内の他のすべての値は9未満であるため、それらはすべて値を出力しますが、出力する値は実際にvbは配列からの値ではありません。ループは0toから8始まり、最初の値は配列内で最も高いためスキップします。したがって、内部ループで数値1を出力します。8
  • 内側のループはvbset toで完了します9
  • 外側のループがインクリメントvaして繰り返されます
  • vbまだに設定され9ているため、内側のループは完全にスキップされます
  • va上記の 2 つの手順は、コードが完了する 9 に到達するまで繰り返されます。

入力として別の配列を使用すると、まったく異なる結果が得られることがわかります。たとえば、配列の先頭から 9 を削除する3と、出力としてのみ得られます ( onlyi[3]は の最初の値より小さいため2)。配列に 3 つのゼロ値を埋め込むと、実際のソート値ではなくカウンター/インデックス値を出力しているため、実際には出力で 9、10、11 が得られます。

于 2013-11-14T13:32:54.370 に答える
2

いいえ、それはバブルソートではありません。さらに、値ではなく配列のインデックスを出力しています。説明についてはウィキペディアを参照してください

次のようなものが必要です。

   int[] i = {9, 2, 7, 6, 1, 3, 5, 4, 8};
   int va = 0;

   bool swapped = true;

   while (swapped) {

     swapped=false;
     va = 0;
  //loop through all numbers in the array.
   while (va < i.Length -1)
   {
          //compare the two values.
           if (i[va] > i[va+1]) {

               int swap = i[va];
               i[va] = i[va+1];
               i[va+1] = swap;
               swapped=true;
           }

       //increment
       va++;  
   }
}

その後i、ソートされます。

ところで、これは最適ではありません。n 番目のパスの最適化と for ループを使用して、より良いアルゴリズムを実現できます。

for ループを使用した、より最適化されたバージョンは次のようになります。

int[] i = {9, 2, 7, 6, 1, 3, 5, 4, 8};

int n = i.Length -1;
bool swapped = true;

for (int n = i.Length - 1; swapped && n > 0; n--) {
  swapped = false;
  for (int va=0; va < n; va++) {
      if (i[va] > i[va+1]) {
           int swap = i[va];
           i[va] = i[va+1];
           i[va+1] = swap;
           swapped=true;
      }
   }
}
于 2013-11-14T13:32:34.040 に答える
1

いいえ、ちがいます。

1) 「S」原則の違反: ボブル ソートを実装するクラスは、コンソールに書き込むべきではありません。

http://es.wikipedia.org/wiki/SOLID_(オブジェクト指向設計)

2) ネストされた while ループはいくつかの数値のみを出力し、何もソートしません。

http://en.wikipedia.org/wiki/Bubble_sort

于 2013-11-14T13:31:41.003 に答える
0 
public static void BubbleSort(int[] arr)
{
    for (int i = 0 ; i < arr.Length; i++)
    {
        for (int j = i + 1 ;  j< arr.Length; j++)
        {
            if (arr[i] > arr[j])
            {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }

    Console.WriteLine(String.Join(", ", arr));
}
于 2013-11-14T13:36:24.170 に答える
0

これは確かにバブルソートではありません。バブル ソートでは、複数のパスを使用して、リスト内のアイテムの位置を並べ替えます。リストを調べて、ループごとに smallets 値を選択するだけです。

あなたの質問に答えるには：

i[vb] < i[va]

i[0] は 9 です。他のエントリよりも小さくなることはないため、出力されることはありません。

編集

ダン、はい。インデックス印刷中です。興味深いことに、vb がいつでも 0 にリセットされているのを確認できませんか?? さて、なぜこれがソートアルゴリズムであると誰かが考えるのか、私は混乱しているとしましょう:)

于 2013-11-14T13:32:00.240 に答える