Radix sort

Radix lub baza jest reprezentacją liczby, która pokazuje, ile cyfr jest wymaganych do przedstawienia liczby pozycji. Na przykład, aby przedstawić liczbę binarną, wartość radix wynosi 2 (reprezentujemy binarne z 0 lub 1). Aby reprezentować liczbę dziesiętną, wartość Radix wynosi 10 (reprezentujemy liczbę dziesiętną z liczbami od 0 do 9).

Jak działa algorytm sortowania Redix

Załóżmy, że mamy następującą listę tablicy i chcemy sortować tę tablicę za pomocą SORT Radix:

W tym algorytmie używamy dwóch kolejnych koncepcji:

1. 1. Najmniej znacząca cyfra
   2. Najważniejsza cyfra

1. Najmniej znacząca cyfra (LSD): Wartość wykładnika liczby dziesiętnej, która jest bardzo zbliżona do pozycji najbardziej prawej, jest określana jako LSD.

Na przykład liczba dziesiętna „2563” ma najmniej znaczącą wartość cyfrową „3”.

2. Najważniejsza cyfra (MSD): MSD jest dokładną odwrotnością LSD. Wartość MSD to niezerowa najszersza cyfra dowolnej liczby dziesiętnej.

Na przykład liczba dziesiętna „2563” ma najważniejszą wartość cyfrową „2”.

Krok 1: Poszukaj najważniejszego elementu (wartość maksymalna)

Jak już wiemy, ten algorytm działa na cyfrach, aby sortować liczby. W tym celu ten algorytm wymaga maksymalnej liczby cyfr do iteracji. Naszym pierwszym krokiem jest znalezienie maksymalnej liczby elementów w tej tablicy. Po znalezieniu maksymalnej wartości tablicy musimy policzyć liczbę cyfr w tej liczbie.

Krok 2: Policz liczbę cyfr maksymalnego elementu

Musimy policzyć liczbę cyfr maksymalnego elementu tablicy, ponieważ wtedy możemy dowiedzieć się, ile iteracji potrzebujemy, aby sortować tablicę.

Tak więc, jak już się dowiedzieliśmy, maksymalny element to 167, a liczba cyfr to 3. Potrzebujemy trzech iteracji, aby sortować tablicę.

Krok 3: Sortowanie elementów za pomocą najmniej znaczącej cyfry

Pierwszy układ cyfrowy odbywa się przy najmniej znaczącej cyfrze. Z następującego obrazu widzimy, że wszystkie najmniejsze, najmniej znaczące cyfry są ułożone po lewej stronie. W tym przypadku skupiamy się tylko na najmniej znaczącej cyfrze.

Jeszcze jedna rzecz, którą możemy tutaj zauważyć, jest to, że niektóre cyfry są automatycznie sortowane, nawet jeśli ich cyfry jednostek są różne, ale inne są takie same.

Na przykład, Liczby 36 w pozycji indeksu 7, jak i liczba 32 w pozycji indeksu 3 mają różne cyfry jednostkowe, ale mają tę samą inną liczbę, czyli 3. Oczywiście numer 32 pojawia się przed numerem 36. Po pierwszych ustaleniach elementu możemy zobaczyć, że teraz 32 jest przed 36.

Krok 4: Sortowanie elementów zgodnie z następną cyfrą (Tens Digit)

Teraz organizujemy elementy tablicy przez dziesiątą cyfrę. Jak już wiemy, to sortowanie musi zostać zakończone w 3 iteracjach, ponieważ maksymalna liczba elementów ma 3 cyfry. To jest nasza druga iteracja i możemy założyć, że większość elementów tablicy jest sortowana po tej iteracji.

Podane wyniki pokazują, że większość elementów tablicy jest już sortowana (poniżej 100). Gdybyśmy mieli tylko dwie cyfry jako naszą maksymalną liczbę, wystarczą tylko dwa iteracje, aby uzyskać posortowaną tablicę.

Krok 5: Sortowanie elementów na podstawie najważniejszej cyfry

Teraz wchodzimy do trzeciej iteracji opartej na najważniejszej cyfrze (setki miejsca). Ta iteracja sortuje trzy cyfrowe elementy tablicy. Po tej iteracji wszystkie elementy tablicy są w sortowanej kolejności.

Po zorganizowaniu elementów na podstawie MSD, nasza tablica jest teraz w pełni posortowana.

Zrozumieliśmy pojęcia algorytmu sortowania Radixa. Ale potrzebujemy jeszcze jednego algorytmu do zaimplementowania sortowania Radix, a to jest Liczenie algorytmu sortowania. Zrozummy to Liczenie algorytmu sortowania.

Liczenie algorytmu sortowania

Teraz wyjaśniamy każdy etap algorytmu sortowania liczenia.

Dostarczona tablica to nasza tablica wejściowa, a liczby pokazane powyżej tablicy to liczby indeksu odpowiednich elementów.

Krok 1: Wyszukaj maksymalny element

Pierwszym krokiem w algorytmie sortowania zliczania jest wyszukiwanie maksymalnego elementu w całej tablicy. Najlepszym sposobem wyszukiwania maksymalnego elementu jest przemierzanie całej tablicy i porównanie elementów w każdej iteracji - element większej wartości jest aktualizowany do końca tablicy.

Podczas pierwszego kroku stwierdziliśmy, że element maksymalny wynosi 9 w pozycji indeksu 8.

Krok 2: Zrób nowy zestaw porównywalnych rozmiarów

Tworzymy nową gamę podobnych rozmiarów. Jak już wiemy, maksymalna wartość tablicy wynosi 9, więc będzie w sumie 10 elementów. W rezultacie wymagamy maksymalnego rozmiaru tablicy + 1.

Jak widać na poprzednim obrazie, mamy całkowity rozmiar tablicy 10 o wartości 0. W następnym kroku wypełniamy tę tablicę liczby posortowanymi elementami.

Krok 3: Wypełnij nową tablicę zgodnie z częstotliwością każdego elementu

W tym etapie liczymy każdy element i, zgodnie z ich częstotliwością, wypełniamy odpowiednie wartości w tablicy.

Na przykład, Jak widzimy, element 6 jest obecny dwa razy w tablicy wejściowej. Wprowadzamy więc wartość częstotliwości 2 przy indeksie 6.

Krok 4: Określ częstotliwość skumulowaną

Teraz liczymy skumulowaną częstotliwość wypełnionej tablicy. Ta skumulowana częstotliwość jest używana później do sortowania tablicy wejściowej.

Możemy obliczyć częstotliwość skumulowaną, dodając bieżącą wartość do poprzedniej wartości indeksu, jak pokazano na poniższym zrzucie ekranu:

Ostatnią wartością tablicy w łącznej tablicy musi być całkowita liczba elementów.

Krok 5: Sortowanie tablicy według częstotliwości przemiennej

Teraz używamy kumulatywnej tablicy częstotliwości, aby zmapować każdy element tablicy, aby wytworzyć posortowaną tablicę.

Na przykład, Pierwszy element w tablicy 5, którą wybieramy. Następnie odpowiednia skumulowana wartość częstotliwości w indeksie 5, która ma wartość 7. Zmniejszamy wartość o 1 i otrzymaliśmy 6. Umieszczamy wartość 5 w indeksie w pozycji 6, a także zmniejszamy częstotliwość skumulowaną w indeksie 5 na 1.

Częstotliwość skumulowana jest w indeksie 5 po zmniejszeniu o jeden.

Zrozumiemy tę koncepcję z jeszcze jednym przykładem.

Następny element w tablicy to 2. Wybieramy wartość indeksu 2 w tablicy częstotliwości przemiennej. Zmniejszamy wartość w indeksie 2 i otrzymujemy 1. Umieszczamy element tablicy 2 w pozycji indeksu 1. Na końcu zmniejszamy wartość częstotliwości przy wskaźniku 2 na 1, jak pokazano na poniższym zrzucie ekranu:

Z poprzedniej sortowanej tablicy widzimy, że tylko jedno miejsce pozostało przed 2 (pozycja indeksu 1) i jedna wartość mniejsza niż 2 w oryginalnej tablicy, która wynosi 1. Tak więc idzie we właściwy sposób sortowania tablicy.

Nie musimy pamiętać, aby zmniejszyć wartość skumulowaną przy każdej iteracji. Po dwóch poprzednich iteracjach skumulowana tablica wygląda jak następujące:

Krok 6: Ostateczna tablica

Uruchamiamy krok 5, aż każde elementy tablicy zostaną wypełnione w posortowanej tablicy. Po jego wypełnieniu nasza tablica wygląda tak:

Program C ++ dla algorytmu sortowania Radix

Ten przykład opiera się na wyjaśnieniu w tym samouczku wskazów Linuksa

#włączać
za pomocą przestrzeni nazw Std;
void Radixsortalgo (int a [], int size_of_a)
// W pierwszym etapie (krok 1) FINą maksymalną wartość w tablicy.
int Maximumumber = a [0];
dla (int i = 1; imaximumumber = maks. (Maximumumber, a [i]);

// W drugim etapie (kroku 2) obliczamy liczbę cyfr
// maksymalny element tablicy
int digitsCount = 0;
while (Maximumumber> 0)
DigitsCount ++;
Maximumumber /= 10;

// aktualizujemy teraz nową tablicę (kroki 3,4 i 5)
dla (int i = 0; iint pwr = pow (10, i);
int new_a [size_of_a];
// To jest liczba_arey, która jest używana do tablicy zliczania
// do sortowania cyfr od 0 do 9.
int count_array [10];
memset (count_array, 0, sizeof (count_array));
// Obliczanie częstotliwości każdego elementu tablicy
for (int j = 0; jint num = (A [j]/pWr) % 10;
count_array [num] ++;

// To jest komulacyjna częstotliwość
dla (int j = 1; j<10;j++)
count_array [j] += count_array [j-1];

// mapujemy tablicę częstotliwości z każdym elementem
// tablicy, aby znaleźć pożądaną pozycję w zaktualizowanej tablicy
for (int j = size_of_a-1; j> = 0; j-)
int num = (A [j]/pWr) % 10;
new_a [count_array [num] -1] = a [j];
count_array [num]-;

// Teraz aktualizujemy tablicę o nowej tablicy
for (int j = 0; ja [j] = new_a [j];

// Wreszcie drukujemy wynik posortowanej tablicy
for (int j = 0; jCout<Cout<
int main ()
// Ta tablica wartości zostanie sortowana za pomocą algorytmu sortowania Radix.
int a [] = 155, 10, 51, 38, 16, 811, 755, 3, 91, 6;
// obliczamy rozmiar tablicy
int size_of_a = sizeof (a)/sizeof (size_of_a);
// Wzywa do metody algorytmu sortowania Radix
Radixsortalgo (a, size_of_a);
zwrot 1;

Wyjście z uruchamiania sortowania C+ Radix

Linuxhint@Desktop: ~ $ ./źródło
3 6 10 16 38 51 91 155 755 811
Linuxhint@Desktop: ~ $

Złożoność czasu algorytmu sortowania radix

Obliczmy złożoność czasu algorytmu sortowania Radix.

Krok 1: Aby obliczyć maksymalną liczbę elementów w całej tablicy, przemierzamy całą tablicę. Tak więc całkowity wymagany czas to O (n).

Krok 2: Załóżmy, że całkowitą cyfry w maksymalnej liczbie to k. Tak więc całkowity czas, który ma na celu obliczenie liczby cyfr w maksymalnej liczbie, wynosi O (K).

Kroki 3 do 5: Te kroki działają na samych cyfrach, więc biorą O (K) razy wraz z liczeniem algorytmu sortowania przy każdej iteracji - O (K * N).

W rezultacie całkowita złożoność czasu wynosi O (K * N).

Wniosek

Badaliśmy algorytm sortowania i zliczania Radixa. Istnieją różne rodzaje algorytmów sortowania, które są dostępne na rynku. Najlepszy algorytm zależy również od wymagań. Nie jest łatwo powiedzieć, który algorytm jest najlepszy. Ale na podstawie złożoności czasu staramy się znaleźć najlepszy algorytm. Na podstawie tego Radix jest również jednym z najlepszych algorytmów do sortowania.