Radix Sort di Java

1. Perkenalan

Dalam tutorial ini, kita akan belajar tentang Radix Sort, menganalisis kinerjanya, dan melihat implementasinya.

Di sini kami fokus menggunakan Radix Sort untuk mengurutkan bilangan bulat, tetapi tidak terbatas hanya pada angka. Kita bisa menggunakannya untuk mengurutkan tipe lain seperti String juga.

Untuk membuatnya tetap sederhana, kita akan fokus pada sistem desimal di mana angka-angka tersebut dinyatakan dalam basis (radix) 10.

2. Gambaran Algoritma

Radix sort adalah algoritma pengurutan yang mengurutkan angka berdasarkan posisi digitnya. Pada dasarnya, ini menggunakan nilai tempat dari digit dalam sebuah angka. Tidak seperti kebanyakan algoritma pengurutan lainnya, seperti Merge Sort, Insertion Sort, Bubble Sort, ini tidak membandingkan angka.

Radix sort menggunakan algoritme pengurutan yang stabil sebagai subrutin untuk mengurutkan digit. Kami telah menggunakan variasi urutan penghitungan sebagai subrutin di sini yang menggunakan akar untuk mengurutkan digit di setiap posisi. Jenis penghitungan adalah algoritme pengurutan yang stabil dan bekerja dengan baik dalam praktiknya.

Radix sort bekerja dengan menyortir digit dari Digit Signifikan Terkecil (LSD) ke Digit Paling Signifikan (MSD). Kami juga dapat menerapkan penyortiran Radix untuk memproses digit dari MSD.

3. Contoh Cepat

Mari kita lihat cara kerjanya dengan sebuah contoh. Mari pertimbangkan larik berikut:

Iterasi 1:

Kami akan mengurutkan array ini dengan memproses digit dari LSD dan bergerak menuju MSD.

Jadi mari kita mulai dengan angka di satu tempat:

Setelah iterasi pertama, array sekarang terlihat seperti:

Perhatikan bahwa nomor telah diurutkan menurut digit di satu tempat.

Iterasi 2:

Mari beralih ke digit di tempat puluhan:

Sekarang arraynya terlihat seperti:

Kita melihat bahwa angka 7 telah menempati posisi pertama dalam larik karena tidak memiliki digit di tempat puluhan. Kita juga bisa menganggap ini sebagai memiliki 0 di tempat puluhan.

Iterasi 3:

Mari beralih ke angka dalam posisi ratusan:

Setelah iterasi ini, arraynya terlihat seperti:

Dan algoritme berhenti di sini, dengan semua elemen diurutkan.

4. Implementasi

Sekarang mari kita lihat implementasinya.

void sort(int[] numbers) { int maximumNumber = findMaximumNumberIn(numbers); int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber); int placeValue = 1; while (numberOfDigits-- > 0) { applyCountingSortOn(numbers, placeValue); placeValue *= 10; } }

Algoritme bekerja dengan mencari jumlah maksimum dalam larik dan kemudian menghitung panjangnya. Langkah ini membantu kami memastikan bahwa kami menjalankan subrutin untuk setiap nilai tempat.

Misalnya, dalam larik, [7, 37, 68, 123, 134, 221, 387, 468, 769] , jumlah maksimumnya adalah 769 dan panjangnya 3.

So, we iterate and apply the subroutine thrice on the digits in every position:

void applyCountingSortOn(int[] numbers, int placeValue) { int range = 10 // decimal system, numbers from 0-9 // ... // calculate the frequency of digits for (int i = 0; i < length; i++) { int digit = (numbers[i] / placeValue) % range; frequency[digit]++; } for (int i = 1; i 
    
     = 0; i--) { int digit = (numbers[i] / placeValue) % range; sortedValues[frequency[digit] - 1] = numbers[i]; frequency[digit]--; } System.arraycopy(result, 0, numbers, 0, length); }
    

In the subroutine, we've used the radix (range) to count the occurrence of each digit and increment its frequency. So, each bin in the range from 0 to 9 will have some value based on the frequency of digits. We then use the frequency to position each element in the array. This also helps us to minimize the space required to sort the array.

Now let's test our method:

@Test public void givenUnsortedArray_whenRadixSort_thenArraySorted() { int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort(numbers); int[] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals(numbersSorted, numbers); }

5. Radix Sort vs Counting Sort

In the subroutine, the length of the frequency array is 10 (0-9). In the case of Counting Sort, we don't use the range. The length of the frequency array will be the maximum number in the array + 1. So we don't divide them into bins whereas Radix Sort uses the bins to sort.

Counting Sort is quite efficient when the length of the array is not much smaller than the maximum value in the array whereas Radix Sort allows for larger values in the array.

6. Complexity

The performance of Radix Sort depends on the stable sorting algorithm chosen to sort the digits.

Di sini kita telah menggunakan Radix Sort untuk mengurutkan larik n angka dalam basis b . Dalam kasus kita, basisnya adalah 10. Kita telah menerapkan Jenis Penghitungan d kali di mana d adalah jumlah digit. Jadi kompleksitas waktu Radix Sort menjadi O (d * (n + b)) .

Kompleksitas ruang adalah O (n + b) karena kita telah menggunakan variasi dari Counting Sort sebagai subrutin di sini.

7. Kesimpulan

Dalam artikel ini, kami menjelaskan algoritme pengurutan Radix dan mengilustrasikan cara mengimplementasikannya.

Seperti biasa, implementasi kode tersedia di Github.