1
\$\begingroup\$

Here I've prepared my solutions for the following algorithms, and was curious if there were a way to optimize any of them. Any input is welcome and appreciated!

using System;
using System.Collections.Generic;
using System.Linq;

namespace algotest
{
    class Program
    {
        static void InsertionSort(int[] arr)
        {
            for (int i = 1; i < arr.Length; ++i)
            {
                int temp = arr[i];
                bool sorted = false;

                for (int j = i - 1; j >= 0 && !sorted;)
                {
                    if (temp < arr[j])
                    {
                        arr[j + 1] = arr[j];
                        --j;
                        arr[j + 1] = temp;
                    }
                    else
                    {
                        sorted = true;
                    }
                }
            }
        }

        static void BubbleSort(int[] arr)
        {
            int temp = 0;

            for (int i = 0; i < arr.Length; ++i)
            {
                for (int j = 0; j < arr.Length - 1; ++j)
                {
                    if (arr[j] > arr[j + 1])
                    {
                        temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }

        static void SelectionSort(int[] arr)
        {
            int temp, min;

            for (int i = 0; i < arr.Length - 1; ++i)
            {
                min = i;

                for (int j = i + 1; j < arr.Length; ++j)
                {
                    if (arr[j] < arr[min])
                    {
                        min = j;
                    }
                }

                temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }

        static void Merge(int[] arr, int left, int pivot, int right)
        {
            int[] temp = new int[25];
            int index = left;
            int leftBound = pivot - 1;
            int length = right - left + 1;

            while (left <= leftBound && pivot <= right)
            {
                if (arr[left] <= arr[pivot])
                {
                    temp[index++] = arr[left++];
                }
                else
                {
                    temp[index++] = arr[pivot++];
                }
            }

            while (left <= leftBound)
            {
                temp[index++] = arr[left++];
            }

            while (pivot <= right)
            {
                temp[index++] = arr[pivot++];
            }

            for (int i = 0; i < length; i++)
            {
                arr[right] = temp[right];
                right--;
            }
        }

        static void MergeSort(int[] arr, int left, int right)
        {
            if (right > left)
            {
                int pivot = (right + left) / 2;
                MergeSort(arr, left, pivot);
                MergeSort(arr, pivot + 1, right);
                Merge(arr, left, pivot + 1, right);
            }
        }

        static void QuickSort(int[] arr, int left, int right)
        {
            int i = left, j = right;
            int pivot = arr[(left + right) / 2];

            while (i <= j)
            {
                while (arr[i].CompareTo(pivot) < 0)
                {
                    ++i;
                }

                while (arr[j].CompareTo(pivot) > 0)
                {
                    --j;
                }

                if (i <= j)
                {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;

                    ++i;
                    --j;
                }
            }

            if (left < j)
            {
                QuickSort(arr, left, j);
            }

            if (i < right)
            {
                QuickSort(arr, i, right);
            }
        }

        static void Heapify(int[] arr, int i, int n)
        {
            try
            {
                int temp = arr[i];
                int j = 2 * i;

                while (j <= n)
                {
                    if (j < n && arr[j] < arr[j + 1])
                    {
                        j++;
                    }

                    if (temp >= arr[j])
                    {
                        break;
                    }

                    arr[j / 2] = arr[j];
                    j *= 2;
                }

                arr[j / 2] = temp;
            }
            catch (IndexOutOfRangeException err)
            {
                Console.WriteLine("Array Out of Bounds ", err);
            }
        }

        static void HeapSort(int[] arr)
        {
            for (int i = arr.Length / 2; i >= 0; --i)
            {
                Heapify(arr, i, arr.Length - 1);
            }

            for (int i = arr.Length - 2; i >= 0; --i)
            {
                int temp = arr[i + 1];
                arr[i + 1] = arr[0];
                arr[0] = temp;

                Heapify(arr, 0, i);
            }
        }

        static void CountingSort(int[] arr)
        {
            int[] count = new int[arr.Max() + 1];

            for (int i = 0; i < arr.Length; ++i)
            {
                ++count[arr[i]];
            }

            int j = 0;

            for (int i = 0; i < count.Length; ++i)
            {
                for (int k = 0; k < count[i]; ++k)
                {
                    arr[j++] = i;
                }
            }
        }

        static void RadixSort(int[] arr)
        {
            int i, j;
            int[] temp = new int[arr.Length];

            for (int shift = 31; shift > -1; --shift)
            {
                j = 0;

                for (i = 0; i < arr.Length; ++i)
                {
                    bool move = (arr[i] << shift) >= 0;

                    if (shift == 0 ? !move : move)
                    {
                        arr[i - j] = arr[i];
                    }
                    else
                    {
                        temp[j++] = arr[i];
                    }
                }

                Array.Copy(temp, 0, arr, arr.Length - j, j);
            }
        }

        static void BucketSort(int[] arr)
        {
            // bucket size key:
            // array 1-99 ; 10 buckets
            // arrat 100-199 ; 20 buckets
            // etc.
            // TODO: Implement logic to determine bucket size?

            int numOfBuckets = 10;
            List<int> result = new List<int>();
            List<int>[] buckets = new List<int>[numOfBuckets];

            for (int i = 0; i < numOfBuckets; ++i)
            {
                buckets[i] = new List<int>();
            }

            for (int i = 0; i < arr.Length; ++i)
            {
                int index = arr[i] / numOfBuckets;
                buckets[index].Add(arr[i]);
            }

            for (int i = 0; i < numOfBuckets; ++i)
            {
                int[] temp = buckets[i].ToArray();
                InsertionSort(arr);
                result.AddRange(temp);
            }

            arr = result.ToArray();
        }

        static void Main(string[] args)
        {
            Console.WriteLine("Please select an algorithm: ");
            Console.WriteLine("I : InsertionSort O(n^2)");
            Console.WriteLine("B : BubbleSort O(n^2)");
            Console.WriteLine("S : SelectionSort O(n^2)");
            Console.WriteLine("M : MergeSort O(nlgn)");
            Console.WriteLine("Q : QuickSort O(nlgn)");
            Console.WriteLine("H : HeapSort O(nlgn)");
            Console.WriteLine("C : CountingSort O(n)");
            Console.WriteLine("R : RadixSort O(n)");
            Console.WriteLine("U : BucketSort O(n)");

            string algorithm = Console.ReadLine().ToUpper();

            Console.WriteLine("How many elements?");

            int numOfElements = int.Parse(Console.ReadLine());
            int[] arr = new int[numOfElements];
            Random rand = new Random();

            Console.WriteLine("Generating random data...");

            for (int i = 0; i < numOfElements; ++i)
            {
                arr[i] = rand.Next(100);
            }

            switch (algorithm)
            {
                case "I":
                    InsertionSort(arr);
                    break;
                case "B":
                    BubbleSort(arr);
                    break;
                case "S":
                    SelectionSort(arr);
                    break;
                case "M":
                    MergeSort(arr, 0, arr.Length - 1);
                    break;
                case "Q":
                    QuickSort(arr, 0, arr.Length - 1);
                    break;
                case "H":
                    HeapSort(arr);
                    break;
                case "C":
                    CountingSort(arr);
                    break;
                case "R":
                    RadixSort(arr);
                    break;
                case "U":
                    BucketSort(arr);
                    break;
            }

            for (int i = 0; i < arr.Length; ++i)
            {
                Console.WriteLine(arr[i]);
            }

            Console.WriteLine("Press any key to exit.");
            Console.ReadKey();
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Define optimize(goal?). Have ordered items at both ends with insertion sort to almost half the number of assignments (first step towards Library_sort). Select min and max concurrently in selection sort, comparing only the lesser of each pair of input items to min, the greater to max to save one fourth on comparisons. (Next step is to keep pairs ordered to avoid the next quarter: first step to Heapsort.) Annoyingly effective: "bubbling up" candidates. Iterate on quicksort's larger partition. \$\endgroup\$ – greybeard Sep 23 '17 at 9:36
  • \$\begingroup\$ (I expected "the optimistic approach to insertion into a heap" to be commented in at least one answer - didn't see that. Improvement: take the pessimistic/realistic approach: just assume the child of higher priority to have priority over the new item, and only start comparing the latter once the "highest priority path to a leaf" is known.) \$\endgroup\$ – greybeard Sep 23 '17 at 10:05
  • 1
    \$\begingroup\$ That does not look like a proper bubble sort to me. en.wikipedia.org/wiki/Bubble_sort \$\endgroup\$ – paparazzo Sep 23 '17 at 14:04
  • 1
    \$\begingroup\$ @greybeard That looks like it needs to be an answer! :P \$\endgroup\$ – T145 Sep 23 '17 at 22:59
  • \$\begingroup\$ @Paparazzi Use the program for debugging the algorithms; I assure you it works. \$\endgroup\$ – T145 Sep 23 '17 at 23:00
3
\$\begingroup\$

Insertion sort

You don't need the flag variable sorted. Instead of sorted = true, you can simply break out of the loop.

Many times flag variables can be avoided, and result in simpler, more readable solutions. Always look suspiciously at flag variables.

Merge sort

The number 25 in int[] temp = new int[25] looks arbitrary. Why is it 25?

Note that this may lead to integer overflow, a common pitfall in merge sort implementations:

int pivot = (right + left) / 2;

The fix is simple enough:

int pivot = left + (right - left) / 2;

Counting sort

The implementation allocates an array of size arr.Max() + 1 as storage. It would be good to also take into account arr.Min(), to avoid allocating much more space than necessary.

Furthermore, the current implementation will crash if the input contains negative numbers. That's another reason to consider arr.Min() too.

\$\endgroup\$
1
\$\begingroup\$

Insertion sort

You appear to be writing the moving element repeatedly, which isn't needed, and as mentioned there is a sorted flag you don't need, so you can break out of the loop to place the moving element.

    static void InsertionSort(int[] arr)
    {
        for (int i = 1; i < arr.Length; ++i)
        {
            int temp = arr[i];
            int j = i - 1;

            while (j >= 0)
            {
                if (temp >= arr[j])   break; // found insertion point

                arr[j + 1] = arr[j];
                --j;
            }
            arr[j + 1] = temp;
        }
    }

Bubble sort

Normally bubble sort refers to swapping adjacent elements. It can be optimized by tracking the last swap.

    static void BubbleSort(int[] arr)
    {
        int endPt = arr.Length - 1;
        while (endPt > 0)
        {
            int lastSwap = 0;
            for (int j = 0; j < endPt; ++j)
            {
                if (arr[j] > arr[j+1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    lastSwap = j;
                }
            }
            endPt = lastSwap;
        }
    }

Selection sort

No issues, although you have variables declared a little further from their point of use than in the previous routines.

... I might look at some more later.

\$\endgroup\$
  • \$\begingroup\$ I think you meant for the arr[j + 1] = temp; to be in the for-loop. Also, for your Insertion sort critique, I get the following when I run my solution: i.imgur.com/fMtMEq5.png and this when I run yours: i.imgur.com/fO1O3f2.png \$\endgroup\$ – T145 Sep 23 '17 at 7:33
  • \$\begingroup\$ Yes, I was trying too hard for minimal changes, apologies - the j variable should persist for the update subsequent to the loop. \$\endgroup\$ – Joffan Sep 23 '17 at 8:11
  • \$\begingroup\$ @T145 note that your edit was overwritten by the edit I was making at the same time, which was not the same. \$\endgroup\$ – Joffan Sep 23 '17 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.