プログラミング学び直しシリーズ。食わせる数列は以下。1 〜 100の100個の整数をランダムに並べたもの。

60 32 85 24 57 31 98 50 49 81 52 80 96 41 55 91 54 70 77 36 94 74 89 29 38 1 34 73 4 2 6 18 16 65 51 3 22 56 9 28 13 46 17 33 45 72 99 26 76 14 42 82 44 35 53 19 92 87 90 8 12 95 97 69 20 37 48 15 66 64 78 83 40 79 75 86 68 62 61 10 84 100 93 27 21 43 25 67 71 88 63 23 11 39 30 59 5 58 7 47

バブルソート

using System;
using System.Linq;

public class Program
{

    public static void Main(string[] args)
    {
        var steps = 0;
        var list = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        bool swapped = false;
        do
        {
            swapped = false;
            for (var i = 0; i < list.Length - 1; i++)
            {
                steps++;
                var a = list[i];
                var b = list[i + 1];

                if (a > b)
                {
                    list[i] = b;
                    list[i + 1] = a;
                    swapped = true;
                }
            }
        } while (swapped);

        foreach (var x in list)
        {
            Console.WriteLine(x);
        }

        Console.WriteLine("steps: " + steps);
    }

}

steps: 9207

シェイカーソート

using System;
using System.Linq;

public class Program
{

    public static void Main(string[] args)
    {
        var steps = 0;
        var list = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        bool swapped = false;
        do
        {
            swapped = false;

            for (var i = 0; i < list.Length - 1; i++)
            {
                steps++;
                var a = list[i];
                var b = list[i + 1];

                if (a > b)
                {
                    list[i] = b;
                    list[i + 1] = a;
                    swapped = true;
                }
            }

            for (var i = list.Length - 1; i > 0; i--)
            {
                steps++;
                var a = list[i];
                var b = list[i - 1];

                if (a < b)
                {
                    list[i] = b;
                    list[i - 1] = a;
                    swapped = true;
                }
            }

        } while (swapped);

        foreach (var x in list)
        {
            Console.WriteLine(x);
        }

        Console.WriteLine("steps: " + steps);
    }

}

steps: 5346

ノームソート

using System;
using System.Linq;

public class Program
{

    public static void Main(string[] args)
    {
        var steps = 0;
        var list = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        for (int i = 0; i < list.Length - 1; i++)
        {
            do
            {
                steps++;
                var a = list[i];
                var b = list[i + 1];

                if (a > b)
                {
                    list[i] = b;
                    list[i + 1] = a;
                    i--;
                }
                else
                {
                    break;
                }
            } while (i != -1);
        }

        foreach (var x in list)
        {
            Console.WriteLine(x);
        }

        Console.WriteLine("steps: " + steps);
    }

}

steps: 5158

選択ソート

using System;
using System.Linq;

public class Program
{

    public static void Main(string[] args)
    {
        var steps = 0;
        var list = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        for (var i = 0; i < list.Length; i++)
        {
            var min = i;

            for (var j = i + 1; j < list.Length; j++)
            {
                steps++;
                if (list[min] > list[j])
                {
                    min = j;
                }
            }

            steps++;
            if (i != min)
            {
                var a = list[i];
                var b = list[min];

                list[i] = b;
                list[min] = a;
            }
        }

        foreach (var x in list)
        {
            Console.WriteLine(x);
        }

        Console.WriteLine("steps: " + steps);
    }

}

steps: 5050