バブルソート

アルゴリズム
バブルソート
バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。


先頭から順に次の要素と比較して、小さい値があれば入れ替えることを繰り返し
入れ替えがなくなったら処理が終了。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sample
{
    class Program
    {
        static void Main()
        {
            // 20までの数字を生成しシャッフルする
            var data = Program.GenerateData(20);

            // Sort前
            Console.WriteLine(string.Join(',', data));

            // バブルソート
            Program.BubbleSort(data);

            // バブルソート後
            Console.WriteLine(string.Join(',', data));
        }

        static void BubbleSort(List<int> data)
        {
            var flagChange = false;
            do
            {
                // 初期化
                flagChange = false;
                for (var i = 0; i < data.Count - 1; i++)
                {
                    // 次の要素の方が小さい場合入れ替えを行う
                    if (data[i + 1] < data[i])
                    {
                        var temp = data[i];
                        data[i] = data[i + 1];
                        data[i + 1] = temp;
                        flagChange = true;
                    }
                }
            } while (flagChange);
        }

        /// <summary>
        /// 任意の1〜nまでのリストを生成し、Fisher-Yatesシャッフルしたものを返す
        /// </summary>
        /// <param name="maxNumber"></param>
        /// <returns>1〜任意の数字までのシャッフルされたリスト</returns>
        static List<int> GenerateData(int maxNumber)
        {
            // 1未満の場合は空のリストを返す
            if (maxNumber < 1) { new List<int>(); }

            // 1から任意の数字までのリストを生成
            var num = Enumerable.Range(1, maxNumber).ToList<int>();

            // シャッフル
            Random r = new Random();
            for (var i = num.Count() - 1; 0 < i; i--)
            {
                var rand = r.Next(i);

                // 乱数が最大値と同じ時、シャッフル元とシャッフル先が同一となるため何もしない
                if (rand == i) { continue; }

                var temp = num[i];
                num[i] = num[rand];
                num[rand] = temp;
            }

            return num;
        }
    }
}


色々こねこねして思ったのは、下記の方がシンプルですね。
using System;

namespace Sample
{
    class Program
    {
        static void Main()
        {
            var ret = GreatestCommonDivisor(945, 280);
            Console.WriteLine(ret);
        }

        static int GreatestCommonDivisor(int a, int b)
        {

            if (b < a)
            {
                var temp = a;
                a = b;
                b = temp;
            }

            var r = 0;
            do
            {
                r = b % a;
                b = a;
                a = r;
            } while (0 < r);

            return b;
        }
    }
}

投稿日時: 2019-12-01 13:07:01
更新日時: 2019-12-02 00:22:02
VSCodeでファイル比較 | ユークリッド互除法

Comment