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

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


More than 5 years have passed since last update.


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);


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

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

        method(array, 0, array.Length - 1);

        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();

        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 };
        return a[1];


要素数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



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


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