バブルソート

BubbleSort.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;

class BubbleSort
{
    static void Main()
    {
        var array = new List<int>();
        var rand = new Random();
        
        for (int i = 0; i < 10000; i++)
        {
            //10000個の整数をランダムで生成
            array.Add(rand.Next(10000));
        }
        
        var sw = new StopWatch();
        
        sw.Reset();
        sw.Start();
        
        //計測時はどっちかコメントアウトして計測して下さい
        pattern_1(array.ToArray());
        
        pattern_2(array.ToArray());
        
        sw.Stop();
        
        Console.WriteLine(sw.Elapsed);
        
        //処理結果(My PC)
        //パターン１：６秒台
        //パターン２：３秒台
    }
    
    private static void Pattern_1(int[] array)
    {
        //一般的なバブルソート
        for (int i = 0; i < (array.Length - 1); i++)
        {
            for (int j = 0; j < array.Length - 1; j++)
            {
                if (array[j] > array[j + 1])
                {
                    var tmp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }
    
    private static void Pattern_2(int[] array)
    {
        //１回目のループは何番目の要素までの並び替えを行っているか知ることができる。
        //パターン１だと、並び替えが終わった要素も再び条件判断に含まれているので、
        //並び替えが必要な要素から検索を始めることで処理時間を短縮することができる。
        for (int i = 0; i < (array.Length - 1); i++)
        {
            for (int j = 0; j < (array.Length) - 1; j++)
            {
                if (array[i] > array[j + 1])
                {
                    var tmp = array[j + 1];
                    array[j + 1] = array[i];
                    array[i] = tmp;
                }
            }
        }
    }
}