Monthly Archives: Temmuz 2014

03 Tem

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 Tem

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 Tem

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:

03 Tem

C# Selection Sort Algorithm Implementation

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It selects the smallest unsorted item remaining in the list. Then swapping it with the item in the next position to be filled.

For more information about Selection Sort Algorithm:
http://en.wikipedia.org/wiki/Selection_sort

Implementation and Usage:

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

            Sort(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 Sort(int[] arr)
        {
            int i, j, min;
            for (i = 0; i < arr.Length; i++)
            {
                min = i;
                for (j = 0; j < arr.Length; j++)
                {
                    if (arr[j] > arr[min])
                    {
                        min = j;
                        Swap(ref arr[i], ref arr[min]);
                    }
                }
            }
        }

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

See Also:

03 Tem

C# Towers Of Hanoi Problem Implementation

This example contains a recursive solution for the Towers of Hanoi problem.

For more information about Hanoi Tower:
http://en.wikipedia.org/wiki/Tower_of_Hanoi

Usage:

            MoveDisc(3, 1, 3, 2);

            //Output:
            //Index of 20 value in list is 4
            //Move disk 1 from tower 1 to tower 3
            //Move disk 2 from tower 1 to tower 2
            //Move disk 1 from tower 3 to tower 2
            //Move disk 3 from tower 1 to tower 3
            //Move disk 1 from tower 2 to tower 1
            //Move disk 2 from tower 2 to tower 3
            //Move disk 1 from tower 1 to tower 3

        public void MoveDisc(int n, int from, int to, int other)
        {
            if (n > 0)
            {
                MoveDisc(n - 1, from, other, to);
                Console.WriteLine("Move disk {0} from tower {1} to tower {2}", n, from, to);
                MoveDisc(n - 1, other, to, from);
            }
        }