{"id":34000,"date":"2024-11-01T09:22:54","date_gmt":"2024-11-01T09:22:54","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34000"},"modified":"2024-11-01T10:54:22","modified_gmt":"2024-11-01T10:54:22","slug":"c-coding-test-course-radix-sort","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34000\/","title":{"rendered":"C# Coding Test Course, Radix Sort"},"content":{"rendered":"

<\/p>\n

Hello! Today we will explore the concept of Radix Sort and how to implement it using C#. Radix Sort is one of the efficient ways to sort unsorted data, particularly useful when the range of integers is limited.<\/p>\n

1. What is Radix Sort?<\/h2>\n

Radix Sort is a method of sorting numbers based on the position of their digits, typically divided into LSD (Least Significant Digit) and MSD (Most Significant Digit) methods. Using L starts the sorting from the lowest digit, while starting with M sorts from the highest digit.<\/p>\n

2. How Radix Sort Works<\/h2>\n

The mechanism of Radix Sort works as follows:<\/p>\n

    \n
  1. Starting from the least significant digit, sort the data based on each digit.<\/li>\n
  2. Repeat the sorting process up to the most significant digit.<\/li>\n
  3. In this process, a stable sorting algorithm, such as Counting Sort, is used to sort based on each digit.<\/li>\n<\/ol>\n

    3. Time Complexity of Radix Sort<\/h2>\n

    The time complexity of Radix Sort is O(d * (n + k))<\/code>, where d<\/code> is the number of digits in the numbers, n<\/code> is the number of integers to sort, and k<\/code> is the range of digits from 0 to the maximum digit. One of the biggest advantages is that Radix Sort is stable.<\/p>\n

    4. Example Problem Solving with Radix Sort<\/h2>\n

    Now, let’s solve a problem by sorting a specific list of numbers using Radix Sort.<\/p>\n

    Problem Description<\/h3>\n

    Sort the given list of integers in ascending order using Radix Sort.
    \nInput: [170, 45, 75, 90, 802, 24, 2, 66]
    \nOutput: [2, 24, 45, 66, 75, 90, 170, 802]<\/p>\n

    Problem Solving Process<\/h3>\n
      \n
    1. Start from the least significant digit. Sort using the first digit in the units place.<\/li>\n<\/ol>\n
      C#\npublic static void LSDRadixSort(int[] array)\n{\n    \/\/ Find the largest number.\n    int max = array.Max();\n    \/\/ Find the number of digits.\n    for (int exp = 1; max \/ exp > 0; exp *= 10)\n    {\n        CountingSort(array, exp);\n    }\n}\n\nprivate static void CountingSort(int[] array, int exp)\n{\n    int n = array.Length;\n    int[] output = new int[n]; \/\/ Sorted array\n    int[] count = new int[10]; \/\/ Count for digits 0-9\n\n    \/\/ Count the number of elements corresponding to the digit.\n    for (int i = 0; i < n; i++)\n    {\n        count[(array[i] \/ exp) % 10]++;\n    }\n\n    \/\/ Calculate cumulative count.\n    for (int i = 1; i < 10; i++)\n    {\n        count[i] += count[i - 1];\n    }\n\n    \/\/ Create the sorted array.\n    for (int i = n - 1; i >= 0; i--)\n    {\n        output[count[(array[i] \/ exp) % 10] - 1] = array[i];\n        count[(array[i] \/ exp) % 10]--;\n    }\n\n    \/\/ Update the original array.\n    for (int i = 0; i < n; i++)\n    {\n        array[i] = output[i];\n    }\n}\n<\/code><\/pre>\n
      In the above code, we define the LSDRadixSort<\/code> method. This method sorts using CountingSort<\/code> for each digit.<\/p>\n
      5. Implementation and Execution<\/h2>\n
      Now, we will run the entire program using the above functions. Below is the complete code for the program:<\/p>\n
      C#\nusing System;\nusing System.Linq;\n\nclass Program\n{\n    public static void Main(string[] args)\n    {\n        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};\n        LSDRadixSort(array);\n\n        Console.WriteLine(\"Sorted array:\");\n        Console.WriteLine(string.Join(\", \", array));\n    }\n  \n    public static void LSDRadixSort(int[] array)\n    {\n        int max = array.Max();\n        for (int exp = 1; max \/ exp > 0; exp *= 10)\n        {\n            CountingSort(array, exp);\n        }\n    }\n\n    private static void CountingSort(int[] array, int exp)\n    {\n        int n = array.Length;\n        int[] output = new int[n];\n        int[] count = new int[10];\n\n        for (int i = 0; i < n; i++)\n        {\n            count[(array[i] \/ exp) % 10]++;\n        }\n\n        for (int i = 1; i < 10; i++)\n        {\n            count[i] += count[i - 1];\n        }\n\n        for (int i = n - 1; i >= 0; i--)\n        {\n            output[count[(array[i] \/ exp) % 10] - 1] = array[i];\n            count[(array[i] \/ exp) % 10]--;\n        }\n\n        for (int i = 0; i < n; i++)\n        {\n            array[i] = output[i];\n        }\n    }\n}\n<\/code><\/pre>\n
      When executing the above code, the following results can be obtained:<\/p>\n
      \nSorted array:\n2, 24, 45, 66, 75, 90, 170, 802\n<\/code><\/pre>\n
      6. Advantages and Disadvantages of Radix Sort<\/h2>\n
      The advantages of Radix Sort are as follows:<\/p>\n