Рубрики

Radix Sort

Нижняя граница для алгоритма сортировки на основе сравнения (сортировка слиянием, сортировка по кучи, быстрая сортировка и т. Д.) Составляет Ω (nLogn), т. Е. Они не могут работать лучше, чем nLogn.

Счетная сортировка — это алгоритм линейной сортировки по времени, который сортирует по времени O (n + k), когда элементы находятся в диапазоне от 1 до k.

Что если элементы находятся в диапазоне от 1 до n 2 ?
Мы не можем использовать сортировку подсчета, потому что сортировка подсчета займет O (n 2 ), что хуже, чем алгоритмы сортировки, основанные на сравнении. Можем ли мы отсортировать такой массив за линейное время?
Radix Sort является ответом. Идея Radix Sort заключается в том, чтобы делать сортировку цифр за цифрой, начиная с наименее значимой цифры до самой значимой цифры. Radix sort использует подсчет сортировки как подпрограмму для сортировки.

Алгоритм сортировки по радиксу
1) Выполните следующие действия для каждой цифры i, где i изменяется от наименее значимой цифры до самой значимой цифры.
…………. а) Сортировать входной массив, используя сортировку с подсчетом (или любую устойчивую сортировку) по i-й цифре.

Пример:
Оригинальный, несортированный список:

170, 45, 75, 90, 802, 24, 2, 66

Сортировка по наименьшей значащей цифре (1-е место) дает: [* Обратите внимание, что мы сохраняем 802 до 2, потому что 802 имел место до 2 в исходном списке, и аналогично для пар 170 и 90 и 45 и 75.]

17 0 , 9 0 , 80 2 , 2 , 2 4 , 4 5 , 7 5 , 6 6

Сортировка по следующей цифре (10-е место) дает: [* Обратите внимание, что 802 снова предшествует 2, как 802 предшествует 2 в предыдущем списке.]

8 0 2, 2, 2 4, 4 5, 6 6, 1 7 0, 7 5, 9 0

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

2, 24, 45, 66, 75, 90, 1 70, 8 02

Какое время работы Radix Sort?
Пусть во входных целых числах будет d цифр. Radix Sort занимает время O (d * (n + b)), где b является базой для представления чисел, например, для десятичной системы, b равно 10. Каково значение d? Если k — максимально возможное значение, то d будет O (log b (k)). Таким образом, общая сложность времени составляет O ((n + b) * log b (k)). Который выглядит больше, чем временная сложность алгоритмов сортировки на основе сравнения для большого k. Давайте сначала ограничим k. Пусть k <= n c, где c постоянная. В этом случае сложность становится O (nLog b (n)). Но он все еще не превосходит алгоритмы сортировки, основанные на сравнении.
Что если мы увеличим значение b? Каким должно быть значение b, чтобы сложность времени была линейной? Если мы установим b как n, мы получим временную сложность как O (n). Другими словами, мы можем отсортировать массив целых чисел с диапазоном от 1 до n c, если числа представлены в базе n (или каждая цифра занимает log 2 (n) битов).

Является ли Radix Sort предпочтительным алгоритмом сортировки на основе сравнения, например, Quick-Sort?
Если у нас есть log 2 n битов для каждой цифры, время выполнения Radix будет лучше, чем Quick Sort для широкого диапазона входных чисел. Постоянные факторы, скрытые в асимптотической записи, выше для Radix Sort, а Quick-Sort использует аппаратные кеши более эффективно. Кроме того, сортировка Radix использует подсчет сортировки в качестве подпрограммы, а сортировка подсчета занимает дополнительное место для сортировки чисел.

Внедрение Radix Sort
Ниже приводится простая реализация Radix Sort. Для простоты предполагается, что значение d равно 10. Мы рекомендуем вам просмотреть раздел « Сортировка подсчета» для получения подробной информации о функции countSort () в приведенном ниже коде.

C / C ++

// C ++ реализация Radix Sort
#include<iostream>

using namespace std;

  
// Полезная функция для получения максимального значения в arr []

int getMax(int arr[], int n)

{

    int mx = arr[0];

    for (int i = 1; i < n; i++)

        if (arr[i] > mx)

            mx = arr[i];

    return mx;

}

  
// Функция для подсчета сортировки arr [] в соответствии с
// цифра, представленная exp.

void countSort(int arr[], int n, int exp)

{

    int output[n]; // выходной массив

    int i, count[10] = {0};

  

    // Сохраняем количество вхождений в count []

    for (i = 0; i < n; i++)

        count[ (arr[i]/exp)%10 ]++;

  

    // Изменить count [i] так, чтобы count [i] теперь содержал фактический

    // положение этой цифры в выходных данных []

    for (i = 1; i < 10; i++)

        count[i] += count[i - 1];

  

    // Создаем выходной массив

    for (i = n - 1; i >= 0; i--)

    {

        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

        count[ (arr[i]/exp)%10 ]--;

    }

  

    // Копируем выходной массив в arr [], так что теперь arr []

    // содержит отсортированные номера по текущей цифре

    for (i = 0; i < n; i++)

        arr[i] = output[i];

}

  
// Основная функция для сортировки arr [] размера n, используя
// Radix Sort

void radixsort(int arr[], int n)

{

    // Находим максимальное число, чтобы узнать количество цифр

    int m = getMax(arr, n);

  

    // Делаем подсчет для каждой цифры. Обратите внимание, что вместо

    // номер проходной цифры, переданный опыт. опыт 10 ^ я

    // где я текущая цифра

    for (int exp = 1; m/exp > 0; exp *= 10)

        countSort(arr, n, exp);

}

  
// Вспомогательная функция для печати массива

void print(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

    int n = sizeof(arr)/sizeof(arr[0]);

    radixsort(arr, n);

    print(arr, n);

    return 0;

}

Джава

// Radix-сортировка реализации Java

import java.io.*;

import java.util.*;

  

class Radix {

  

    // Полезная функция для получения максимального значения в arr []

    static int getMax(int arr[], int n)

    {

        int mx = arr[0];

        for (int i = 1; i < n; i++)

            if (arr[i] > mx)

                mx = arr[i];

        return mx;

    }

  

    // Функция для подсчета сортировки arr [] в соответствии с

    // цифра, представленная exp.

    static void countSort(int arr[], int n, int exp)

    {

        int output[] = new int[n]; // выходной массив

        int i;

        int count[] = new int[10];

        Arrays.fill(count,0);

  

        // Сохраняем количество вхождений в count []

        for (i = 0; i < n; i++)

            count[ (arr[i]/exp)%10 ]++;

  

        // Изменим count [i] так, чтобы count [i] теперь содержал

        // фактическая позиция этой цифры на выходе []

        for (i = 1; i < 10; i++)

            count[i] += count[i - 1];

  

        // Создаем выходной массив

        for (i = n - 1; i >= 0; i--)

        {

            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

            count[ (arr[i]/exp)%10 ]--;

        }

  

        // Копируем выходной массив в arr [], так что теперь arr []

        // содержит отсортированные номера по текущей цифре

        for (i = 0; i < n; i++)

            arr[i] = output[i];

    }

  

    // Основная функция для сортировки arr [] размера n, используя

    // Radix Sort

    static void radixsort(int arr[], int n)

    {

        // Находим максимальное число, чтобы узнать количество цифр

        int m = getMax(arr, n);

  

        // Делаем подсчет для каждой цифры. Обратите внимание, что вместо

        // номер проходной цифры, переданный опыт. опыт 10 ^ я

        // где я текущая цифра

        for (int exp = 1; m/exp > 0; exp *= 10)

            countSort(arr, n, exp);

    }

  

    // Вспомогательная функция для печати массива

    static void print(int arr[], int n)

    {

        for (int i=0; i<n; i++)

            System.out.print(arr[i]+" ");

    }

  

  

    / * Функция драйвера для проверки вышеуказанной функции * /

    public static void main (String[] args)

    {

        int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

        int n = arr.length;

        radixsort(arr, n);

        print(arr, n);

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

питон

# Python программа для реализации Radix Sort

  
# Функция для подсчета вида arr [] в соответствии с
# цифра, представленная эксп.

def countingSort(arr, exp1):

  

    n = len(arr)

  

    # Элементы массива вывода, которые будут отсортированы об

    output = [0] * (n)

  

    # инициализировать массив count как 0

    count = [0] * (10)

  

    # Хранить количество вхождений в count []

    for i in range(0, n):

        index = (arr[i]/exp1)

        count[ (index)%10 ] += 1

  

    # Измените count [i] так, чтобы count [i] теперь содержал фактический

    # позиция этой цифры в выходном массиве

    for i in range(1,10):

        count[i] += count[i-1]

  

    # Построить выходной массив

    i = n-1

    while i>=0:

        index = (arr[i]/exp1)

        output[ count[ (index)%10 ] - 1] = arr[i]

        count[ (index)%10 ] -= 1

        i -= 1

  

    # Копирование выходного массива в arr [],

    # чтобы arr теперь содержал отсортированные числа

    i = 0

    for i in range(0,len(arr)):

        arr[i] = output[i]

  
# Способ сделать сортировку по Radix

def radixSort(arr):

  

    # Найти максимальное число, чтобы узнать количество цифр

    max1 = max(arr)

  

    # Делать подсчет сортировки для каждой цифры. Обратите внимание, что вместо

    количество проходящих цифр, передается опыт. опыт 10 ^ я

    # где я текущая цифра

    exp = 1

    while max1/exp > 0:

        countingSort(arr,exp)

        exp *= 10

  
# Код драйвера для проверки выше

arr = [ 170, 45, 75, 90, 802, 24, 2, 66]

radixSort(arr)

  

for i in range(len(arr)):

    print(arr[i]),

  
# Этот код предоставлен Мохитом Кумрой

C #

// C # реализация Radix Sort

using System; 

    

class GFG 

    public static int getMax(int[] arr, int n) 

    

        int mx = arr[0]; 

        for (int i = 1; i < n; i++) 

            if (arr[i] > mx) 

                mx = arr[i]; 

        return mx; 

    

        

    // Функция для подсчета сортировки arr [] в соответствии с

    // цифра, представленная exp.

    public static void countSort(int[] arr, int n, int exp) 

    

        int[] output = new int[n]; // выходной массив

        int i;

        int[] count = new int[10];

          

        // инициализация всех элементов count до 0

        for(i = 0; i < 10; i++)

            count[i] = 0;

        

        // Сохраняем количество вхождений в count []

        for (i = 0; i < n; i++) 

            count[ (arr[i]/exp)%10 ]++; 

        

        // Изменить count [i] так, чтобы count [i] теперь содержал фактический

        // положение этой цифры в выходных данных []

        for (i = 1; i < 10; i++) 

            count[i] += count[i - 1]; 

        

        // Создаем выходной массив

        for (i = n - 1; i >= 0; i--) 

        

            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 

            count[ (arr[i]/exp)%10 ]--; 

        

        

        // Копируем выходной массив в arr [], так что теперь arr []

        // содержит отсортированные номера по текущей цифре

        for (i = 0; i < n; i++) 

            arr[i] = output[i]; 

    

        

    // Основная функция для сортировки arr [] размера n, используя

    // Radix Sort

    public static void radixsort(int[] arr, int n) 

    

        // Находим максимальное число, чтобы узнать количество цифр

        int m = getMax(arr, n); 

        

        // Делаем подсчет для каждой цифры. Обратите внимание, что вместо

        // номер проходной цифры, переданный опыт. опыт 10 ^ я

        // где я текущая цифра

        for (int exp = 1; m/exp > 0; exp *= 10) 

            countSort(arr, n, exp); 

    

        

    // Вспомогательная функция для печати массива

    public static void print(int[] arr, int n) 

    

        for (int i = 0; i < n; i++) 

            Console.Write(arr[i] + " "); 

    

        

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main()

    {

        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66}; 

        int n = arr.Length; 

        radixsort(arr, n); 

        print(arr, n); 

    }

      

    // Этот код предоставлен DrRoot_

}

PHP

<?php
// PHP реализация Radix Sort

  

  
// Функция для подсчета сортировки arr []
// в соответствии с цифрой, представленной exp.

function countSort(&$arr, $n, $exp

    $output = array_fill(0, $n, 0); // выходной массив

    $count = array_fill(0, 10, 0); 

  

    // Сохраняем количество вхождений в count []

    for ($i = 0; $i < $n; $i++) 

        $count[ ($arr[$i] / $exp) % 10 ]++; 

  

    // Изменим count [i] так, чтобы count [i]

    // теперь содержит актуальную позицию

    // эта цифра в выходных данных []

    for ($i = 1; $i < 10; $i++) 

        $count[$i] += $count[$i - 1]; 

  

    // Создаем выходной массив

    for ($i = $n - 1; $i >= 0; $i--) 

    

        $output[$count[ ($arr[$i] / 

                         $exp) % 10 ] - 1] = $arr[$i]; 

        $count[ ($arr[$i] / $exp) % 10 ]--; 

    

  

    // Копируем выходной массив в arr [], поэтому

    // этот arr [] теперь содержит отсортированные числа

    // в соответствии с текущей цифрой

    for ($i = 0; $i < $n; $i++) 

        $arr[$i] = $output[$i]; 

  
// Основная функция для сортировки arr []
// размера n с использованием Radix Sort

function radixsort(&$arr, $n

      

    // Находим максимальное число, которое нужно знать

    // количество цифр

    $m = max($arr); 

  

    // Делаем подсчет для каждой цифры. Заметка

    // что вместо передачи цифр,

    // опыт передан. опыт 10 ^ я где я

    // номер текущей цифры

    for ($exp = 1; $m / $exp > 0; $exp *= 10) 

        countSort($arr, $n, $exp); 

  
// Вспомогательная функция для печати массива

function PrintArray(&$arr,$n

    for ($i = 0; $i < $n; $i++) 

        echo $arr[$i] . " "

  
// Код драйвера

$arr = array(170, 45, 75, 90, 802, 24, 2, 66); 

$n = count($arr); 

radixsort($arr, $n); 

PrintArray($arr, $n); 

  
// Этот код предоставлен rathbhupendra
?>


Выход:

2 24 45 66 75 90 170 802




Тест на сортировку по Radix

Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz:

Ссылки:
http://en.wikipedia.org/wiki/Radix_sort
http://alg12.wikischolars.columbia.edu/file/view/RADIX.pdf
MIT Video Lecture
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Radix Sort

0.00 (0%) 0 votes