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

In this article, we will discuss the concept and implementation of Radix Sort, as well as detail the process through practical problems.<\/p>\n<\/header>\n

\n

1. Overview of Radix Sort<\/h2>\n

Radix Sort is a special type of sorting algorithm that is effective when the data to be sorted consists of integers or strings within a specific range. Unlike typical sorting algorithms, Radix Sort sorts based on “digits.” Through this, Radix Sort has a time complexity of O(d(n + k)), where d is the number of digits, n is the number of data to be sorted, and k is the range of values.<\/p>\n<\/section>\n

\n

2. Principle of Radix Sort<\/h2>\n

Radix Sort is performed through the following process:<\/p>\n

    \n
  1. Starting from the least significant digit, numbers are sorted based on each digit.<\/li>\n
  2. Sorting is repeated for each digit.<\/li>\n
  3. Once sorting is completed for all digits, a fully sorted array is obtained.<\/li>\n<\/ol>\n

    Radix Sort is typically implemented as a stable sorting algorithm, meaning that the order of elements with the same value retains their relative positions.<\/p>\n<\/section>\n

    \n

    3. Implementation of Radix Sort<\/h2>\n

    Let’s implement Radix Sort in C++. Here is the basic implementation of Radix Sort:<\/p>\n

    \n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\n\/\/ Function for sorting based on a specific digit\nvoid countingSort(vector<int> &arr, int exp) {\n    int n = arr.size();\n    vector<int> output(n);\n    int count[10] = {0}; \/\/ Range of numbers is 0~9\n\n    \/\/ Count occurrences of each digit\n    for (int i = 0; i < n; i++) {\n        count[(arr[i] \/ exp) % 10]++;\n    }\n\n    \/\/ Calculate cumulative sum\n    for (int i = 1; i < 10; i++) {\n        count[i] += count[i - 1];\n    }\n\n    \/\/ Build the output array\n    for (int i = n - 1; i >= 0; i--) {\n        output[count[(arr[i] \/ exp) % 10] - 1] = arr[i];\n        count[(arr[i] \/ exp) % 10]--;\n    }\n\n    \/\/ Store the result in the original array\n    for (int i = 0; i < n; i++) {\n        arr[i] = output[i];\n    }\n}\n\n\/\/ Radix Sort function\nvoid radixSort(vector<int> &arr) {\n    \/\/ Find the maximum value\n    int maxVal = *max_element(arr.begin(), arr.end());\n\n    \/\/ Sort by each digit\n    for (int exp = 1; maxVal \/ exp > 0; exp *= 10) {\n        countingSort(arr, exp);\n    }\n}\n\n\/\/ Main function\nint main() {\n    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};\n    radixSort(arr);\n    \n    cout << \"Sorted array: \";\n    for (int i : arr) {\n        cout << i << \" \";\n    }\n    \n    return 0;\n}\n        <\/code><\/pre>\n
    This code demonstrates the basic flow of Radix Sort. The countingSort<\/strong> function counts the occurrences for each digit and sorts the elements based on that. The radixSort<\/strong> function calls countingSort<\/strong> for each digit and returns the final sorted array.<\/p>\n<\/section>\n
    \n
    4. Example Problem Solved with Radix Sort<\/h2>\n
    Now, let\u2019s present an algorithm problem that can be solved using Radix Sort.<\/p>\n
    Problem: Sort the given list of integers using Radix Sort.<\/h3>\n
    Input: [170, 45, 75, 90, 802, 24, 2, 66]<\/p>\n
    Output: [2, 24, 45, 66, 75, 90, 170, 802]<\/p>\n
    Problem-solving process<\/h4>\n
      \n
    1. Find the maximum value, which is confirmed to be 802. This value determines the highest digit.<\/li>\n
    2. Start with the least significant digit and call countingSort for each digit in the order of 1’s place, 10’s place, and 100’s place.<\/li>\n
    3. After sorting each digit, the final array will be sorted.<\/li>\n<\/ol>\n
      Try solving the problem using Radix Sort!<\/p>\n<\/section>\n