Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What is going on with this article?
@Nucleareal

クイックソートと偽クイックソートの比較

More than 5 years have passed since last update.

最近関数型言語で「クイックソートが数行で書けるんだぜ!」みたいなアレがあるけどどう見てもクイックソートじゃないので
C#でそのソートとクイックソートを比較してみた。

計測に使ったプヨグヤム
```csharp:qsort.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Reflection;

namespace Test
{
class Program
{
public static int[] arr;

    static void Main(string[] args)
    {
        arr = GenerateArray(new Random());

        Console.Write("QuickF"); Calculate(QuicksortF);
        Console.Write("QuickT"); Calculate(QuicksortT);

        Console.ReadKey();
    }

    static void Calculate(Action<int[], int, int> method)
    {
        Stopwatch sw = new Stopwatch();

        var array = new int[arr.Length];
        Array.Copy(arr, array, arr.Length);

        sw.Reset();
        sw.Start();
        method(array, 0, array.Length - 1);
        sw.Stop();

        Console.WriteLine(":{1}ms", method, sw.ElapsedMilliseconds);
    }

    static int[] GenerateArray(Random rand)
    {
        return Enumerable.Range(0, 1000000).Select(x => rand.Next(100000)).ToArray();
    }

    static void QuicksortF(int[] array, int left, int right)
    {
        var pt = GetPt(array, 0, array.Length-1);

        var lList = new List<int>();
        var rList = new List<int>();
        var cList = new List<int>();

        var list = array.ToList();

        foreach(var v in array)
        {
            if (v < pt) lList.Add(v); else if (v > pt) rList.Add(v); else cList.Add(v);
        }

        var arrayL = lList.ToArray();
        var arrayR = rList.ToArray();
        var arrayC = cList.ToArray();

        if (arrayL.Length > 0) QuicksortF(arrayL, 0, lList.Count - 1);
        if (arrayR.Length > 0) QuicksortF(arrayR, lList.Count, lList.Count + rList.Count - 1);

        var totalList = arrayL.ToList();
        totalList.AddRange(arrayC);
        totalList.AddRange(arrayR);

        for (var i = 0; i < totalList.Count; i++)
        {
            ReplaceF(ref array[i], totalList[i]);
        }
    }

    static void ReplaceF(ref int var, int val)
    {
        var = val;
    }

    static void QuicksortT(int[] array, int left, int right)
    {
        var pt = GetPt(array, left, right);

        int i = left, j = right;

        while (true)
        {
            while (array[i] < pt) i++;

            while (pt < array[j]) j--;

            if (i >= j) break;

            SwapT(ref array[i], ref array[j]);
            i++; j--;
        }

        if (left < i - 1)  QuicksortT(array, left, i - 1);
        if (j + 1 < right) QuicksortT(array, j + 1, right);
    }

    static void SwapT(ref int a, ref int b)
    {
        var tmp = a;
        a = b;
        b = tmp;
    }

    static int GetPt(int[] array, int left, int right)
    {
        int l = array[left];
        int r = array[right];
        int c = array[(left + right) / 2];
        int[] a = new int[] { l, r, c };
        Array.Sort(a);
        return a[1];
    }
}

}
```
QuicksortFがその偽ソートでQuicksortTが実際のクイックソート。
平均はとらなかったけど察して

要素数100万, 乱数0~99999

  • QuicksortF: 873ms
  • QuicksortT: 331ms

要素数1000万, 乱数0~99999

  • QuicksortF: 7821ms
  • QuicksortT: 3603ms

要素数100万, 乱数0~99

  • QuicksortF: 283ms
  • QuicksortT: 346ms

要素数100万, 乱数0~9

  • QuicksortF: 124ms
  • QuicksortT: 307ms

結論

偽クイックソートはどう見てもマージソート

3
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
3
Help us understand the problem. What is going on with this article?