3

Long story short, I came up with this algorithm, but I doubt that I invented something. So what's the name of this?

I know it has a lot of restrictions in multiple areas. For instance this implementation can not sort numbers higher than UInt16, and is limited to a maximum of int.MaxValue occurences. I also might have some array boundary issue somewhere. And it already eats RAM like cake :)

The actual algorithm is implemented in the CustomSort method. The rest is the code I used for testing.

  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();
        }
    }
0

3 Answers 3

6

The algorithm you’ve come up with is counting sort!

Sign up to request clarification or add additional context in comments.

Comments

1

It's called the Counting Sort. There is also a modification of this algorithm, called Radix Sort. More details: https://www.geeksforgeeks.org/radix-sort/

Comments

-1

You've got it. Thank you very much!

In summary the algorithm I got is Counting-Sort

And an improved implementation is Radix-Sort

I guess this can be closed.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.