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

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

}

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)
{
}

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