Skip to content
TheChatArchiveThe Chat Archive
Qwenqwen3-30b-a3b· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

давай также для radix sort

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Geminigemini-2.5-flash’s answer.
  1. User

    давай также для radix sort

  2. Qwen Assistant

    Radix Sort: Реализация на Python и C++

    Radix Sort — это несравнительный алгоритм сортировки, который сортирует числа по разрядам, начиная с младшего. Он использует стабильную сортировку (например, подсчет) для каждого разряда, что позволяет ему работать за линейное время.


    ✅ Реализация Radix Sort на Python

    def radix_sort(arr):
        if not arr:
            return arr
    
        # Найти максимальное число для определения количества разрядов
        max_num = max(arr)
        exp = 1  # Степень 10 (1, 10, 100, ...)
    
        while max_num // exp > 0:
            # Использовать стабильную сортировку (подсчет) для текущего разряда
            count = [0] * 10
            output = [0] * len(arr)
    
            # Подсчёт количества элементов
            for num in arr:
                digit = (num // exp) % 10
                count[digit] += 1
    
            # Накопление количества
            for i in range(1, 10):
                count[i] += count[i - 1]
    
            # Построение выходного массива
            for i in reversed(range(len(arr))):
                digit = (arr[i] // exp) % 10
                output[count[digit] - 1] = arr[i]
                count[digit] -= 1
    
            # Обновить массив
            arr = output
    
            # Перейти к следующему разряду
            exp *= 10
    
        return arr
    
    # Пример использования
    arr = [170, 45, 75, 90, 802, 24, 2, 66]
    sorted_arr = radix_sort(arr)
    print("Отсортированный массив:", sorted_arr)
    

    ✅ Реализация Radix Sort на C++

    #include <iostream>
    #include <vector>
    #include <cmath>
    
    using namespace std;
    
    vector<int> radix_sort(vector<int> arr) {
        if (arr.empty()) {
            return arr;
        }
    
        int max_num = *max_element(arr.begin(), arr.end());
        int exp = 1;  // Степень 10 (1, 10, 100, ...)
    
        while (max_num / exp > 0) {
            vector<int> count(10, 0);
            vector<int> output(arr.size(), 0);
    
            // Подсчёт количества элементов
            for (int num : arr) {
                int digit = (num / exp) % 10;
                count[digit]++;
            }
    
            // Накопление количества
            for (int i = 1; i < 10; ++i) {
                count[i] += count[i - 1];
            }
    
            // Построение выходного массива
            for (int i = arr.size() - 1; i >= 0; --i) {
                int digit = (arr[i] / exp) % 10;
                output[count[digit] - 1] = arr[i];
                count[digit]--;
            }
    
            // Обновить массив
            arr = output;
    
            // Перейти к следующему разряду
            exp *= 10;
        }
    
        return arr;
    }
    
    // Пример использования
    int main() {
        vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
        vector<int> sorted_arr = radix_sort(arr);
    
        cout << "Отсортированный массив: ";
        for (int num : sorted_arr) {
            cout << num << " ";
        }
        cout << endl;
    
        return 0;
    }
    

    📌 Пояснения:

    • Этап 1: Нахождение максимального числа
      Чтобы определить, сколько разрядов нужно обработать, мы находим максимальное число в массиве.

    • Этап 2: Сортировка по разрядам
      Для каждого разряда (единицы, десятки, сотни и т.д.) мы используем стабильную сортировку (подсчет), чтобы распределить числа по цифрам.

    • Этап 3: Повторение для всех разрядов
      После сортировки по текущему разряду, мы переходим к следующему разряду (умножая exp на 10).

    • Сложность:

      • Время: O(n * k), где n — количество элементов, k — количество разрядов.
      • Память: O(n + b), где b — размер алфавита (в данном случае 10 для десятичных цифр).

    🧪 Пример работы:

    Вход: [170, 45, 75, 90, 802, 24, 2, 66]
    Выход: [2, 24, 45, 66, 75, 90, 170, 802]


    ⚠️ Примечание:

    Radix Sort работает эффективно только с неотрицательными целыми числами. Для отрицательных чисел требуется дополнительная обработка (например, разделение на положительные и отрицательные).

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.