using System;
using System.Linq;
using System.Text.Json;
// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass
static int[] Sort(int[] arr) {
var items = new int[arr.Length];
arr.CopyTo(items, 0);
for (int end = items.Length; end > 1; end--) {
var swapped = false;
for (int j = 1; j < end; j++) {
if (items[j] < items[j - 1]) {
var tmp = items[j];
items[j] = items[j - 1];
items[j - 1] = tmp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
return items;
}
var items = new[] { 4, 1, 5, 3, 2 };
var sortItems = Sort(items);
// sortItems is {1, 2, 3, 4, 5}
Console.WriteLine(JsonSerializer.Serialize(sortItems));
// *** simplified speed test ***
items = (new int[200]).Select((_, i) => 199 - i).ToArray();
var count = 10000;
var start = DateTime.Now;
for (int i = 0; i < count; i++)
Sort(items);
var delta = DateTime.Now - start;
var milliseconds = delta.TotalMilliseconds;
Console.WriteLine($"{milliseconds} milliseconds");
// about 235 milliseconds