Упражнения по алгоритму поиска и сортировки C # Sharp: Radix sort

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

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

Radix sort - это не сравнительный алгоритм целочисленной сортировки, который сортирует данные по целочисленным ключам путем группировки ключей по отдельным цифрам, которые имеют одинаковые значимые позиции и значения.

Пример :

Оригинал, несортированный список: 272, 45, 75, 81, 501, 2, 24, 66

Сортировка по младшей цифре (1-е место) дает:

27 2 , 8 1, 50 1 , 2 , 2 4, 4 5, 7 5, 6 6

Здесь мы держим 501 перед 2, потому что 501 произошло до 2 в исходном списке, и аналогично для пар 272 и 81 и 45 и 75.

Сортировка по следующей цифре (10-е место) дает:

501, 2, 2 4, 4 5, 6 6, 272, 7 5, 9

Обратите внимание, что 501 снова идет перед 2, так как 501 идет перед 2 в предыдущем списке.

Сортировка по наиболее значимой цифре (место 100) дает:

2, 24, 45, 66, 75, 81, 2 72, 5 01

Важно понимать, что для каждого из вышеперечисленных этапов требуется всего один проход данных, поскольку каждый элемент может быть помещен в свое правильное ведро без необходимости сравнения с другими элементами.

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

272, 045, 075, 081, 002, 024, 501, 066

Первый проход отсчета начинается с наименее значащей цифры каждого ключа, создавая массив размеров сегмента:

• 2 (размер ведра для цифр 0: 272, 081)
• 2 (размер ведра для цифр 2: 002, 501)
• 1 (размер ведра для цифр 4: 024)
• 2 (размер ведра для цифр 5: 045, 075)
• 1 (размер ведра для цифр 6: 066)

Второй проход подсчета следующей более значимой цифры каждого ключа даст массив размеров сегментов:

• 2 (размер корзины для цифр 0: 002, 501)
• 1 (размер ведра для цифр 2: 024)
• 1 (размер ведра для цифр 4: 045)
• 1 (размер ведра для цифр 6: 066)
• 2 (размер ведра для цифр 7: 272, 075)
• 1 (размер ведра для цифр 9: 081

Третий и последний проход подсчета самой значимой цифры каждого ключа даст массив размеров сегментов:

• 6 (размер блока для цифр 0: 002, 024, 045, 066, 075, 081)
• 1 (размер ведра для цифр 1: 272)
• 1 (размер ведра для цифр 8: 501)

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

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

using System;
 namespace Radix_Sort
{
    class Program
    {
        static void Sort(int[] arr)
        {
            int i, j;
            int[] tmp = new int[arr.Length];
            for (int shift = 31; shift > -1; --shift)
            {
                j = 0;
                for (i = 0; i < arr.Length; ++i)
                {
                    bool move = (arr[i] << shift) >= 0;
                    if (shift == 0 ? !move : move)   
                        arr[i-j] = arr[i];
                    else                             
                        tmp[j++] = arr[i];
                }
                Array.Copy(tmp, 0, arr, arr.Length-j, j);
            }
        }
        static void Main(string[] args)
        {
            
			int[] arr = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6  };
			Console.WriteLine("\nOriginal array : ");
			foreach (var item in arr)
            {
                Console.Write(" " + item);    
            }
            Sort(arr);
			Console.WriteLine("\nSorted array : ");
			foreach (var item in arr)
            {
                Console.Write(" " + item);    
            }
           Console.WriteLine("\n");
        }
    }
}

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

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

Блок - схема:

Редактор кода C # Sharp:

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

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