03 Jul

C# Merge Sort Algorithm Implementation

Merge sort is a comparison-based sorting algorithm. It is based on divide-and-conquer paradigm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

For more information about Merge Sort Algorithm:
http://en.wikipedia.org/wiki/Merge_sort

Implementation and Usage:

            int[] arr = new int[10]
            {
                1, 5, 4, 11, 20, 8, 2, 98, 90, 16
            };

            MergeSort(arr, 0, arr.Length - 1);
            Console.WriteLine("Sorted Values:");
            for (int i = 0; i < arr.Length; i++)
                Console.WriteLine(arr[i]);

            //Output:
            //Sorted Values:
            //1
            //2
            //4
            //5
            //8
            //11
            //16
            //20
            //90
            //98
        private void Merge(int[] input, int left, int middle, int right)
        {
            int[] leftArray = new int[middle - left + 1];
            int[] rightArray = new int[right - middle];

            Array.Copy(input, left, leftArray, 0, middle - left + 1);
            Array.Copy(input, middle + 1, rightArray, 0, right - middle);

            int i = 0;
            int j = 0;
            for (int k = left; k < right + 1; k++)
            {
                if (i == leftArray.Length)
                {
                    input[k] = rightArray[j];
                    j++;
                }
                else if (j == rightArray.Length)
                {
                    input[k] = leftArray[i];
                    i++;
                }
                else if (leftArray[i] <= rightArray[j])
                {
                    input[k] = leftArray[i];
                    i++;
                }
                else
                {
                    input[k] = rightArray[j];
                    j++;
                }
            }
        }

        private void MergeSort(int[] input, int left, int right)
        {
            if (left < right)
            {
                int middle = (left + right) / 2;

                MergeSort(input, left, middle);
                MergeSort(input, middle + 1, right);

                Merge(input, left, middle, right);
            }
        }    

See Also:

03 Jul

C# Quick Sort Algorithm Implementation

Quicksort algorithm is a sorting algorithm developed by Tony Hoare that, on average, makes O(n log n) comparisons to sort n items.

For more information about Quick Sort Algorithm:
http://en.wikipedia.org/wiki/Quicksort

Implementation and Usage:

            int[] arr = new int[10]
            {
                1, 5, 4, 11, 20, 8, 2, 98, 90, 16
            };

            QuickSort(arr, 0, arr.Length - 1);
            Console.WriteLine("Sorted Values:");
            for (int i = 0; i < arr.Length; i++)
                Console.WriteLine(arr[i]);

            //Output:
            //Sorted Values:
            //1
            //2
            //4
            //5
            //8
            //11
            //16
            //20
            //90
            //98
        private void QuickSort(int[] arr, int start, int end)
        {
            int i;
            if (start < end)
            {
                i = Partition(arr, start, end);

                QuickSort(arr, start, i - 1);
                QuickSort(arr, i + 1, end);
            }
        }

        private int Partition(int[] arr, int start, int end)
        {
            int temp;
            int p = arr[end];
            int i = start - 1;

            for (int j = start; j <= end - 1; j++)
            {
                if (arr[j] <= p)
                {
                    i++;
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }

            temp = arr[i + 1];
            arr[i + 1] = arr[end];
            arr[end] = temp;
            return i + 1;
        }

See Also:

03 Jul

C# Counting Sort Algorithm Implementation

Counting sort is an sorting algorithm for sorting a collection of objects according to keys that are small integers;

For more information about Counting Sort Algorithm:
http://en.wikipedia.org/wiki/Counting_sort

Implementation and Usage:

            int[] arr = new int[10]
            {
                1, 5, 4, 11, 20, 8, 2, 98, 90, 16
            };

            int[] sortedArray = CountingSort(arr);
            Console.WriteLine("Sorted Values:");
            for (int i = 0; i < sortedArray.Length; i++)
                Console.WriteLine(sortedArray[i]);

            //Output:
            //Sorted Values:
            //1
            //2
            //4
            //5
            //8
            //11
            //16
            //20
            //90
            //98
        public int[] CountingSort(int[] array)
        {
            int[] sortedArray = new int[array.Length];

            // find smallest and largest value
            int minVal = array[0];
            int maxVal = array[0];
            for (int i = 1; i < array.Length; i++)
            {
                if (array[i] < minVal) minVal = array[i];
                else if (array[i] > maxVal) maxVal = array[i];
            }

            // init array of frequencies
            int[] counts = new int[maxVal - minVal + 1];

            // init the frequencies
            for (int i = 0; i < array.Length; i++)
            {
                counts[array[i] - minVal]++;
            }

            // recalculate
            counts[0]--;
            for (int i = 1; i < counts.Length; i++)
            {
                counts[i] = counts[i] + counts[i - 1];
            }

            // Sort the array
            for (int i = array.Length - 1; i >= 0; i--)
            {
                sortedArray[counts[array[i] - minVal]--] = array[i];
            }

            return sortedArray;
        }

See Also:

03 Jul

C# Bubble Sort Algorithm Implementation

The simplest sorting algorithm is bubble sort. It works by repeatedly stepping through the list to be sorted. It walks from the first element to the last and compares each pair of elements and switches their positions if necessary.

For more information about Bubble Sort Algorithm:
http://en.wikipedia.org/wiki/Bubble_sort

Implementation and Usage:

            int[] arr = new int[10]
            {
                1, 5, 4, 11, 20, 8, 2, 98, 90, 16
            };

            BubbleSort(arr);
            Console.WriteLine("Sorted Values:");
            for (int i = 0; i < arr.Length; i++)
                Console.WriteLine(arr[i]);

            //Output:
            //Sorted Values:
            //1
            //2
            //4
            //5
            //8
            //11
            //16
            //20
            //90
            //98
        private void BubbleSort(int[] arr)
        {
            for (int i = 0; i < arr.Length - 1; i++)
            {
                for (int j = arr.Length - 1; j > i; j--)
                {
                    if (arr[j] < arr[j - 1])
                    {
                        Swap(ref arr[j], ref arr[j - 1]);
                    }
                }
            }
        }

        private void Swap(ref int x, ref int y)
        {
            int temp = x;
            x = y;
            y = temp;
        }

See Also:

03 Jul

C# Insertion Sort Algorithm Implementation

Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

For more information about Insertion Sort Algorithm:
http://en.wikipedia.org/wiki/Insertion_sort

Implementation and Usage:

            int[] arr = new int[10]
            {
                1, 5, 4, 11, 20, 8, 2, 98, 90, 16
            };

            InsertionSort(arr);
            Console.WriteLine("Sorted Values:");
            for (int i = 0; i < arr.Length; i++)
                Console.WriteLine(arr[i]);

            //Output:
            //Sorted Values:
            //1
            //2
            //4
            //5
            //8
            //11
            //16
            //20
            //90
            //98
        private void InsertionSort(int[] arr)
        {
            int j, temp;
            for (int i = 1; i <= arr.Length - 1; i++)
            {
                temp = arr[i];
                j = i - 1;
                while (j >= 0 && arr[j] > temp)
                {
                    arr[j + 1] = arr[j];
                    j--;
                }
                arr[j + 1] = temp;
            }
        }

See Also: