Sortuj Radix to algorytm sortowania liniowego, który sortuje elementy, przetwarzając je cyfra po cyfrze. Jest to wydajny algorytm sortowania liczb całkowitych lub ciągów znaków z kluczami o stałym rozmiarze.
Zamiast bezpośrednio porównywać elementy, Radix Sort rozdziela elementy na segmenty na podstawie wartości każdej cyfry. Poprzez wielokrotne sortowanie elementów według ich cyfr znaczących, od najmniej znaczących do najbardziej znaczących, Radix Sort osiąga ostateczny porządek sortowania.
Algorytm sortowania radiacyjnego
Kluczową ideą stojącą za Radix Sort jest wykorzystanie koncepcji wartości miejsca. Zakłada, że sortowanie liczb cyfra po cyfrze ostatecznie doprowadzi do w pełni posortowanej listy. Sortowanie radiacyjne można przeprowadzić przy użyciu różnych odmian, takich jak sortowanie radiacyjne według najmniejszej cyfry znaczącej (LSD) lub sortowanie radiacyjne według najbardziej znaczącej cyfry (MSD).
Jak działa algorytm sortowania Radix?
Aby wykonać sortowanie radix tablicy [170, 45, 75, 90, 802, 24, 2, 66], wykonujemy następujące kroki:
Jak działa algorytm sortowania Radix | Krok 1
Krok 1: Znajdź największy element tablicy, czyli 802. Ma trzy cyfry, więc będziemy iterować trzy razy, po jednym dla każdego znaczącego miejsca.
Krok 2: Sortuj elementy na podstawie cyfr miejsca w jednostce (X=0). Do sortowania cyfr w każdym znaczącym miejscu używamy stabilnej techniki sortowania, takiej jak sortowanie przez zliczanie.
konstruktor strunSortowanie ze względu na miejsce jednostki:
- Wykonaj sortowanie zliczające w tablicy w oparciu o cyfry miejsca jednostkowego.
- Tablica posortowana według miejsca jednostkowego to [170, 90, 802, 2, 24, 45, 75, 66].
Jak działa algorytm sortowania Radix | Krok 2
Krok 3: Sortuj elementy na podstawie cyfr miejsca dziesiątek.
Sortowanie według miejsca dziesiątek:
- Wykonaj sortowanie zliczające w tablicy w oparciu o cyfry dziesiątek.
- Posortowana tablica oparta na miejscu dziesiątek to [802, 2, 24, 45, 66, 170, 75, 90].
Jak działa algorytm sortowania Radix | Krok 3
Krok 4: Sortuj elementy w oparciu o cyfry setek miejsc.
Sortowanie według miejsca setek:
- Wykonaj sortowanie zliczające w tablicy w oparciu o cyfry setek.
- Tablica posortowana według miejsca setek to [2, 24, 45, 66, 75, 90, 170, 802].
Jak działa algorytm sortowania Radix | Krok 4
Krok 5: Tablica jest teraz posortowana rosnąco.
tablica w ciąguOstateczna tablica posortowana przy użyciu sortowania radix to [2, 24, 45, 66, 75, 90, 170, 802].
Jak działa algorytm sortowania Radix | Krok 5
Poniżej implementacja powyższych ilustracji:
C++ // C++ implementation of Radix Sort #include using namespace std; // A utility function to get maximum // value in arr[] int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = tablica[i]; zwróć mx; } // Funkcja zliczająca sortowanie arr[] // według cyfry // reprezentowanej przez exp. void countSort(int arr[], int n, int exp) { // Tablica wyjściowa int wyjście[n]; int i, liczba[10] = { 0 }; // Przechowuj liczbę wystąpień // w liczbie [] for (i = 0; i< n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] // now contains actual position // of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { wyjście[liczba[(arr[i] / exp) % 10] - 1] = tablica[i]; liczba[(arr[i] / exp) % 10]--; } // Skopiuj tablicę wyjściową do arr[], // tak, aby tablica [] zawierała teraz posortowane // liczby według bieżącej cyfry dla (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] // of size n using Radix Sort void radixsort(int arr[], int n) { // Find the maximum number to // know number of digits int m = getMax(arr, n); // Do counting sort for every digit. // Note that instead of passing digit // number, exp is passed. exp is 10^i // where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Funkcja narzędziowa umożliwiająca wydrukowanie tablicy void print(int arr[], int n) { for (int i = 0; i< n; i++) cout << arr[i] << ' '; } // Driver Code int main() { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call radixsort(arr, n); print(arr, n); return 0; }> Jawa // Radix sort Java implementation import java.io.*; import java.util.*; class Radix { // A utility function to get maximum value in arr[] static int getMax(int arr[], int n) { int mx = arr[0]; for (int i = 1; i < n; i++) if (arr[i]>mx) mx = tablica[i]; zwróć mx; } // Funkcja zliczająca sortowanie arr[] według // cyfry reprezentowanej przez exp. statyczny void countSort(int arr[], int n, int exp) { int wyjście[] = nowy int[n]; // tablica wyjściowa in i; int liczba[] = nowa int[10]; Tablice.fill(liczba, 0); // Zapisz liczbę wystąpień w count[] for (i = 0; i< n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { wyjście[liczba[(arr[i] / exp) % 10] - 1] = tablica[i]; liczba[(arr[i] / exp) % 10]--; } // Skopiuj tablicę wyjściową do arr[] tak, że arr[] teraz // zawiera liczby posortowane według bieżącej // cyfry dla (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of // size n using Radix Sort static void radixsort(int arr[], int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Funkcja narzędziowa umożliwiająca wydrukowanie tablicy static void print(int arr[], int n) { for (int i = 0; i< n; i++) System.out.print(arr[i] + ' '); } // Main driver method public static void main(String[] args) { int arr[] = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.length; // Function Call radixsort(arr, n); print(arr, n); } }> Python3 # Python program for implementation of Radix Sort # A function to do counting sort of arr[] according to # the digit represented by exp. def countingSort(arr, exp1): n = len(arr) # The output array elements that will have sorted arr output = [0] * (n) # initialize count array as 0 count = [0] * (10) # Store count of occurrences in count[] for i in range(0, n): index = arr[i] // exp1 count[index % 10] += 1 # Change count[i] so that count[i] now contains actual # position of this digit in output array for i in range(1, 10): count[i] += count[i - 1] # Build the output array i = n - 1 while i>= 0: indeks = arr[i] // exp1 wyjście[liczba[indeks % 10] - 1] = arr[i] liczba[indeks % 10] -= 1 i -= 1 # Kopiowanie tablicy wyjściowej do arr[] , # tak, że arr zawiera teraz posortowane liczby i = 0 dla i w zakresie(0, len(arr)): arr[i] = wyjście[i] # Metoda wykonania Radix Sort def radixSort(arr): # Znajdź maksimum liczba, aby poznać liczbę cyfr max1 = max(arr) # Wykonuj sortowanie zliczające dla każdej cyfry. Zauważ, że zamiast # przekazywanej cyfry, przekazywane jest exp. exp to 10^i # gdzie i to bieżąca cyfra numeru exp = 1 natomiast max1 / exp>= 1: countingSort(arr, exp) exp *= 10 # Kod sterownika arr = [170, 45, 75, 90, 802, 24 , 2, 66] # Wywołanie funkcji radixSort(arr) dla i w zakresie(len(arr)): print(arr[i], end=' ') # Autorem tego kodu jest Mohit Kumra # Edytowane przez Patricka Gallaghera>
C# // C# implementation of 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 = tablica[i]; zwróć mx; } // Funkcja zliczająca sortowanie arr[] według // cyfry reprezentowanej przez exp. public static void countSort(int[] arr, int n, int exp) { int[] wyjście = nowy int[n]; // tablica wyjściowa in i; int[] liczba = nowa int[10]; // inicjalizacja wszystkich elementów count na 0 for (i = 0; i< 10; i++) count[i] = 0; // Store count of occurrences in count[] for (i = 0; i < n; i++) count[(arr[i] / exp) % 10]++; // Change count[i] so that count[i] now contains // actual // position of this digit in output[] for (i = 1; i < 10; i++) count[i] += count[i - 1]; // Build the output array for (i = n - 1; i>= 0; i--) { wyjście[liczba[(arr[i] / exp) % 10] - 1] = tablica[i]; liczba[(arr[i] / exp) % 10]--; } // Skopiuj tablicę wyjściową do arr[] tak, że arr[] teraz // zawiera liczby posortowane według bieżącej // cyfry dla (i = 0; i< n; i++) arr[i] = output[i]; } // The main function to that sorts arr[] of size n using // Radix Sort public static void radixsort(int[] arr, int n) { // Find the maximum number to know number of digits int m = getMax(arr, n); // Do counting sort for every digit. Note that // instead of passing digit number, exp is passed. // exp is 10^i where i is current digit number for (int exp = 1; m / exp>0; exp *= 10) countSort(arr, n, exp); } // Funkcja narzędziowa do drukowania tablicy public static void print(int[] arr, int n) { for (int i = 0; i< n; i++) Console.Write(arr[i] + ' '); } // Driver Code public static void Main() { int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 }; int n = arr.Length; // Function Call radixsort(arr, n); print(arr, n); } // This code is contributed by DrRoot_ }> JavaScript // Radix sort JavaScript implementation 'use strict'; // A utility function to get maximum value in arr[] function getMax(arr) { const length = arr.length; let mx = arr[0]; for (let i = 1; i < length; i++) { if (arr[i]>mx) mx = tablica[i]; } zwróć mx; } // Funkcja zliczająca sortowanie arr[] według // cyfry reprezentowanej przez exp. funkcja countSort(arr, exp) { stała długość = tablica.długość; niech wyjście = tablica (długość); // tablica wyjściowa let count = Array(10).fill(0, 0); // Zapisz liczbę wystąpień w liczniku [] for (let i = 0; tj< length; i++) { const digit = Math.floor(arr[i] / exp) % 10; count[digit]++; } // Change count[i] so that count[i] now contains // actual position of this digit in output[] for (let i = 1; i < 10; i++) { count[i] += count[i - 1]; } // Build the output array for (let i = length - 1; i>= 0; i--) { const cyfra = Math.floor(arr[i] / exp) % 10; wyjście[liczba[cyfra] - 1] = tablica[i]; liczba[cyfra]--; } zwróć wyjście; } // Główna funkcja sortująca arr[] przy użyciu funkcji sortowania Radix radixSort(arr) { // Znajdź maksymalną liczbę, aby poznać liczbę cyfr const maxNumber = getMax(arr); // Utwórz płytką kopię, w której będą przechowywane posortowane wartości let sortedArr = [...arr]; // Wykonaj sortowanie zliczające dla każdej cyfry. Zauważ, że // zamiast przekazywać cyfrę, przekazywane jest wyrażenie exp. // exp to 10^i, gdzie i to bieżąca cyfra dla (let exp = 1; Math.floor(maxNumber / exp)> 0; exp *= 10) { // Uzyskaj iterację sortowania Count const sortedIteration = countSort(sortedArr , do potęgi); sortedArr = sortedIteration; } zwróć posortowanyArr; } /*Kod sterownika*/ const arr = [170, 45, 75, 90, 802, 24, 2, 66]; // Wywołanie funkcji const sortedArr = radixSort(arr); konsola.log(sortedArr.join(' ')); // Ten kod został napisany przez beeduhboodee> PHP // PHP implementation of Radix Sort // A function to do counting sort of arr[] // according to the digit represented by exp. function countSort(&$arr, $n, $exp) { $output = array_fill(0, $n, 0); // output array $count = array_fill(0, 10, 0); // Store count of occurrences in count[] for ($i = 0; $i < $n; $i++) $count[ ($arr[$i] / $exp) % 10 ]++; // Change count[i] so that count[i] // now contains actual position of // this digit in output[] for ($i = 1; $i < 10; $i++) $count[$i] += $count[$i - 1]; // Build the output array for ($i = $n - 1; $i>= 0; $i--) { $wyjście[$liczba[($arr[$i] / $exp) % 10 ] - 1] = $arr[$i]; $liczba[($arr[$i] / $exp) % 10 ]--; } // Skopiuj tablicę wyjściową do arr[], więc // ta tablica [] zawiera teraz posortowane liczby // według bieżącej cyfry dla ($i = 0; $i< $n; $i++) $arr[$i] = $output[$i]; } // The main function to that sorts arr[] // of size n using Radix Sort function radixsort(&$arr, $n) { // Find the maximum number to know // number of digits $m = max($arr); // Do counting sort for every digit. Note // that instead of passing digit number, // exp is passed. exp is 10^i where i is // current digit number for ($exp = 1; $m / $exp>0; $exp *= 10) countSort($arr, $n, $exp); } // Funkcja narzędziowa umożliwiająca wydrukowanie funkcji tablicowej PrintArray(&$arr,$n) { for ($i = 0; $i< $n; $i++) echo $arr[$i] . ' '; } // Driver Code $arr = array(170, 45, 75, 90, 802, 24, 2, 66); $n = count($arr); // Function Call radixsort($arr, $n); PrintArray($arr, $n); // This code is contributed by rathbhupendra ?>> Strzałka // Radix sort Dart implementation /// A utility function to get the maximum value of a `List` [array] int getMax(List tablica) { int max = tablica[0]; for (zakończ w tablicy) { if (it> max) { max = it; } } zwróć maks.; } /// Funkcja zliczająca sortowanie `Listy` [tablica] według /// cyfry reprezentowanej przez [exp]. Lista liczbaSortuj(Lista array, int exp) { długość końcowa = tablica.długość; końcowe wyjścieArr = List.filled(długość, 0); // Lista, gdzie indeks reprezentuje cyfrę, a wartość reprezentuje liczbę // wystąpień finaldigitsCount = List.filled(10, 0); // Zapisz liczbę wystąpień w cyfrachCount[] for (końcowy element w tablicy) { ostatnia cyfra = pozycja ~/ exp % 10; cyfryLiczba[cyfra]++; } // Zmień cyfryCount[i] tak, aby cyfryCount[i] zawierały teraz rzeczywistą pozycję // tej cyfry w OutputArr[] for (int i = 1; i< 10; i++) { digitsCount[i] += digitsCount[i - 1]; } // Build the output array for (int i = length - 1; i>= 0; i--) { element końcowy = tablica[i]; ostatnia cyfra = pozycja ~/ exp % 10; OutputArr[cyfryLiczba[cyfra] - 1] = pozycja; cyfryLiczba[cyfra]--; } zwróć wynikowy Arr; } /// Główna funkcja sortująca `Listę` [tablicę] przy użyciu listy sortowania Radix radixSort(Lista array) { // Znajdź maksymalną liczbę, aby poznać liczbę cyfr final maxNumber = getMax(array); // Płytka kopia tablicy wejściowej final sortedArr = List.of(array); // Wykonaj sortowanie zliczające dla każdej cyfry. Zauważ, że zamiast przekazywać cyfrę // liczbę, przekazywane jest wyrażenie. exp to 10^i, gdzie i to bieżąca cyfra dla (int exp = 1; maxNumber ~/ exp> 0; exp *= 10) { final sortedIteration = countSort(sortedArr, exp); sortowaneArr.clear(); sortedArr.addAll(sortedIteration); } zwróć posortowanyArr; } void main() { const tablica = [170, 45, 75, 90, 802, 24, 2, 66]; final sortedArray = radixSort(tablica); print(posortowana tablica); } // Ten kod został stworzony przez beeduhboodee>
Wyjście
2 24 45 66 75 90 170 802>
Analiza złożoności sortowania radiacyjnego :
Złożoność czasowa:
- Sortowanie radiacyjne to nieporównawczy algorytm sortowania liczb całkowitych, który sortuje dane za pomocą kluczy całkowitych, grupując klucze według poszczególnych cyfr, które mają tę samą znaczącą pozycję i wartość. Ma złożoność czasową O(d * (n + b)) , gdzie d to liczba cyfr, n to liczba elementów, a b to podstawa używanego systemu liczbowego.
- W praktycznych implementacjach sortowanie radix jest często szybsze niż inne algorytmy sortowania oparte na porównaniach, takie jak sortowanie szybkie lub sortowanie przez scalanie, w przypadku dużych zbiorów danych, zwłaszcza gdy klucze mają wiele cyfr. Jednak jego złożoność czasowa rośnie liniowo wraz z liczbą cyfr, dlatego nie jest tak wydajna w przypadku małych zbiorów danych.
Przestrzeń pomocnicza:
znak w ciągu
- Sortowanie radiacyjne ma również złożoność przestrzenną O(n + b), gdzie n jest liczbą elementów, a b jest podstawą systemu liczbowego. Ta złożoność przestrzeni wynika z konieczności tworzenia segmentów dla każdej wartości cyfry i kopiowania elementów z powrotem do oryginalnej tablicy po posortowaniu każdej cyfry.
Często zadawane pytania dotyczące RadixSort
Pytanie 1. Czy sortowanie Radix jest lepsze niż algorytmy sortowania oparte na porównaniu, takie jak Quick-Sort?
Jeśli mamy log2n bitów na każdą cyfrę, czas działania Radix wydaje się być lepszy niż Szybkie sortowanie dla szerokiego zakresu liczb wejściowych. Stałe współczynniki ukryte w notacji asymptotycznej są wyższe w przypadku sortowania radiacyjnego, a szybkie sortowanie efektywniej wykorzystuje sprzętowe pamięci podręczne. Ponadto sortowanie Radix wykorzystuje sortowanie przez zliczanie jako podprogram, a sortowanie przez zliczanie zajmuje dodatkową przestrzeń do sortowania liczb.
Pytanie 2. A co jeśli elementy znajdują się w zakres od 1 do n 2 ?
- Dolna granica algorytmu sortowania opartego na porównaniu (sortowanie przez scalanie, sortowanie sterty, sortowanie szybkie itp.) wynosi Ω(nLogn), co oznacza, że nie mogą one działać lepiej niż nZaloguj się . Sortowanie zliczające to liniowy algorytm sortowania według czasu, który sortuje w czasie O(n+k), gdy elementy znajdują się w zakresie od 1 do k.
- Nie możemy użyć sortowania zliczającego, ponieważ sortowanie zliczające zajmie O(n2), co jest gorsze niż algorytmy sortowania opartego na porównaniach. Czy możemy posortować taką tablicę w czasie liniowym?
- Sortuj Radix jest odpowiedzią. Ideą Radix Sort jest sortowanie cyfra po cyfrze, zaczynając od cyfry najmniej znaczącej do cyfry najbardziej znaczącej. Sortowanie Radix wykorzystuje sortowanie zliczające jako podprogram sortowania.