ソート（並べ替え）②: 選択ソート

選択ソートの定義

「未整列な配列」の最小値を取り出し、「整列済み配列」の末尾に付け加える

 

---

選択ソートのPseudo Code

selection_sort(A : 配列, n : Aの要素数)
    for i = 0 to n-2
        // A[i] ~ A[n-1] の最小値を見つけ、A[i]と交換する
        // つまり、整列済みとなっている A[0] ~ A[i-1] の末尾に、A[i] ~ A[n-1] の最小値を付け加える
        
        // A[i] ~ A[n-1] の最小値の位置を保存する変数 min_index を用意
        // 暫定的に A[i] を最小値とする
        min_index <- i

        // 最小値を探す
        for j = i+1 to n-1
            if A[j] < A[min_index] then
                min_index = j

        // A[i] と A[min_index]を交換
        swap(A[i], A[min_index])

        // A[0] ~ A[i] が整列済みになった

---

選択ソートの時間複雑度

O(n^2) 

---

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var line = Console.ReadLine().Split().Select(int.Parse).ToArray();
        
        for(int i = 0; i < n-1; i++)
        {
            int minIdx = i;
            
            for(int j = i+1; j < n; j++)
            {
                if(line[j] < line[minIdx]) minIdx = j;
            }
            
            int temp = line[i];
            line[i] = line[minIdx];
            line[minIdx] = temp;
            
            Console.WriteLine(string.Join(" ",line));
        }
    }
}