Skip to content

Instantly share code, notes, and snippets.

@Pzixel
Last active February 26, 2016 11:36
Show Gist options
  • Save Pzixel/c84e86e9989fb0714c08 to your computer and use it in GitHub Desktop.
Save Pzixel/c84e86e9989fb0714c08 to your computer and use it in GitHub Desktop.
Sorting prototype
using System;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
namespace ConsoleApplication6
{
class Program
{
static void Main(string[] args)
{
var r = new Random(10);
int[] arr = Enumerable.Range(1, 16).Select(x => r.Next(100)).ToArray();
foreach (int i in arr)
{
Console.Write(i + " ");
}
Console.WriteLine();
ZParallel.Sort(arr);
// int[] arr2 = (int[]) arr.Clone();
//var sw = Stopwatch.StartNew();
//Array.Sort(arr);
//sw.Stop();
//Console.WriteLine(sw.Elapsed);
//var sw2 = Stopwatch.StartNew();
//sw2.Stop();
//Console.WriteLine(sw2.Elapsed);
//Console.WriteLine("{0:N}", sw.ElapsedTicks / (double)sw2.ElapsedTicks);
//int[] arrTest = { 10, 15, 19, 23, 26, 32, 4, 9, 16, 30, 39, 47 };
//Console.WriteLine();
//var ranges = Range.FromArray(arrTest, 2);
//ZParallel.MergeArray(arrTest, ranges);
foreach (int i in arr)
{
Console.Write(i + " ");
}
}
}
public class ZParallel
{
public static void Sort(int[] arr)
{
var ranges = Range.FromArray(arr);
var allDone = new ManualResetEventSlim(false, ranges.Length*2);
int completed = 0;
foreach (var range in ranges)
{
ThreadPool.QueueUserWorkItem(r =>
{
var rr = (Range) r;
Array.Sort(arr, rr.StartIndex, rr.Length);
if (Interlocked.Increment(ref completed) == ranges.Length)
allDone.Set();
}, range);
}
allDone.Wait();
while (true)
{
MergeArray(arr, ranges);
if (ranges.Length <= 2)
break;
var newRanges = new Range[ranges.Length/2];
for (int i = 0, j = 0; i < newRanges.Length; i++, j += 2)
{
newRanges[i] = ranges[i].Union(ranges[i + 1]);
}
ranges = newRanges;
}
}
public static void MergeArray(int[] result, Range[] ranges)
{
if (ranges.Length == 1)
return;
for (int i = 1; i < ranges.Length; i += 2)
{
Range leftRange = ranges[i - 1];
Range rightRange = ranges[i];
var pivot = MergeRange(result, leftRange, rightRange);
var split = leftRange.Split(pivot.LeftBound);
MergeRange(result, split.Item1, split.Item2);
var rightSplit = rightRange.Split(pivot.RightBound);
MergeRange(result, rightSplit.Item1, rightSplit.Item2);
}
}
private static Pivot MergeRange(int[] result, Range leftRange, Range rightRange)
{
Pivot pivot = GetPivot(result, leftRange, rightRange);
Swap(result, pivot);
return pivot;
}
private static void Swap(int[] result, Pivot pivot)
{
for (int i = pivot.LeftBound, j = pivot.Middle; i < pivot.Middle; i++, j++)
{
var tmp = result[i];
result[i] = result[j];
result[j] = tmp;
}
}
private static Pivot GetPivot(int[] result, Range leftRange, Range rightRange)
{
int i, j;
int middle = rightRange.StartIndex;
for (i = leftRange.EndIndex, j = middle; result[i] >= result[j]; i--, j++)
{
if (i == leftRange.StartIndex)
return new Pivot(i, j, rightRange.StartIndex);
}
return new Pivot(i + 1, j - 1, rightRange.StartIndex);
}
}
public class Range
{
public int StartIndex { get; }
public int Length { get; }
public int EndIndex => Length + StartIndex - 1;
public Range(int startIndex, int length)
{
StartIndex = startIndex;
Length = length;
}
private static Range FromIndex(int startIndex, int endIndex)
{
var length = endIndex - startIndex + 1;
return new Range(startIndex, length);
}
public static Range[] FromArray<T>(T[] source)
{
return FromArray(source, Environment.ProcessorCount);
}
public static Range[] FromArray<T>(T[] source, int splitCount)
{
int partitionLength = (int) (source.Length/(double) splitCount);
var result = new Range[splitCount];
int start = 0;
for (int i = 0; i < result.Length - 1; i++)
{
result[i] = new Range(start, partitionLength);
start += partitionLength;
}
result[result.Length - 1] = new Range(start, source.Length - start);
return result;
}
public Range Union(Range range)
{
var min = Math.Min(StartIndex, range.StartIndex);
return new Range(min, Length + range.Length);
}
public Tuple<Range, Range> Split(int pivot)
{
var range1 = FromIndex(StartIndex, pivot - 1);
var range2 = FromIndex(pivot, EndIndex);
return new Tuple<Range, Range>(range1, range2);
}
}
public struct Pivot
{
public int LeftBound { get; }
public int RightBound { get; }
public int Middle { get; }
public Pivot(int leftBound, int rightBound, int middle)
{
LeftBound = leftBound;
RightBound = rightBound;
Middle = middle;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment