Algoritma Radix Sort

Dalam tutorial ini, Anda akan mempelajari cara kerja radix sort. Juga, Anda akan menemukan contoh kerja pengurutan radix di C, C ++, Java dan Python.

Pengurutan radix adalah teknik pengurutan yang menyortir elemen dengan terlebih dahulu mengelompokkan digit individu dari nilai tempat yang sama . Kemudian, urutkan elemen-elemen tersebut menurut urutan naik / turunnya.

Misalkan, kita memiliki array 8 elemen. Pertama, kita akan mengurutkan elemen berdasarkan nilai tempat satuan. Kemudian, kami akan mengurutkan elemen berdasarkan nilai tempat kesepuluh. Proses ini berlangsung hingga tempat penting terakhir.

Biarkan array awal menjadi (121, 432, 564, 23, 1, 45, 788). Ini diurutkan menurut jenis radix seperti yang ditunjukkan pada gambar di bawah ini.

Cara Kerja Radix Sort

Harap telusuri jenis penghitungan sebelum membaca artikel ini karena jenis penghitungan digunakan sebagai jenis perantara dalam jenis radix.

Bagaimana Radix Sort Bekerja?

  1. Temukan elemen terbesar dalam larik, yaitu maks. Membiarkan Xmenjadi jumlah digit dalam max. Xdihitung karena kita harus melalui semua tempat penting dari semua elemen.
    Dalam larik ini (121, 432, 564, 23, 1, 45, 788), kami memiliki angka terbesar 788. Ini memiliki 3 digit. Oleh karena itu, loop harus naik ke ratusan tempat (3 kali).
  2. Sekarang, telusuri setiap tempat penting satu per satu.
    Gunakan teknik penyortiran stabil apa pun untuk mengurutkan angka di setiap tempat penting. Kami telah menggunakan jenis penghitungan untuk ini.
    Sortir elemen berdasarkan digit tempat satuan ( X=0). Menggunakan urutan penghitungan untuk mengurutkan elemen berdasarkan tempat satuan
  3. Sekarang, urutkan elemen berdasarkan digit di tempat puluhan. Urutkan elemen berdasarkan tempat puluhan
  4. Terakhir, urutkan elemen berdasarkan digit di ratusan tempat. Urutkan elemen berdasarkan ratusan tempat

Algoritma Radix Sort

 radixSort (array) d <- jumlah maksimum digit dalam elemen terbesar buat d ember ukuran 0-9 untuk i <- 0 hingga d mengurutkan elemen sesuai dengan digit tempat ke i menggunakan countSort countSort (array, d) max <- find elemen terbesar di antara elemen tempat d menginisialisasi larik hitungan dengan semua nol untuk j <- 0 untuk ukuran menemukan jumlah total setiap digit unik di tempat ke d elemen dan menyimpan hitungan pada indeks ke j dalam larik hitungan untuk i <- 1 hingga pencarian maksimal jumlah kumulatif dan menyimpannya dalam array hitungan itu sendiri untuk j <- size down to 1 restore elemen ke array pengurangan jumlah setiap elemen dipulihkan oleh 1

Contoh Python, Java dan C / C ++

Python Java 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); )

Kompleksitas

Karena jenis radix adalah algoritma non-komparatif, ia memiliki keunggulan dibandingkan algoritma pengurutan komparatif.

Untuk jenis radix yang menggunakan urutan penghitungan sebagai pengurutan stabil menengah, kompleksitas waktunya adalah O(d(n+k)).

Di sini, dadalah siklus bilangan dan O(n+k)kompleksitas waktu dari urutan penghitungan.

Jadi, jenis radix memiliki kompleksitas waktu linier yang lebih baik daripada O(nlog n)algoritma pengurutan komparatif.

Jika kita mengambil angka digit yang sangat besar atau jumlah basis lain seperti angka 32-bit dan 64-bit maka itu dapat dilakukan dalam waktu linier namun jenis perantara membutuhkan ruang yang besar.

Hal ini membuat ruang sortir radix menjadi tidak efisien. Inilah alasan mengapa jenis ini tidak digunakan di perpustakaan perangkat lunak.

Aplikasi Radix Sort

Jenis Radix diimplementasikan di

  • Algoritma DC3 (Kärkkäinen-Sanders-Burkhardt) saat membuat array sufiks.
  • tempat-tempat yang banyak jumlahnya.

Artikel yang menarik...