Алгоритм поиска и сортировки C # Sharp: подсчет

Алгоритм поиска и сортировки C # Sharp: упражнение-4 с решением

Напишите программу на C # Sharp для сортировки списка элементов, используя сортировку Counting

Согласно Википедии "В компьютерных науках сортировка подсчета - это алгоритм сортировки коллекции объектов по ключам, которые являются маленькими целыми числами; то есть это алгоритм целочисленной сортировки. Он работает путем подсчета количества объектов, у которых есть каждый отдельный ключ значение и использование арифметики по этим подсчетам для определения позиций каждого значения ключа в выходной последовательности. Время его выполнения линейно по количеству элементов и разности между максимальным и минимальным значениями ключа, поэтому оно подходит только для непосредственного использования в ситуациях, когда изменение в ключах не намного больше, чем количество элементов. Однако оно часто используется в качестве подпрограммы в другом алгоритме сортировки, основанном на сортировке, который может обрабатывать большие ключи более эффективно ».

Алгоритм зацикливается на элементах, вычисляя гистограмму того, сколько раз каждый ключ встречается в коллекции входных данных. Затем он выполняет вычисление суммы префикса (второй цикл по диапазону возможных ключей), чтобы определить для каждого ключа начальную позицию в выходном массиве элементов, имеющих этот ключ. Наконец, он снова зацикливается на элементах, перемещая каждый элемент в его отсортированную позицию в выходном массиве.

Пример решения : -

C # острый код:

using System;
using System.Linq;
public class Counting_sort  
{  
 public static void Main()  
    {  
int[] array = new int[10]
{
    2, 5, -4, 11, 0, 8, 22, 67, 51, 6
};
 
    Console.WriteLine("\n"+"Original array :");
           foreach (int aa in array)                       
           Console.Write(aa + " "); 
    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];
    }
 
  Console.WriteLine("\n"+"Sorted array :");
           foreach (int aa in sortedArray)                       
           Console.Write(aa + " "); 
  Console.Write("\n");            
                   
}
}

Пример вывода:

 Исходный массив:                                                                                              
2 5 -4 11 0 8 22 67 51 6                                                                                      
Сортированный массив:                                                                                                
-4 0 2 5 6 8 11 22 51 67

Блок - схема:

C # Sharp Практика онлайн:

Внесите свой код и комментарии через Disqus.

Предыдущий: Напишите программу на C # Sharp для сортировки списка элементов с использованием Bubble sort.
Далее: Напишите программу на C # Sharp для сортировки списка элементов, используя сортировку Heap.