選択ソート

アルゴリズム
選択ソート
選択ソート(英: selection sort)は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。


最小値を探しだし、走査した最初の要素と置き換え、
範囲を一つ小さくして同じ処理の繰り返しを行う

例)
2,3,5,1,4の場合

未ソート領域から最小値を探す


未ソート領域の先頭要素と入れ替える


-------

未ソート領域から最小値を探す


未ソート領域の先頭要素と入れ替える


-------

未ソート領域から最小値を探す


未ソート領域の先頭要素と入れ替える


-------

未ソート領域から最小値を探す


未ソート領域の先頭要素と入れ替える



サンプルコード
using System;
using System.Collections.Generic;
using System.Linq;

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

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

            // 選択ソート
            Program.SelectionSort(data);

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

        static void SelectionSort(List<int> data)
        {
            // データが0個なら終了
            if (data.Count == 0) { return; }

            // 未ソート領域の範囲を1つずつ狭めていく
            for (var i = 0; i < data.Count - 1; i++)
            {
                // 最小値の要素番号を取得
                // 最初の要素番号を基準値にする
                var minIndex = i;
                for (var j = i + 1; j < data.Count; j++)
                {
                    // より小さな値があればIndexを入れ替える
                    if (data[j] < data[minIndex]) { minIndex = j; }
                }

                // 最小値が先頭の場合入れ替え作業は不要
                if (i == minIndex)
                {
                    continue;
                }
                else
                {
                    // 未ソート領域の先頭要素と入れ替える
                    (data[i], data[minIndex]) = (data[minIndex], data[i]);
                }
            }
        }

        /// <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; }

                (num[i], num[rand]) = (num[rand], num[i]);
            }

            return num;
        }
    }
}

投稿日時: 2020-08-14 14:55:14
更新日時: 2020-08-16 14:48:16
マージソート | 呼び出し元のメソッド名、行数、ファイル名の取得

Comment