Radix šķirošanas algoritms

Šajā apmācībā jūs uzzināsiet, kā darbojas radix šķirošana. Jūs atradīsit arī radix kārtojuma piemērus C, C ++, Java un Python.

Radix sort ir šķirošanas paņēmiens, kas kārto elementus, vispirms sagrupējot tās pašas vietas atsevišķos ciparus . Pēc tam kārtojiet elementus pēc to pieaugošā / samazināšanās secības.

Pieņemsim, ka mums ir 8 elementu masīvs. Pirmkārt, mēs kārtosim elementus, pamatojoties uz vienības vietas vērtību. Pēc tam mēs kārtosim elementus, pamatojoties uz desmitās vietas vērtību. Šis process turpinās līdz pēdējai nozīmīgajai vietai.

Ļaujiet sākotnējam masīvam būt (121, 432, 564, 23, 1, 45, 788). Tas ir sakārtots pēc radix veida, kā parādīts attēlā zemāk.

Radix Sort darbs

Pirms lasāt šo rakstu, lūdzu, veiciet skaitīšanas kārtību, jo skaitīšanas kārtojums tiek izmantots kā starpsada kārtojums radix kārtojumā.

Kā darbojas Radix Sort?

  1. Atrodiet masīva lielāko elementu, ti, maks. Ļaut Xbūt ciparu skaits max. Xtiek aprēķināts, jo mums jāiet cauri visām nozīmīgajām visu elementu vietām.
    Šajā masīvā (121, 432, 564, 23, 1, 45, 788)mums ir lielākais skaitlis 788. Tam ir 3 cipari. Tāpēc cilpai vajadzētu iet uz augšu simtiem vietu (3 reizes).
  2. Tagad iet pa katru nozīmīgo vietu pa vienam.
    Izmantojiet jebkuru stabilu šķirošanas paņēmienu, lai kārtotu ciparus katrā nozīmīgajā vietā. Mēs tam izmantojām skaitīšanas kārtību.
    Kārtojiet elementus, pamatojoties uz vienības vietas cipariem ( X=0). Izmantojot skaitīšanas kārtojumu, lai kārtotu elementus, pamatojoties uz vietu vienību
  3. Tagad kārtojiet elementus, pamatojoties uz cipariem desmitos. Kārtojiet elementus, pamatojoties uz desmitiem
  4. Visbeidzot, kārtojiet elementus, pamatojoties uz cipariem simtiem vietu. Kārtojiet elementus, pamatojoties uz simtiem vietu

Radix šķirošanas algoritms

 radixSort (masīvs) d <- maksimālais ciparu skaits lielākajā elementā izveido d spaiņus ar lielumu 0-9 i <- 0, lai d kārtotu elementus pēc i-tiem vietas cipariem, izmantojot countingSort countingSort (masīvs, d) max <- atrast lielākais elements starp d-tās vietas elementiem inicializē skaitīšanas masīvu ar visām nullēm j <- 0, lai izmērs atrastu katra unikālā cipara kopējo daudzumu elementu d-tajā vietā un saglabātu skaitu j-tajā indeksā skaitīšanas masīvā i <- 1 līdz max atrastu kumulatīvā summa un glabājiet to pašā skaitīšanas masīvā j <- izmērs līdz 1, lai atjaunotu elementus, lai masīvs samazinātu katra elementa skaitu, kas atjaunots par 1

Python, Java un C / C ++ piemēri

Python Java C C ++ 
 # Radix sort in Python # Using counting sort to sort the elements in the basis of significant places def countingSort(array, place): size = len(array) output = (0) * size count = (0) * 10 # Calculate count of elements for i in range(0, size): index = array(i) // place count(index % 10) += 1 # Calculate cummulative count for i in range(1, 10): count(i) += count(i - 1) # Place the elements in sorted order i = size - 1 while i>= 0: index = array(i) // place output(count(index % 10) - 1) = array(i) count(index % 10) -= 1 i -= 1 for i in range(0, size): array(i) = output(i) # Main function to implement radix sort def radixSort(array): # Get maximum element max_element = max(array) # Apply counting sort to sort elements based on place value. place = 1 while max_element // place> 0: countingSort(array, place) place *= 10 data = (121, 432, 564, 23, 1, 45, 788) radixSort(data) print(data) 
 // Radix Sort in Java Programming import java.util.Arrays; class RadixSort ( // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int() output = new int(size + 1); int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i < size; i++) array(i) = output(i); ) // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Main function to implement radix sort void radixSort(int array(), int size) ( // Get maximum element int max = getMax(array, size); // Apply counting sort to sort elements based on place value. for (int place = 1; max / place> 0; place *= 10) countingSort(array, size, place); ) // Driver code public static void main(String args()) ( int() data = ( 121, 432, 564, 23, 1, 45, 788 ); int size = data.length; RadixSort rs = new RadixSort(); rs.radixSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Radix Sort in C Programming #include // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( int output(size + 1); int max = (array(0) / place) % 10; for (int i = 1; i max) max = array(i); ) int count(max + 1); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i <10; i++) count(i) += count(i - 1); // Place the elements in sorted order for (int i = size - 1; i>= 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )
 // Radix Sort in C++ Programming #include using namespace std; // Function to get the largest element from an array int getMax(int array(), int n) ( int max = array(0); for (int i = 1; i max) max = array(i); return max; ) // Using counting sort to sort the elements in the basis of significant places void countingSort(int array(), int size, int place) ( const int max = 10; int output(size); int count(max); for (int i = 0; i < max; ++i) count(i) = 0; // Calculate count of elements for (int i = 0; i < size; i++) count((array(i) / place) % 10)++; // Calculate cummulative count for (int i = 1; i  = 0; i--) ( output(count((array(i) / place) % 10) - 1) = array(i); count((array(i) / place) % 10)--; ) for (int i = 0; i 0; place *= 10) countingSort(array, size, place); ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (121, 432, 564, 23, 1, 45, 788); int n = sizeof(array) / sizeof(array(0)); radixsort(array, n); printArray(array, n); )

Sarežģītība

Tā kā radiksa šķirošana nav salīdzinošs algoritms, tam ir priekšrocības salīdzinājumā ar salīdzinošās šķirošanas algoritmiem.

Radix kārtojumam, kas izmanto skaitīšanas kārtību kā stabilu starpposma kārtošanu, laika sarežģītība ir O(d(n+k)).

Šeit dir skaitļu cikls un O(n+k)laika skaitīšanas kārtības sarežģītība.

Tādējādi radix šķirošanai ir lineāra laika sarežģītība, kas ir labāka nekā O(nlog n)salīdzinošajiem šķirošanas algoritmiem.

Ja mēs ņemam ļoti lielus ciparus vai citu bāzu skaitu, piemēram, 32 bitu un 64 bitu skaitļus, tas var darboties lineārā laikā, tomēr starpposma kārtošana aizņem lielu vietu.

Tas padara radix šķirošanas vietu neefektīvu. Tas ir iemesls, kāpēc šāda veida programmatūras bibliotēkās netiek izmantota.

Radix kārtot lietojumprogrammas

Radix šķirošana ir ieviesta

  • DC3 algoritms (Kärkkäinen-Sanders-Burkhardt), veidojot sufiksu masīvu.
  • vietas, kur ir skaitļi lielos diapazonos.

Interesanti raksti...