Selection sort in C#

Selection sort - overview

Selection sort is an in-place comparison sort and it is quite simple and intuitive. It is inefficient for large lists and should thus only be used for arrays with a small numbers of items.

Description of the selection sort algorithm

Selection sort views the input array as two separate sublists. The list to the left contains the values that are already sorted. The values are sorted from left to right.

The list to the right contains the values remaining to be sorted.

Initially the array to the left is empty and the rest of the list constitutes the full input array.

Next, the algorithm will loop through all positions in the array from left to right and for each value it tries to find the smallest value in the right sublist and change places with the value at the current position.

Computational complexity

It is easy to show that selection sort has has a complexity of  O(n²) for all cases.

Example of an implementation of selection sort in C#

    private void SortArrayWithSelectionSort()
    {
        int[] array = { 7, 5, 23, 2, 0 };
        SelectionSort(array);

        // PrintResult(array);
    }

    private void SelectionSort(int[] a)
    {
        int minPos;
        int minVal;

        for (int i = 0; i < a.Length - 1; i++)
        {
            minPos = i;
            minVal = a[i];

            for (int j = i + 1; j < a.Length; j++)
            {
                if (a[j] < a[i] && a[j] < minVal)
                {
                    minPos = j;
                    minVal = a[j];
                }
            }

            SwapValues(a, i, minPos);
        }
    }

    private void SwapValues(int[] a, int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

Shell sort in C#

Shell sort - overview

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an in-place comparison sort.

Shell noticed that the two other sorting algorithms bubble sort and insertion sort only moved elements one location at a time. It means that each element must move quite far before it finds its correct location. With Shells algorithm it is possible for elements to jump several locations at a time, which improves the execution time.

Shell sort can be viewed as a generalized version of insertion sort.

Description of the Shell sort algorithm

Shell sort works in the same way as insertion sort, but with the difference that the outer loop in insertion sort is surrounded with another loop. This extra loop is called the gap loop.

Instead of sorting values one by one, as in the insertion sort algorithm, we can now perform an insertion sort every g values (where g is equal to the gap value).

After each round of sorting g should be decreased. Shell suggested the following gap sequence:

N/2, N/4, ... , 1

The last round always has a gap size of 1, and that corresponds to a round with the original insertion sort. The previous sorting rounds makes the array almost sorted so that the array is prepared for the final round, so that it does not have to move the elements very far. Insertion sort is namely very quick if the elements in the array are already "roughly" sorted.

Any diminishing sequence can be used as gap sequence as long as the last value is 1. However, the computational complexity is quite dependent on the gap sequence. For example, instead of dividing the value by 2, the value 2.2 could be used. It has been shown that that value gives better performance than 2.

Computational complexity

Worst case performance is O(n²). Best case performance O(n log n). Average case performance depends on selection of gap sequence.

Example of an implementation of Shell sort in C#

    private void SortArrayWithShellSort()
    {
        int[] array = { 7, 5, 17 };
        ShellSort(array);

        // PrintResult(array);
    }
        
    private void ShellSort(int[] array)
    {
        int n = array.Length;
        int gap = n / 2;
        int temp;

        while (gap > 0)
        {
            for (int i = 0; i + gap < n; i++)
            {
                int j = i + gap;
                temp = array[j];

                while (j - gap >= 0 && temp < array[j - gap])
                {
                    array[j] = array[j - gap];
                    j = j - gap;
                }

                array[j] = temp;
            }

            gap = gap / 2;
        }
    }

Insertion sort in C#

Insertion sort - overview

Insertion sort is a sorting algoritm with a simple implementation. It is pretty efficient when the array to be sorted contains a small number of elements. It is also efficient when the array is already almost sorted.

Description of the insertion sort algorithm

Insertion sort works in almost the same way as when a person wants to sort a hand of for example 5 playing cards.

First the left hand holds no cards and the 5 cards are lying face down on the table. Then we pick one card at a time from the table. To find the position of the card we compare it with the cards in the left hand, from the right to the left. Throughout the algorithm the cards in the left hand will always be sorted.

Insertion sort is an in-place algorithm

The sorting is performed in place. It means that the numbers are moved around within the array. Because of that it requires only a constant amount O(1) of memory space.

Computational complexity

The best case performance is when the input array is already sorted. In that case the algorithm only needs to do O(n) work.

For worst and average case the algorithm has a complexity of  O(n²).

Example of an implementation of insertion sort in C#

    private void SortArrayWithInsertionSort()
    {
        int[] array = { 7, 5, 17, 3, 1, 4, 4 };
        InsertionSort(array);

        // PrintResult(array);
    }

    private void InsertionSort(int[] array)
    {
        int j;
        int temp;

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

Merge sort in C#

Merge sort - overview

Merge sort is a comparison based divide-and-conquer sorting algoritm. It was invented by John von Neumann in 1945. It is also a stable algorithm, which means that the order of equal elements in the input array will be kept so that it is the same after sorting.

The algorithm is based on the fact that two ordered arrays can be merged pretty quickly and easy. One just loops through the two arrays in parallel och copies the smallest value of the two arrays into a third array. The algorithm then uses recursive divide-and-conquer methodology to get the sorting done.

Description of the merge sort algorithm

The algorithm works like this:

1. The unsorted input array is recursively divided into n subarrays containing one element each. A list with only 1 element is considered to be sorted.
2. The subarrays are merged to produce new sorted subarrays until there is only one array left.

Computational complexity

In each recursion level merging is performed. Since merging is a linear operation, at each level we are doing O(n) work.

In each recursive step we are dividing the size of the input in half. Therefore there will be O(log n) recursive calls.

The number of recursive calls multiplied with the work at each level thus gives us the total complexity of O(n log n).

Example of an implementation of merge sort in C#

    private void SortArrayWithMergeSort()
    {
        int[] array = { 7, 5, 17, 3, 1 };

        int low = 0;
        int hi = array.Length - 1;

        MergeSort(array, low, hi);

        // PrintResult(array);
    }

    public void MergeSort(int[] array, int low, int hi)
    {
        if (hi - low <= 0)
        {
            return;
        }

        int mid = (low + hi) / 2;
        MergeSort(array, low, mid);
        MergeSort(array, mid + 1, hi);
        Merge(array, low, mid + 1, hi);
    }

    private void Merge(int[] array, int low, int mid, int hi)
    {
        int[] temp = new int[array.Length];
        int tempCount = low;
        int i = low;
        int j = mid;

        while (i < mid && j <= hi)
        {
            if (array[i] <= array[j])
            {
                temp[tempCount++] = array[i++];
            }
            else
            {
                temp[tempCount++] = array[j++];
            }
        }

        while (i < mid)
        {
            temp[tempCount++] = array[i++];
        }

        while (j <= hi)
        {
            temp[tempCount++] = array[j++];
        }

        for (int k = low; k <= hi; k++)
        {
            array[k] = temp[k];
        }   
    }

Radix sort in C#

Radix sort - overview

Radix sort is a non-comparative technique for ordering a list of positive integers. It dates back to 1887 when Herman Hollerith invented a machine that could sort punchcards using the very same algorithm. That makes it one of the oldest sorting algorithms.

Radix sort works in a pretty straight-forward way and is quite efficient compared to for example the comparison based algorithms.

Radix sort is actually a category of sorting algorithms, not just a single algorithm. There are two types of radix sorts: LSD (least significant digit) and MSD (most significant digit). Here we will mostly consider the LSD variant of the algorithm.

Radix sort is a stable sorting algorithm

Radix sort is an example a a stable sorting algorithm. A sorting algorithm is said to be stable if two objects with the same keys appear in the exact same order in the sorted output array as they appear in the input array.

Computational complexity

The algorithms efficiency is O(kn) for n keys which consists of k number of digits or less. This means that it often is faster than the comparison-based sort algorithms, who often have a complexity of O(n log n).

Description of the LSD radix sorting algorithm

Lets say that we have an array with the following integer values: [132, 534, 612, 774, 599]. The algorithm starts by examining all the values at the least significant position. All the keys with the same value on that position will be grouped together. We have 10 groups, one for each integer value. In the C# code example below we refer to each group as a "bucket".

After this first round we would have the following grouping:

Group   Keys
0
1
2            132, 612
3
4            534, 774
5
6
7
8
9            599

In the next round LSD radix sort will check the next position and group by that value. Since it is a stable algorithm it will retain the relative position of elements set by the previous pass.

After the second round we will have this grouping:

Group   Keys
0
1            612
2          
3            132, 534
4          
5
6
7            774
8
9            599


In this case all keys consist of 3 digits, so next round will be the last one. It will now check the third value, which in this case is the most significant digit and group by that.

Again we keep the previous relative ordering and get the following:

Group   Keys
0
1            132    
2          
3          
4          
5            534, 599
6            612
7            774
8
9

So after three rounds we now have an ordered collection and the sorting is finished.

Example of an implementation of radix sort in C#

    private void SortArrayWithRadixSort()
    {
        int[] array = { 7, 5, 3, 6, 76, 45, 32 };
        int[] sortedArray = RadixSort(array);

        // PrintResult(sortedArray);
    }
    
    public int[] RadixSort(int[] array)
    {
        bool isFinished = false;
        int digitPosition = 0;

        List<Queue<int>> buckets = new List<Queue<int>>();
        InitializeBuckets(buckets);

        while (!isFinished)
        {
            isFinished = true;

            foreach (int value in array)
            {
                int bucketNumber = GetBucketNumber(value, digitPosition);
                if (bucketNumber > 0)
                {
                    isFinished = false;
                }

                buckets[bucketNumber].Enqueue(value);
            }

            int i = 0;
            foreach (Queue<int> bucket in buckets)
            {
                while (bucket.Count > 0)
                {
                    array[i] = bucket.Dequeue();
                    i++;
                }
            }

            digitPosition++;
        }

        return array;
    }

    private int GetBucketNumber(int value, int digitPosition)
    {
        int bucketNumber = (value / (int)Math.Pow(10, digitPosition)) % 10;
        return bucketNumber;
    }

    private static void InitializeBuckets(List<Queue<int>> buckets)
    {
        for (int i = 0; i < 10; i++)
        {
            Queue<int> q = new Queue<int>();
            buckets.Add(q);
        }
    }

Bubble sort in C#

Bubble sort - overview

Bubble sort is a simple sorting algorithm. It is used to sort an array of for example integers or strings.

Description of the bubble sort algorithm

Bubble sort starts by comparing the first two elements in the array. If the first element is greater than the second, the two values are swapped.

Then the algorithm moves to the next position in the array. It will compare the next two adjacent values and swap them if they are in the wrong order. It will continue doing this until the end of the array has been reached.

After one round is finished another round is started. The first two elements are compared and swapped if necessary, then it moves to the next position, then to the next, and so on.

In this way each round will "bubble" larger elements to the right and the array becomes more and more sorted.

When one sorting round has finished without any swaps it means that the array is sorted, and the bubble sort algorithm has finished its task.

Computational complexity

The algorithms average and worst-case performance is O(n²), which is quite bad compared to other algorithms. So if you want to use bubble sort then you should generally only use it to sort a small number of items.

One situtation when bubble sort actually has good performance is when the array contains elements that are almost sorted. Consider for example the following array: [1, 2, 4, 3]. In this case, where only one number is out of place by only one position, the algorithm would order the elements by one sorting round. In the second round of the algorithm no swaps would be performed, which means that the array is now sorted. In that case the algorithm runs in only 2n time.

Example of an implementation of bubble sort in C#

   private void SortArrayWithBubbleSort()
   {
       int[] array = { 7, 5, 3, 6, 6, 2 };
       int[] sortedArray = BubbleSort(array);

       // PrintResult(sortedArray);         
   }

   private int[] BubbleSort(int[] array)
   {
       for (int i = 0; i < array.Length - 1; i++)
       {
           bool swapped = false;

           for (int j = 0; j < array.Length - 1; j++)
           {
               if (array[j] > array[j + 1])
               {
                   SwapValues(array, j);
                   swapped = true;
               }
           }

           if (!swapped)
           {
               break;
           }
       }

       return array;
   }

   private static void SwapValues(int[] arr, int i)
   {
       int temp = arr[i + 1];
       arr[i + 1] = arr[i];
       arr[i] = temp;
   }

A possible optimization of bubble sort

After the first loop in the algorithm the last position in the array will always contain the largest element in the array. After the second loop the second last position will contain the second largest element and so on.

This behaviour could be described as "the n-th pass finds the n-th largest element and puts it into its final place" (from Wikipedia).

This means that the inner loop can avoid looking at the last n-1 items when running for the n-th time, since those items are already correctly sorted and placed at their final destination in the array.

In the following code example this optimization has been inmplemented by introducing the variable k, that increases by 1 for each loop. After each loop, the number of iterations now exclude the last item processed in the previous iteration.

Bubble sort with slightly better performance in C# code

    private int[] BubbleSort(int[] array)
    {
        for (int i = 0; i < array.Length - 1; i++)
        {
            bool swapped = false;
            int k = 0;

            for (int j = 0; j < array.Length - 1 - k; j++)
            {
                if (array[j] > array[j + 1])
                {
                    SwapValues(array, j);
                    swapped = true;
                }
            }

            k++;

            if (!swapped)
            {
                break;
            }
        }

        return array;
    }

Quicksort in C#

Quicksort - overview

The quicksort algorithm is a very elegant and fast sorting algorithm. It was named "quicksort" by its originator Tony Hoare, who developed it in 1960.

Quicksort is a good example of the general problem solving heuristic divide and conquer. The basic idea of such an algorithm is to split data into two or more sub-problems and then solving the parts individually and in the end combine the part solutions to get the full solution.

The algorithm can be used to sort an array of for example integers or strings.

Description of the quicksort algorithm

The first step in the algorithm is to choose a pivot element. A simple choice could be to pick the leftmost element of the partition, or as in the C# example below to use the partitions middle index.

In the next step it places elements that are larger than the pivot on the right side of the pivot. In the same manner it then places elements that are less than or equal to the pivot on the left side.

At this stage the array is split up into two partitions and the array is sorted to some extent. All values in the right partition are larger than the all values in the left partition.

Now the algorithm can continue to apply quicksort recursively on each of the two partitions. For each partition the algorithm will pick a new pivot and then separate the values in two new smaller partitions. 

The recursion will go on until the base case is reached. The base case occurs when the arrays have been reduced to a size of 1 or zero, since that small arrays never need to be sorted.

Example of an implementation of quicksort in C#

    private void SortArrayWithQuickSort()
    {
        IComparable[] arrayToSort = new String[] { "d", "c", "r", "q", "b" };
        int minIndex = 0;
        int maxIndex = arrayToSort.Length - 1;
        Quicksort(arrayToSort, minIndex, maxIndex);

        // PrintResult(arrayToSort);
    }

    public void Quicksort(IComparable[] elements, int left, int right)
    {
        int i = left;
        int j = right;
        IComparable pivotValue = GetMiddleValue(elements, left, right);

        while (i <= j)
        {
            while (ArrayValueIsLessThanPivot(elements, i, pivotValue))
            {
                i++;
            }

            while (ArrayValueIsGreaterThanPivot(elements, j, pivotValue))
            {
                j--;
            }

            if (i <= j)
            {
                SwapValues(elements, i, j);
                i++;
                j--;
            }
        }

        if (left < j)
        {
            Quicksort(elements, left, j);
        }

        if (i < right)
        {
            Quicksort(elements, i, right);
        }
    }

    private static void SwapValues(IComparable[] elements, int i, int j)
    {
        IComparable tmp = elements[i];
        elements[i] = elements[j];
        elements[j] = tmp;
    }

    private static bool ArrayValueIsGreaterThanPivot(IComparable[] elements, 
        int j, 
        IComparable pivotValue)
    {
        return elements[j].CompareTo(pivotValue) > 0;
    }

    private static bool ArrayValueIsLessThanPivot(IComparable[] elements, 
        int i, 
        IComparable pivotValue)
    {
        return elements[i].CompareTo(pivotValue) < 0;
    }

    private static IComparable GetMiddleValue(IComparable[] elements, 
        int left, 
        int right)
    {
        int middleIndex = left + (right - left) / 2;
        return elements[middleIndex];
    }

Computational complexity

The asymptotic execution time for the quicksort algorithm is for average and best case O(n log n).
For worst case it is O(n²).