Короче говоря, я придумал этот алгоритм, но сомневаюсь, что что-то изобрел. Так как же это называется?
Я знаю, что у него много ограничений во многих областях. Например, эта реализация не может сортировать числа, превышающие UInt16, и ограничена максимумом случаев int.MaxValue. У меня также может быть где-нибудь проблема с границами массива. И он уже ест оперативную память как торт:)
Фактический алгоритм реализован в методе CustomSort. Остальное - код, который я использовал для тестирования.
class Program
{
static Random r = new Random((int)DateTime.Now.Ticks);
static int[] GetRandomIntegers(int count)
{
int[] result = new int[count];
for (int i = 0; i < count; i++)
{
int randomNumber = r.Next(0, UInt16.MaxValue);
result[i] = randomNumber;
}
return result;
}
public static int[] CustomSort(int[] itemsToSort)
{
// Consider each number in the array to sort as a "memory address" or index of a huge array
// which has a default value of zero and gets incremented every time that number is encountered
// Example:
// Array to sort: 5, 2, 2, 7, 5, 1, 3
// Create an array of at most 7 dimensions.
// Since that number takes time to find, bind the algorithms limit of maximum numbers to UInt16 and skip that step. Prefer more ram over processor time :)
// First item, 5 encountered - Take index 5 in result array and add one, result is 1
// Second item, 2 encountered - Take index 2 in result array and add one, result is 1
// Third item, 2 encountered - Take index 2 in result array and add one, result is 2
// Loop until done
// Now the temp array will contain how many times each number was encountered. The array index is the number itself, and traversing the array from 0 to N
// will provide the count of how many times that number was encountered
// For each number not encountered the value at index will stay 0 and just consume RAM :)
int[] temp = new int[UInt16.MaxValue];
for (int i = 0; i < itemsToSort.Length; i++)
{
temp[itemsToSort[i]]++;
}
// Final step, create resulting sorted array by looping over the temp array and creation of that many items as the value of the current index
int[] result = new int[itemsToSort.Length];
int current = 0;
for (int i = 0; i < UInt16.MaxValue; i++)
{
int count = temp[i];
for (int j = 0; j < count; j++)
{
result[current] = i;
current++;
}
}
return result;
}
static void Main(string[] args)
{
Stopwatch watch = new Stopwatch();
watch.Start();
int[] sortMe = GetRandomIntegers(1000000000);
int[] arraySorted = new int[sortMe.Length];
watch.Stop();
Console.WriteLine($"Random generation of '{sortMe.Length}' elements took: {watch.Elapsed}");
Array.Copy(sortMe, 0, arraySorted, 0, sortMe.Length);
watch.Restart();
Array.Sort(arraySorted);
watch.Stop();
Console.WriteLine("Array sort(Heap/Quicksort) took: " + watch.Elapsed);
watch.Restart();
int[] mySorted = CustomSort(sortMe);
watch.Stop();
Console.WriteLine("Custom sort took: " + watch.Elapsed);
watch.Restart();
bool isEqual = Enumerable.SequenceEqual(mySorted, arraySorted);
watch.Stop();
Console.WriteLine($"Equality check: {isEqual} took: {watch.Elapsed}");
Console.WriteLine("Done");
Console.ReadLine();
}
}