[Updated] Using the
IComparer<T>
method from
Solution 3, here is a visualization of the sorting with up to nine (9) sorting algorithms:
Bubble sort[
^],
Comb Sort[
^],
Cycle Sort[
^],
Gnome Sort[
^],
Insertion Sort[
^],
Odd-even sort[
^],
Quick Sort[
^],
Selection Sort[
^],
Shell sort[
^].
I have made them asynchronous so several can run simultaneously and see how they function. I've colour-coded the actions: blue = evaluating, green = swapping, gray = inactive. Lastly, there is a sleep delay value that can be set before running the app so that you can adjust it to suit you.
Here is my attempt, a fully working version, to make the solution "suitably ambiguous" to meet one of the challenge's requirement:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace VisualSort {
public class CodeProjectComparer : IComparer<int> { int IComparer<int>.Compare(int a, int b) => Convert.ToInt32(string.Join("", new[] { a, b })) - Convert.ToInt32(string.Join("", new[] { b, a })); }
public enum SortType { Bubble, Comb, Cycle, Gnome, Insertion, OddEven, Quick, Selection, Shell }
static class Program { static object P = new object(); static int Q { get; set; } static int R { get; set; } static Dictionary<SortType, SortTracker> S = new Dictionary<SortType, SortTracker>(); static List<List<Position>> U = new List<List<Position>>();
static void Main(string[] a) { ucolr = Console.ForegroundColor; ecolr = ConsoleColor.Blue; scolr = ConsoleColor.Green; R = 50; Q = 100; Intro(); PromptUser("-- Press any key to begin --", true); MainAsync().GetAwaiter().GetResult(); PromptUser("-- Press any key to exit --"); }
static async Task MainAsync() { InitPos(); Add(SortType.Bubble, "Bubble Sort Descending"); Add(SortType.Insertion, "Insertion Sort"); Add(SortType.Quick, "Quick Sort"); Add(SortType.Shell, "Shell Sort Descending"); InitArea(); var a = InitTests(); for (int b = 0; b < a.Count; b++) { await ExecuteTestAsync(a[b], string.Format("Running Test: {0} of {1}...", b + 1, a.Count)); if (b < a.Count - 1) PromptUser("-- Press any key to run the next test --"); } }
static async Task ExecuteTestAsync(int[] a, string b) { ClearArea(S.Count); SetAreas(a); await Task.Delay(1000); WriteAt(new Position(5, upos), ucolr, b); await Task.WhenAll(S.Execute(a)); }
static void Add(SortType a, string b) { S.Add(a, new SortTracker(b, ucolr, ecolr, scolr, U[S.Count], new Position(23, 9 + S.Count * 10), Q, WriteAt)); }
static List<int[]> InitTests(int a = 50) { R = a; var b = new Random(); var c = new int[R]; for (int d = 0; d < R; d++) for (;;) { int e = b.Next(1, 255); if (!c.Contains(e)) { c[d] = e; break; } } return new List<int[]>(){new[]{1,5,67,9},new[]{1,5,67,94,96,91,9},new[]{11,112,1,114},new[]{4,45,46,43},new[]{23,232,235,233},new[]{102,1,36,12,21,79,170,9},new[]{3,12,306,12,21,190,170,90},c}; }
static int upos; static ConsoleColor ucolr { get; set; } static ConsoleColor ecolr { get; set; } static ConsoleColor scolr { get; set; }
static void SetAreas(int[] a) { foreach (var tracker in S) for (int b = 0; b < a.Length; b++) WriteAt(tracker.Value.Z[b], tracker.Value.W, a[b].ToString().PadLeft(5)); }
static void ClearArea(int a) { int b = 9; foreach (var tracker in S) { for (int c = 0; c < R; c++) WriteAt(tracker.Value.Z[c], tracker.Value.W, " "); WriteAt(new Position(23, b), tracker.Value.W, "0".PadRight(5)); b += 10; } WriteAt(new Position(5, upos), Console.ForegroundColor, "".PadLeft(40)); }
static void Intro() { Console.WriteLine("CodeProject's Coding challenge: arrange numbers to form the largest possible integer"); Console.WriteLine(""); Console.WriteLine("This is a Visualualisaton of different sorting algorithms on number datasets\r\nthat meet the following requirements:"); Console.WriteLine(""); Console.WriteLine("1. Given a set of integers, arrange the integers so that the final integer\r\n thus formed is the largest number possible."); Console.WriteLine("2. The list may contain up to 50 numbers, and each number will be less than\r\n 256 and positive."); Console.WriteLine(""); Console.WriteLine("There are a number of different sorting algorithms that can be toggled on/off\r\nin the MainAsync method before running."); Console.WriteLine(""); Console.WriteLine("NOTE: It is advisable to adjust the size of the console window to see all\r\nsorts in action at the same time."); Console.WriteLine(""); Console.WriteLine("Enjoy! :)"); Console.WriteLine(""); Console.WriteLine(""); }
static void InitPos() { int a = R < 11 ? R : 10; int b = R < 11 ? 1 : R / 10; for (int c = 0; c < 9; c++) U.Add(new List<Position>()); for (int d = 0; d < b; d++) for (int e = 0; e < a; e++) { int f = 3; foreach (var postion in U) { postion.Add(new Position((e * 5) + 5, d + f)); f += 10; } } }
static void InitArea() { upos = 2 + S.Count * 10; Console.CursorVisible = false; Console.Clear(); var a = Console.ForegroundColor; var b = Console.BackgroundColor; int c = 1, d = 9; foreach (var tracker in S) { Console.BackgroundColor = ConsoleColor.Blue; WriteAt(new Position(5, c), ConsoleColor.White, string.Format(" {0}", tracker.Value.P).PadRight(50)); Console.BackgroundColor = b; WriteAt(new Position(15, d), ConsoleColor.White, "Steps:"); c += 10; d += 10; } ConsoleBox(new Position(60, 3), 17, 8, ConsoleColor.White); Console.BackgroundColor = ConsoleColor.Blue; WriteAt(new Position(61, 4), ConsoleColor.White, " COLOUR LEGEND "); Console.BackgroundColor = b; WriteAt(new Position(64, 6), ucolr, "idle"); WriteAt(new Position(64, 7), ecolr, "Evaluating"); WriteAt(new Position(64, 8), scolr, "Changing"); Console.ForegroundColor = a; }
static void WriteAt(Position a, ConsoleColor b, string c) { lock (P) { Console.ForegroundColor = b; if (a != null) Console.SetCursorPosition(a.C, a.R); Console.Write(c); } }
static void PromptUser(string a, bool b = false) { WriteAt(b ? null : new Position(5, upos), Console.ForegroundColor, a); Console.ReadKey(); }
static void ConsoleBox(Position a, int b, int c, ConsoleColor d) { var e = Console.ForegroundColor; Console.OutputEncoding = Encoding.GetEncoding(866); Console.ForegroundColor = d; int f = b - 2; var g = string.Join("", Enumerable.Range(1, f).Select(h => "─")); var i = new StringBuilder().Append("┌").Append(g).Append("┐\n").ToString(); var j = new StringBuilder().Append("│").Append("".PadLeft(f)).Append("│\n").ToString(); var k = new StringBuilder().Append("└").Append(g).Append("┘").ToString(); Console.SetCursorPosition(a.C, a.R); Console.Write(i); for (int l = 1; l < c; l++) { Console.SetCursorPosition(a.C, a.R + l); Console.Write(j); } Console.SetCursorPosition(a.C, a.R + c - 1); Console.Write(k); Console.ForegroundColor = e; } }
public enum FeedbackType { Eval, Swap, Done }
public class Position { public Position(int c, int r) { C = c; R = r; } public int C { get; set; } public int R { get; set; } }
public class SortTracker { public SortTracker() { }
public SortTracker(string a, ConsoleColor b, ConsoleColor c, ConsoleColor d, List<Position> e, Position f, int g, Action<Position, ConsoleColor, string> h) { P = a; W = b; X = c; Y = d; Z = e; V = g; U = f; Writer = h; S = new[] { -1, -1 }; }
public string P { get; set; } public int Q { get; set; } public int[] R { get; set; } int[] S { get; } Position U; public int V { get; set; } public ConsoleColor W { get; set; } public ConsoleColor X { get; set; } public ConsoleColor Y { get; set; } public List<Position> Z { get; set; } public Action<Position, ConsoleColor, string> Writer { get; set; }
public void a0(int[] a) { R = a; Q = 0; S[0] = -1; S[1] = -1; }
public Task a1(int a, int b, FeedbackType c, bool d) { switch (c) { case FeedbackType.Done: case FeedbackType.Eval: if (S[0] != -1) { Writer(Z[S[0]], W, R[S[0]].ToString().PadLeft(5)); Writer(Z[S[1]], W, R[S[1]].ToString().PadLeft(5)); } if (a != -1) { S[0] = a; S[1] = b; Writer(Z[a], X, R[a].ToString().PadLeft(5)); Writer(Z[b], X, R[b].ToString().PadLeft(5)); } break; case FeedbackType.Swap: if (d) { Writer(Z[S[0]], W, R[S[0]].ToString().PadLeft(5)); Writer(Z[S[1]], W, R[S[1]].ToString().PadLeft(5)); S[0] = a; S[1] = b; } Writer(Z[a], Y, R[a].ToString().PadLeft(5)); Writer(Z[b], Y, R[b].ToString().PadLeft(5)); break; } Writer(U, W, (++Q).ToString("N0")); return Task.Delay(V); } }
public static class SortHelpers { public static Task[] Execute(this Dictionary<SortType, SortTracker> a, int[] b) { var c = new Task[a.Count]; for (int d = 0; d < a.Count; d++) { var e = a.ElementAt(d); e.Value.a0(b.Select(f => f).ToArray()); switch (e.Key) { case SortType.Bubble: c[d] = e.Value.R.Bubble(new CodeProjectComparer(), e.Value.a1); break; case SortType.Comb: c[d] = e.Value.R.Comb(new CodeProjectComparer(), e.Value.a1); break; case SortType.Cycle: c[d] = e.Value.R.Cycle(new CodeProjectComparer(), e.Value.a1); break; case SortType.Gnome: c[d] = e.Value.R.Gnome(new CodeProjectComparer(), e.Value.a1); break; case SortType.Insertion: c[d] = e.Value.R.Insertion(new CodeProjectComparer(), e.Value.a1); break; case SortType.OddEven: c[d] = e.Value.R.OddEven(new CodeProjectComparer(), e.Value.a1); break; case SortType.Quick: c[d] = e.Value.R.Quick(new CodeProjectComparer(), e.Value.a1); break; case SortType.Selection: c[d] = e.Value.R.Selection(new CodeProjectComparer(), e.Value.a1); break; case SortType.Shell: c[d] = e.Value.R.Shell(new CodeProjectComparer(), e.Value.a1); break; } } return c; }
public static Task Bubble<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { for (int d = 0; d < a.Count - 1; d++) for (int e = 1; e < a.Count - d; e++) { if (c != null) await c.Invoke(e, e - 1, FeedbackType.Eval, false); if (b.Compare(a[e], a[e - 1]) > 0) { a.P(e - 1, e); if (c != null) await c.Invoke(e - 1, e, FeedbackType.Swap, false); } } if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); });
public static Task Comb<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { double d = a.Count; var e = true; while (d > 1 || e) { d /= 1.247330950103979; if (d < 1) d = 1; int f = 0; e = false; while (f + d < a.Count) { int g = f + (int)d; if (c != null) await c.Invoke(f, g, FeedbackType.Eval, false); if (b.Compare(a[f], a[g]) < 0) { a.P(f, g); e = true; if (c != null) await c.Invoke(f, g, FeedbackType.Swap, false); } f++; } } if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); });
public static Task Cycle<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { for (int d = 0; d < a.Count; d++) { T e = a[d]; int f = d; do { int g = 0; for (int h = 0; h < a.Count; h++) { if (c != null) await c.Invoke(f, h, FeedbackType.Eval, false); if (h != d && b.Compare(a[h], e) > 0) g++; } if (f != g) { while (f != g && b.Compare(e, a[g]) == 0) { if (c != null) await c.Invoke(f, g, FeedbackType.Eval, false); g++; } T i = a[g]; a[g] = e; e = i; if (c != null) await c.Invoke(f, g, FeedbackType.Swap, true); f = g; } } while (f != d); } if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); });
public static Task Gnome<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { int d = 1; while (d < a.Count) { if (c != null) await c.Invoke(d, d - 1, FeedbackType.Eval, false); if (b.Compare(a[d], a[d - 1]) <= 0) d++; else { a.P(d, d - 1); if (c != null) await c.Invoke(d, d - 1, FeedbackType.Swap, false); if (d > 1) d--; } } if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); });
public static Task Insertion<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { int d; for (int e = 1; e < a.Count; e++) { T f = a[e]; d = e - 1; if (c != null) await c.Invoke(e, d, FeedbackType.Eval, false); while ((d >= 0) && (b.Compare(a[d], f) < 0)) { a[d + 1] = a[d]; if (c != null) await c.Invoke(d + 1, e, FeedbackType.Swap, true); d--; } a[d + 1] = f; if (c != null) await c.Invoke(d + 1, e, FeedbackType.Swap, true); } if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); });
public static Task OddEven<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { var d = false; while (!d) { d = true; for (int e = 1; e < a.Count - 1; e += 2) { if (c != null) await c.Invoke(e, e + 1, FeedbackType.Eval, false); if (b.Compare(a[e], a[e + 1]) < 0) { a.P(e, e + 1); d = false; if (c != null) await c.Invoke(e, e + 1, FeedbackType.Swap, false); } } for (int e = 0; e < a.Count - 1; e += 2) { if (c != null) await c.Invoke(e, e + 1, FeedbackType.Eval, false); if (b.Compare(a[e], a[e + 1]) < 0) { a.P(e, e + 1); d = false; if (c != null) await c.Invoke(e, e + 1, FeedbackType.Swap, false); } } } if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); });
public static Task Quick<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { await a.X(0, a.Count - 1, b, c); if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); });
static async Task X<T>(this IList<T> a, int b, int c, IComparer<T> d, Func<int, int, FeedbackType, bool, Task> e = null) { if (b < c) { int f = await a.Y(b, c, d, e); await a.X(b, f - 1, d, e); await a.X(f + 1, c, d, e); } }
static async Task<int> Y<T>(this IList<T> a, int b, int c, IComparer<T> d, Func<int, int, FeedbackType, bool, Task> e = null) { int f, g; g = c; T h = a[g]; f = b; for (int i = b; i <= (c - 1); i++) { if (e != null) await e.Invoke(i, g, FeedbackType.Eval, false); if (d.Compare(a[i], h) >= 0) { a.P(i, f); if (e != null) await e.Invoke(i, f, FeedbackType.Swap, true); f++; } } a.P(f, g); if (e != null) await e.Invoke(f, g, FeedbackType.Swap, true); return f; }
public static Task Selection<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { for (int d = a.Count - 1; d > 0; d--) { int e = d; for (int f = 0; f <= d; f++) { if (c != null) await c.Invoke(f, e, FeedbackType.Eval, false); if (b.Compare(a[f], a[e]) < 0) e = f; } a.P(d, e); if (c != null) await c.Invoke(d, e, FeedbackType.Swap, false); } if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); });
public static Task Shell<T>(this IList<T> a, IComparer<T> b, Func<int, int, FeedbackType, bool, Task> c = null) => Task.Run(async () => { var d = true; int e = a.Count; while (d || (e > 1)) { d = false; e = (e + 1) / 2; for (int f = 0; f < (a.Count - e); f++) { if (c != null) await c.Invoke(f + e, f, FeedbackType.Eval, false); if (b.Compare(a[f + e], a[f]) > 0) { a.P(f + e, f); d = true; if (c != null) await c.Invoke(f + e, f, FeedbackType.Swap, false); } } } if (c != null) await c.Invoke(-1, -1, FeedbackType.Done, false); }); }
public static class CollectionExtensions { public static void P<T>(this IList<T> a, int b, int c) { if (a.Count < 2 || b == c) return; T d = a[b]; a[b] = a[c]; a[c] = d; } } }
This is a readable version for those who want to be able to read and understand it:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace VisualSort
{
public class CodeProjectComparer : IComparer<int>
{
int IComparer<int>.Compare(int x, int y)
=> Convert.ToInt32(string.Join("", new[] { x, y })) - Convert.ToInt32(string.Join("", new[] { y, x }));
}
public enum SortType
{
Bubble,
Comb,
Cycle,
Gnome,
Insertion,
OddEven,
Quick,
Selection,
Shell
}
static class Program
{
static object lockObj = new object();
static int SleepMS { get; set; }
static int MaxEntries { get; set; } = 50;
static Dictionary<SortType, SortTracker> Trackers = new Dictionary<SortType, SortTracker>();
static List<List<Position>> Positions = new List<List<Position>>();
static void Main(string[] args)
{
SleepMS = 100;
IntroMessage();
PromptUser("-- Press any key to begin --", true);
MainAsync().GetAwaiter().GetResult();
PromptUser("-- Press any key to exit --");
}
static async Task MainAsync()
{
InitPositions();
AddTracker(SortType.Bubble, "Bubble Sort Descending");
AddTracker(SortType.Insertion, "Insertion Sort");
AddTracker(SortType.Quick, "Quick Sort");
AddTracker(SortType.Shell, "Shell Sort Descending");
InitWorkArea();
var tests = InitTests();
for (int i = 0; i < tests.Count; i++)
{
await ExecuteTestAsync(tests[i], $"Running Test: {i + 1} of {tests.Count}...");
if (i < tests.Count - 1)
PromptUser("-- Press any key to run the next test --");
}
}
static async Task ExecuteTestAsync(int[] test, string msg)
{
ClearAreas(Trackers.Count);
SetAreas(test);
await Task.Delay(1000);
WriteAt(new Position(5, promptPosition), unsetColor, msg);
await Task.WhenAll(Trackers.Execute(test));
}
static void AddTracker(SortType type, string Title)
{
Trackers.Add(type, new SortTracker(Title, unsetColor, evalColor, swapColor,
Positions[Trackers.Count], new Position(23, 9 + Trackers.Count * 10), SleepMS, WriteAt));
}
static List<int[]> InitTests(int max = 50)
{
MaxEntries = max;
var r = new Random();
var randomSet = new int[MaxEntries];
for (int i = 0; i < MaxEntries; i++)
{
for (;;)
{
var n = r.Next(1, 255);
if (!randomSet.Contains(n))
{
randomSet[i] = n;
break;
}
}
}
return new List<int[]>()
{
new[] { 1, 5, 67, 9 },
new[] { 1, 5, 67, 94, 96, 91, 9 },
new[] { 11, 112, 1, 114 },
new[] {4, 45, 46, 43},
new[] {23, 232, 235, 233},
new[] { 102, 1, 36, 12, 21, 79, 170, 9 },
new[] { 3, 12, 306, 12, 21, 190, 170, 90 },
randomSet
};
}
#region Console
static int promptPosition;
static ConsoleColor unsetColor { get; } = Console.ForegroundColor;
static ConsoleColor evalColor { get; } = ConsoleColor.Blue;
static ConsoleColor swapColor { get; } = ConsoleColor.Green;
const int Unset = -1;
static void SetAreas(int[] test)
{
foreach (var tracker in Trackers)
for (int i = 0; i < test.Length; i++)
WriteAt(tracker.Value.Positions[i], tracker.Value.UnsetColor, test[i].ToString().PadLeft(5));
}
static void ClearAreas(int count)
{
int yPos = 9;
foreach (var tracker in Trackers)
{
for (int i = 0; i < MaxEntries; i++)
WriteAt(tracker.Value.Positions[i], tracker.Value.UnsetColor, " ");
WriteAt(new Position(23, yPos), tracker.Value.UnsetColor, "0".PadRight(5));
yPos += 10;
}
WriteAt(new Position(5, promptPosition), Console.ForegroundColor, "".PadLeft(40));
}
static void IntroMessage()
{
Console.WriteLine("CodeProject's Coding challenge: arrange numbers to form the largest possible integer");
Console.WriteLine("");
Console.WriteLine("This is a Visualualisaton of different sorting algorithms on number datasets\r\nthat meet the following requirements:");
Console.WriteLine("");
Console.WriteLine("1. Given a set of integers, arrange the integers so that the final integer\r\n thus formed is the largest number possible.");
Console.WriteLine("2. The list may contain up to 50 numbers, and each number will be less than\r\n 256 and positive.");
Console.WriteLine("");
Console.WriteLine("There are a number of different sorting algorithms that can be toggled on/off\r\nin the MainAsync method before running.");
Console.WriteLine("");
Console.WriteLine("NOTE: It is advisable to adjust the size of the console window to see all\r\nsorts in action at the same time.");
Console.WriteLine("");
Console.WriteLine("Enjoy! :)");
Console.WriteLine("");
Console.WriteLine("");
}
static void InitPositions()
{
var cols = MaxEntries < 11 ? MaxEntries : 10;
var rows = MaxEntries < 11 ? 1 : MaxEntries / 10;
for (int i = 0; i < 9; i++)
Positions.Add(new List<Position>());
for (int y = 0; y < rows; y++)
{
for (int x = 0; x < cols; x++)
{
var yOffset = 3;
foreach (var postion in Positions)
{
postion.Add(new Position((x * 5) + 5, y + yOffset));
yOffset += 10;
}
}
}
}
static void InitWorkArea()
{
promptPosition = 2 + Trackers.Count * 10;
Console.CursorVisible = false;
Console.Clear();
var oldColor = Console.ForegroundColor;
var oldBack = Console.BackgroundColor;
int tPos = 1, sPos = 9;
foreach (var tracker in Trackers)
{
Console.BackgroundColor = ConsoleColor.Blue;
WriteAt(new Position(5, tPos), ConsoleColor.White, $" {tracker.Value.Title}".PadRight(50));
Console.BackgroundColor = oldBack;
WriteAt(new Position(15, sPos), ConsoleColor.White, "Steps:");
tPos += 10; sPos += 10;
}
ConsoleBox(new Position(60, 3), 17, 8, ConsoleColor.White);
Console.BackgroundColor = ConsoleColor.Blue;
WriteAt(new Position(61, 4), ConsoleColor.White, " COLOUR LEGEND ");
Console.BackgroundColor = oldBack;
WriteAt(new Position(64, 6), unsetColor, "idle");
WriteAt(new Position(64, 7), evalColor, "Evaluating");
WriteAt(new Position(64, 8), swapColor, "Changing");
Console.ForegroundColor = oldColor;
}
static void WriteAt(Position pos, ConsoleColor color, string msg)
{
lock (lockObj)
{
Console.ForegroundColor = color;
if (pos != null) Console.SetCursorPosition(pos.X, pos.Y);
Console.Write(msg);
}
}
static void PromptUser(string msg, bool isFlow = false)
{
WriteAt(isFlow ? null : new Position(5, promptPosition), Console.ForegroundColor, msg);
Console.ReadKey();
}
static void ConsoleBox(Position pos, int width, int height, ConsoleColor foreColor)
{
var oldColor = Console.ForegroundColor;
Console.OutputEncoding = Encoding.GetEncoding(866);
Console.ForegroundColor = foreColor;
var w = width - 2;
var bar = string.Join("", Enumerable.Range(1, w).Select(_ => "─"));
var top = new StringBuilder().Append("┌").Append(bar).Append("┐\n").ToString();
var row = new StringBuilder().Append($"│{"".PadLeft(w)}│\n").ToString();
var bot = new StringBuilder().Append("└").Append(bar).Append("┘").ToString();
Console.SetCursorPosition(pos.X, pos.Y);
Console.Write(top);
for (int i = 1; i < height; i++)
{
Console.SetCursorPosition(pos.X, pos.Y + i);
Console.Write(row);
}
Console.SetCursorPosition(pos.X, pos.Y + height - 1);
Console.Write(bot);
Console.ForegroundColor = oldColor;
}
#endregion
}
public enum FeedbackType
{
Evaluate,
Swap,
Done
}
public class Position
{
public Position(int x, int y)
{
X = x;
Y = y;
}
public int X { get; set; }
public int Y { get; set; }
}
public class SortTracker
{
public SortTracker() { }
public SortTracker(string title,
ConsoleColor unsetColor, ConsoleColor evalColor, ConsoleColor swapColor,
List<Position> positions, Position stepPos, int sleepMS,
Action<Position, ConsoleColor, string> writer)
{
Title = title;
UnsetColor = unsetColor;
EvalColor = evalColor;
SwapColor = swapColor;
Positions = positions;
SleepMS = sleepMS;
stepPoint = stepPos;
Writer = writer;
}
const int Unset = -1;
public string Title { get; set; }
public int StepCount { get; set; }
public int[] Data { get; set; }
private int[] pointers { get; } = new[] { Unset, Unset };
private Position stepPoint;
public int SleepMS { get; set; }
public ConsoleColor UnsetColor { get; set; }
public ConsoleColor EvalColor { get; set; }
public ConsoleColor SwapColor { get; set; }
public List<Position> Positions { get; set; }
public Action<Position, ConsoleColor, string> Writer { get; set; }
public void SetData(int[] data)
{
Data = data;
StepCount = 0;
pointers[0] = Unset;
pointers[1] = Unset;
}
public Task ReportAsync(int ndx1, int ndx2, FeedbackType feedback, bool alternate)
{
switch (feedback)
{
case FeedbackType.Done:
case FeedbackType.Evaluate:
if (pointers[0] != Unset)
{
Writer(Positions[pointers[0]], UnsetColor, Data[pointers[0]].ToString().PadLeft(5));
Writer(Positions[pointers[1]], UnsetColor, Data[pointers[1]].ToString().PadLeft(5));
}
if (ndx1 != -1)
{
pointers[0] = ndx1;
pointers[1] = ndx2;
Writer(Positions[ndx1], EvalColor, Data[ndx1].ToString().PadLeft(5));
Writer(Positions[ndx2], EvalColor, Data[ndx2].ToString().PadLeft(5));
}
break;
case FeedbackType.Swap:
if (alternate)
{
Writer(Positions[pointers[0]], UnsetColor, Data[pointers[0]].ToString().PadLeft(5));
Writer(Positions[pointers[1]], UnsetColor, Data[pointers[1]].ToString().PadLeft(5));
pointers[0] = ndx1;
pointers[1] = ndx2;
}
Writer(Positions[ndx1], SwapColor, Data[ndx1].ToString().PadLeft(5));
Writer(Positions[ndx2], SwapColor, Data[ndx2].ToString().PadLeft(5));
break;
}
Writer(stepPoint, UnsetColor, (++StepCount).ToString("N0"));
return Task.Delay(SleepMS);
}
}
public static class SortingHelperExtensions
{
public static Task BubbleSortDescendingAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
for (int i = 0; i < collection.Count - 1; i++)
{
for (int index = 1; index < collection.Count - i; index++)
{
await feedbackAsync?.Invoke(index, index - 1, FeedbackType.Evaluate, false);
if (comparer.Compare(collection[index], collection[index - 1]) > 0)
{
collection.Swap(index - 1, index);
await feedbackAsync?.Invoke(index - 1, index, FeedbackType.Swap, false);
}
}
}
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
public static Task CombSortDescendingAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
double gap = collection.Count;
bool swaps = true;
while (gap > 1 || swaps)
{
gap /= 1.247330950103979;
if (gap < 1) gap = 1;
int i = 0;
swaps = false;
while (i + gap < collection.Count)
{
int igap = i + (int)gap;
await feedbackAsync?.Invoke(i, igap, FeedbackType.Evaluate, false);
if (comparer.Compare(collection[i], collection[igap]) < 0)
{
collection.Swap(i, igap);
swaps = true;
await feedbackAsync?.Invoke(i, igap, FeedbackType.Swap, false);
}
i++;
}
}
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
public static Task CycleSortDescendingAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
for (int cycleStart = 0; cycleStart < collection.Count; cycleStart++)
{
T item = collection[cycleStart];
int position = cycleStart;
do
{
int to = 0;
for (int i = 0; i < collection.Count; i++)
{
await feedbackAsync?.Invoke(position, i, FeedbackType.Evaluate, false);
if (i != cycleStart && comparer.Compare(collection[i], item) > 0)
to++;
}
if (position != to)
{
while (position != to && comparer.Compare(item, collection[to]) == 0)
{
await feedbackAsync?.Invoke(position, to, FeedbackType.Evaluate, false);
to++;
}
T temp = collection[to];
collection[to] = item;
item = temp;
await feedbackAsync?.Invoke(position, to, FeedbackType.Swap, true);
position = to;
}
} while (position != cycleStart);
}
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
public static Task GnomeSortDescendingAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
int pos = 1;
while (pos < collection.Count)
{
await feedbackAsync?.Invoke(pos, pos - 1, FeedbackType.Evaluate, false);
if (comparer.Compare(collection[pos], collection[pos - 1]) <= 0)
pos++;
else
{
collection.Swap(pos, pos - 1);
await feedbackAsync?.Invoke(pos, pos - 1, FeedbackType.Swap, false);
if (pos > 1) pos--;
}
}
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
public static Task InsertionSortAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
int j;
for (int i = 1; i < collection.Count; i++)
{
T value = collection[i];
j = i - 1;
await feedbackAsync?.Invoke(i, j, FeedbackType.Evaluate, false);
while ((j >= 0) && (comparer.Compare(collection[j], value) < 0))
{
collection[j + 1] = collection[j];
await feedbackAsync?.Invoke(j + 1, i, FeedbackType.Swap, true);
j--;
}
collection[j + 1] = value;
await feedbackAsync?.Invoke(j + 1, i, FeedbackType.Swap, true);
}
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
public static Task OddEvenSortDescendingAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
bool sorted = false;
while (!sorted)
{
sorted = true;
for (var i = 1; i < collection.Count - 1; i += 2)
{
await feedbackAsync?.Invoke(i, i + 1, FeedbackType.Evaluate, false);
if (comparer.Compare(collection[i], collection[i + 1]) < 0)
{
collection.Swap(i, i + 1);
sorted = false;
await feedbackAsync?.Invoke(i, i + 1, FeedbackType.Swap, false);
}
}
for (var i = 0; i < collection.Count - 1; i += 2)
{
await feedbackAsync?.Invoke(i, i + 1, FeedbackType.Evaluate, false);
if (comparer.Compare(collection[i], collection[i + 1]) < 0)
{
collection.Swap(i, i + 1);
sorted = false;
await feedbackAsync?.Invoke(i, i + 1, FeedbackType.Swap, false);
}
}
}
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
public static Task QuickSortAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
await collection.InternalQuickSortAsync(0, collection.Count - 1, comparer, feedbackAsync);
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
private static async Task InternalQuickSortAsync<T>(this IList<T> collection, int leftmostIndex, int rightmostIndex, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
{
if (leftmostIndex < rightmostIndex)
{
int wallIndex = await collection.InternalPartitionAsync(leftmostIndex, rightmostIndex, comparer, feedbackAsync);
await collection.InternalQuickSortAsync(leftmostIndex, wallIndex - 1, comparer, feedbackAsync);
await collection.InternalQuickSortAsync(wallIndex + 1, rightmostIndex, comparer, feedbackAsync);
}
}
private static async Task<int> InternalPartitionAsync<T>(this IList<T> collection, int leftmostIndex, int rightmostIndex, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
{
int wallIndex, pivotIndex;
pivotIndex = rightmostIndex;
T pivotValue = collection[pivotIndex];
wallIndex = leftmostIndex;
for (int i = leftmostIndex; i <= (rightmostIndex - 1); i++)
{
await feedbackAsync?.Invoke(i, pivotIndex, FeedbackType.Evaluate, false);
if (comparer.Compare(collection[i], pivotValue) >= 0)
{
collection.Swap(i, wallIndex);
await feedbackAsync?.Invoke(i, wallIndex, FeedbackType.Swap, true);
wallIndex++;
}
}
collection.Swap(wallIndex, pivotIndex);
await feedbackAsync?.Invoke(wallIndex, pivotIndex, FeedbackType.Swap, true);
return wallIndex;
}
public static Task SelectionSortDescendingAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
for (int i = collection.Count - 1; i > 0; i--)
{
int max = i;
for (int j = 0; j <= i; j++)
{
await feedbackAsync?.Invoke(j, max, FeedbackType.Evaluate, false);
if (comparer.Compare(collection[j], collection[max]) < 0)
max = j;
}
collection.Swap(i, max);
await feedbackAsync?.Invoke(i, max, FeedbackType.Swap, false);
}
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
public static Task ShellSortDescendingAsync<T>(this IList<T> collection, IComparer<T> comparer, Func<int, int, FeedbackType, bool, Task> feedbackAsync = null)
=> Task.Run(async () =>
{
bool flag = true;
int d = collection.Count;
while (flag || (d > 1))
{
flag = false;
d = (d + 1) / 2;
for (int i = 0; i < (collection.Count - d); i++)
{
await feedbackAsync?.Invoke(i + d, i, FeedbackType.Evaluate, false);
if (comparer.Compare(collection[i + d], collection[i]) > 0)
{
collection.Swap(i + d, i);
flag = true;
await feedbackAsync?.Invoke(i + d, i, FeedbackType.Swap, false);
}
}
}
await feedbackAsync?.Invoke(-1, -1, FeedbackType.Done, false);
});
public static Task[] Execute(this Dictionary<SortType, SortTracker> trackers, int[] data)
{
var tasks = new Task[trackers.Count];
for (int i = 0; i < trackers.Count; i++)
{
var tracker = trackers.ElementAt(i);
tracker.Value.SetData(data.Select(x => x).ToArray());
switch (tracker.Key)
{
case SortType.Bubble:
tasks[i] = tracker.Value.Data.BubbleSortDescendingAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
case SortType.Comb:
tasks[i] = tracker.Value.Data.CombSortDescendingAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
case SortType.Cycle:
tasks[i] = tracker.Value.Data.CycleSortDescendingAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
case SortType.Gnome:
tasks[i] = tracker.Value.Data.GnomeSortDescendingAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
case SortType.Insertion:
tasks[i] = tracker.Value.Data.InsertionSortAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
case SortType.OddEven:
tasks[i] = tracker.Value.Data.OddEvenSortDescendingAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
case SortType.Quick:
tasks[i] = tracker.Value.Data.QuickSortAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
case SortType.Selection:
tasks[i] = tracker.Value.Data.SelectionSortDescendingAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
case SortType.Shell:
tasks[i] = tracker.Value.Data.ShellSortDescendingAsync(new CodeProjectComparer(), tracker.Value.ReportAsync);
break;
}
}
return tasks;
}
}
public static class CollectionExtensions
{
public static void Swap<T>(this IList<T> list, int firstIndex, int secondIndex)
{
if (list.Count < 2 || firstIndex == secondIndex) return;
var temp = list[firstIndex];
list[firstIndex] = list[secondIndex];
list[secondIndex] = temp;
}
}
}
Static output does not convey how it perfoms but here is sample Output:
.
Bubble Sort Descending
9 95 94 93 89 8 84 63 55 52 ┌───────────────┐
51 44 30 254 252 244 24 237 236 234 │ COLOUR LEGEND │
229 227 222 216 214 21 205 201 196 189 │ │
180 178 174 172 17 171 170 156 153 146 │ idle │
14 137 136 132 127 126 124 121 112 100 │ Evaluating │
│ Changing │
Steps: 1,760 │ │
└───────────────┘
Comb Sort Descending
9 95 94 93 89 8 84 63 55 52
51 44 30 254 252 244 24 237 236 234
229 227 222 216 214 21 205 201 196 189
180 178 174 172 17 171 170 156 153 146
14 137 136 132 127 126 124 121 112 100
Steps: 797
Cycle Sort Descending
9 95 94 93 89 8 84 63 55 52
51 44 30 254 252 244 24 237 236 234
229 227 222 216 214 21 205 201 196 189
180 178 174 172 17 171 170 156 153 146
14 137 136 132 127 126 124 121 112 100
Steps: 4,547
Gnome Sort Descending
9 95 94 93 89 8 84 63 55 52
51 44 30 254 252 244 24 237 236 234
229 227 222 216 214 21 205 201 196 189
180 178 174 172 17 171 170 156 153 146
14 137 136 132 127 126 124 121 112 100
Steps: 1,649
Insertion Sort
9 95 94 93 89 8 84 63 55 52
51 44 30 254 252 244 24 237 236 234
229 227 222 216 214 21 205 201 196 189
180 178 174 172 17 171 170 156 153 146
14 137 136 132 127 126 124 121 112 100
Steps: 633
Odd-Even Sort Descending
9 95 94 93 89 8 84 63 55 52
51 44 30 254 252 244 24 237 236 234
229 227 222 216 214 21 205 201 196 189
180 178 174 172 17 171 170 156 153 146
14 137 136 132 127 126 124 121 112 100
Steps: 1,711
Quick Sort
9 95 94 93 89 8 84 63 55 52
51 44 30 254 252 244 24 237 236 234
229 227 222 216 214 21 205 201 196 189
180 178 174 172 17 171 170 156 153 146
14 137 136 132 127 126 124 121 112 100
Steps: 424
Selection Sort Descending
9 95 94 93 89 8 84 63 55 52
51 44 30 254 252 244 24 237 236 234
229 227 222 216 214 21 205 201 196 189
180 178 174 172 17 171 170 156 153 146
14 137 136 132 127 126 124 121 112 100
Steps: 1,324
Shell Sort Descending
9 95 94 93 89 8 84 63 55 52
51 44 30 254 252 244 24 237 236 234
229 227 222 216 214 21 205 201 196 189
180 178 174 172 17 171 170 156 153 146
14 137 136 132 127 126 124 121 112 100
Steps: 722
-- Press any key to exit --
To watch multiple sorts at the same time, I recommend selecting 3 or 4 differnt types of sorts plus resizing the console window before the they run. If you have the screen resolution (or set a very small font size), you could run all 9 at the same time like above!
Enjoy!