Archive for the ‘ Sorting ’ Category

Write a Program For BingoSort

Code

        public static void BingoSort(int[] inputArray)
        {
            int max = inputArray.Length - 1;
            int nextValue = max;

            for (int i = max; i >= 0; i--)
            {
                if (inputArray[i] > nextValue) { nextValue = inputArray[i]; }

            }
            while ((max > 0) && (inputArray[max] == nextValue))
            {
                max = max - 1;
            }

        }

Write a Program for Bubble Sort

Bubble sort, sometimes incorrectly referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists.

Source : http://en.wikipedia.org/wiki/Bubble_sort

Code

 

        public static int[] BubbleSort(int[] input)
        {
            StreamWriter sw = new StreamWriter(@"Sorting.txt", true);

            sw.WriteLine("\n\t\t Bubble Sorting \n");

            sw.WriteLine(System.DateTime.Now + "\t input Array \t Total Element \t" + 
input.Length); sw.WriteLine(string.Join(",", input)); int i, j; i = j = 0; int temp = 0; for (i = 0; i < input.Length; i++) { for (j = i + 1; j < input.Length; j++) { if (input[i] < input[j]) { temp = input[i]; input[i] = input[j]; input[j] = temp; } } } sw.WriteLine(System.DateTime.Now + "\t Sorted Array \n" +
string.Join(",", input)); sw.Close(); return input; }

Test Case

        private static void BubbleSortTest()
        {
            List<int> input = new List<int>();
            Random rnd = new Random(1); int maxnumber = 1200;
            input.Clear(); for (int i = 1; i <= maxnumber; i++)
            {
                input.Add(rnd.Next(1, maxnumber));
            }
            Sorting.BubbleSort(input.ToArray()); input.Clear();
            maxnumber = 100000; for (int i = 1; i <= maxnumber; i++)
            {
                input.Add(rnd.Next(1, maxnumber));
            }
            Sorting.BubbleSort(input.ToArray());
            input.Clear(); maxnumber = 10000;
            for (int i = 1; i <= maxnumber; i++)
            {
                input.Add(rnd.Next(1, maxnumber));
            }
            Sorting.BubbleSort(input.ToArray());
        }

Write a Program for Selection Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right

Source : http://en.wikipedia.org/wiki/Selection_sort

Code

        public static int[] SelectionSort(int[] input)
        {
            StreamWriter sw = new StreamWriter(@"Sorting.txt", true);
            sw.WriteLine("\n\t\t Selecton Sorting \n");
            sw.WriteLine(System.DateTime.Now + "\t input Array \t Total Element \t" 
+ input.Length); sw.WriteLine(string.Join(",", input)); int i, j; i = j = 0; int temp = 0; int iMin = 0; for (i = 0; i < input.Length; i++) { for (j = i + 1; j < input.Length; j++) { if (input[j] < input[iMin]) { iMin = j; } } if (iMin != i && iMin < input.Length) { temp = input[iMin]; input[iMin] = input[i]; input[i] = temp; } } sw.WriteLine(System.DateTime.Now + "\t Sorted Array \n"
+ string.Join(",", input)); sw.Close(); return input; }
Test Case
 
        private static void SelectionSortTest() {
            List<int> input = new List<int>();
            Random rnd = new Random(1);
            int maxnumber = 1200;
            
            input.Clear();
            for (int i = 1; i <= maxnumber; i++)
            {
                input.Add(rnd.Next(1, maxnumber));
            }
            Sorting.SelectionSort(input.ToArray());
            
            input.Clear();
            maxnumber = 100000;
            for (int i = 1; i <= maxnumber; i++)
            {
                input.Add(rnd.Next(1, maxnumber));
            }
            Sorting.SelectionSort(input.ToArray());            

            input.Clear();
            maxnumber = 10000;
            for (int i = 1; i <= maxnumber; i++)
            {
                input.Add(rnd.Next(1, maxnumber));
            }
            Sorting.SelectionSort(input.ToArray());
            
        
        }

Counting Sort

Definition from Wikipedia

In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the maximum key value, so it is only suitable for use directly in situations where the keys are not significantly larger than the number of items. However, it is often used as a subroutine in another sorting algorithm, radix sort, that can handle larger keys more efficiently.

Here is the C# implementation of Counting Sort

 class Program
  {
    static void Main(string[] args)
    {
      //create an input array with maximum value of an element is 1024
      int[] input = new int[10000];
      Random random = new Random();
      for (int i = 0; i < 10000; i++)
      {
        input[i] = random.Next(0, 1024);

      }
      Sorting.CountingSort(input);
    }

   
  }

 public class Sorting
  {
    public static void CountingSort(int[] arrayA)
    {
      Console.WriteLine("Original Array");
      for (int i = 0; i < arrayA.Length; i++)
      {

        Console.Write(arrayA[i] + " , ");
      }
      Console.WriteLine("");
      int k = 1024;
      int[] arrayB = new int[arrayA.Length];
      int[] arrayC = new int[k];
      for (int i = 0; i < arrayC.Length; i++)
      {

        arrayC[i] = 0;
      }
      for (int j = 0; j < arrayA.Length; j++)
      {
        arrayC[arrayA[j]] = arrayC[arrayA[j]] + 1;
      }

      //Place the number of elements less than each value at i into array C.    
      for (int i = 1; i < k; i++)
        arrayC[i] = arrayC[i] + arrayC[i - 1];

      //Place each element of arrayA into its correct sorted position in the
      //output array B.
      for (int j = arrayA.Length - 1; j >= 0; j--)
      {
        arrayB[arrayC[arrayA[j]] - 1] = arrayA[j];
        arrayC[arrayA[j]] = arrayC[arrayA[j]] - 1;
      }

      //Overwrite the original arrayA with the output arrayB.
      Console.WriteLine("Sorted Array");
      for (int i = 0; i < arrayA.Length; i++)
      {
        arrayA[i] = arrayB[i];
        Console.Write(arrayA[i] + " , ");
      }

      Console.WriteLine("");

    }
  }
 
in this program I am showing output on console, it can be easily saved on file also.