Algoritma Sortir Radix dalam Struktur Data

Apa itu Algoritma Radix Sort?

Radix Sort adalah algoritma pengurutan non-komparatif. Ia bekerja dengan mengelompokkan digit individual dari elemen yang akan diurutkan. Teknik pengurutan yang stabil kemudian digunakan untuk mengatur elemen berdasarkan radixnya. Ini adalah algoritma pengurutan linier.

Proses penyortiran melibatkan properti berikut:

Menemukan elemen maksimum dan memperoleh jumlah digit elemen tersebut. Ini memberi kita jumlah iterasi yang akan diikuti oleh proses penyortiran.
Kelompokkan masing-masing digit elemen pada posisi signifikan yang sama di setiap iterasi.
Proses pengelompokan akan dimulai dari angka paling signifikan dan berakhir pada angka paling signifikan.
Mengurutkan unsur berdasarkan angka pada posisi penting tersebut.
Mempertahankan urutan relatif elemen yang memiliki nilai kunci yang sama. Sifat pengurutan radix ini menjadikannya pengurutan stabil.

Iterasi terakhir akan memberi kita daftar yang terurut sepenuhnya.

Cara Kerja Algoritma Radix Sort

Mari kita coba mengurutkan daftar bilangan bulat pada gambar di atas dalam urutan menaik menggunakan algoritma Radix Sort.

Berikut langkah-langkah untuk melakukan proses Radix Sorting:

Langkah 1) Identifikasi elemen dengan nilai maksimum dalam daftar. Dalam hal ini adalah 835.

Langkah 2) Hitung jumlah digit elemen maksimum. 835 mempunyai 3 digit persisnya.

Langkah 3) Tentukan banyaknya iterasi berdasarkan langkah ke 2. 835 mempunyai 3 digit, artinya jumlah iterasinya adalah 3.

Langkah 4) Tentukan basis unsur-unsurnya. Karena ini adalah sistem desimal, basisnya adalah 10.

Langkah 5) Mulai iterasi pertama.

a) Iterasi pertama

Pada iterasi pertama, kami mempertimbangkan nilai tempat satuan setiap elemen.

Langkah 1) Ubah bilangan bulat sebanyak 10 untuk mendapatkan tempat satuan elemen. Misalnya, 623 mod 10 memberi kita nilai 3, dan 248 mod 10 memberi kita nilai 8.

Langkah 2) Gunakan pengurutan penghitungan atau pengurutan stabil lainnya untuk mengurutkan bilangan bulat berdasarkan digit terkecilnya. Dilihat dari gambar, 248 akan jatuh pada ember ke-8. 623 akan jatuh pada ember ke 3 dan seterusnya.

Setelah iterasi pertama, daftarnya sekarang terlihat seperti ini.

Seperti yang dapat Anda lihat dari gambar di atas, daftar tersebut belum diurutkan dan memerlukan lebih banyak iterasi untuk dapat diurutkan sepenuhnya.

b) Iterasi kedua

Dalam iterasi ini, kita akan mempertimbangkan angka 10^th tempat untuk proses penyortiran.

Langkah 1) Bagilah bilangan bulat dengan 10. 248 dibagi 10 menghasilkan 24.

Langkah 2) Mod keluaran langkah 1 kali 10. 24 mod 10 memberi kita 4.

Langkah 3) Ikuti langkah 2 dari iterasi sebelumnya.

Setelah iterasi kedua, daftarnya sekarang terlihat seperti ini

Anda dapat melihat dari gambar di atas bahwa daftar tersebut masih belum terurut sepenuhnya karena belum dalam urutan menaik.

c) Iterasi ketiga

Untuk iterasi terakhir, kami ingin mendapatkan angka paling signifikan. Dalam hal ini, itu adalah 100^thtempatkan untuk masing-masing bilangan bulat dalam daftar.

Langkah 1) Bagilah bilangan bulat dengan 100… 415 dibagi 100 menghasilkan 4.

Langkah 2) Mod hasil dari langkah 1 kali 10. 4 mod 10 memberi kita 4 lagi.

Langkah 3) Ikuti langkah 3 dari iterasi sebelumnya.

Seperti yang bisa kita lihat, daftarnya sekarang diurutkan dalam urutan menaik. Iterasi terakhir telah selesai, dan proses penyortiran kini telah selesai.

Pseudocode Algoritma Radix Sort

Berikut adalah pseudo-code untuk Algoritma Radix Sort

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the j^th place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the j^thplace
   arr = sorted elements

C++ Program untuk Mengimplementasikan Radix Sort

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Keluaran:

162 248 415 623 835

Python Program Algoritma Pengurutan Radix

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Keluaran:

[162,248,415,623,835]

Analisis kompleksitas Radix Sort

Ada dua jenis kompleksitas yang perlu dipertimbangkan, kompleksitas ruang dan kompleksitas waktu.

Kompleksitas ruang: O(n+b) di mana n adalah ukuran array dan b adalah basis yang dipertimbangkan.
Kompleksitas waktu: O(d*(n+b)) di mana d adalah jumlah digit elemen terbesar dalam array.

Kompleksitas Ruang dari Urutan Radix

Dua fitur yang perlu difokuskan pada kompleksitas ruang

Jumlah elemen dalam array, n.
Dasar untuk merepresentasikan elemen, b.

Terkadang basis ini bisa lebih besar dari ukuran array.

Kompleksitas keseluruhannya adalah O(n+b).

Properti elemen berikut dalam daftar dapat membuat ruang pengurutan radix tidak efisien:

Elemen dengan jumlah digit yang banyak.
Basis elemennya besar, seperti bilangan 64-bit.

Kompleksitas Waktu dari Urutan Radix

Anda dapat menggunakan pengurutan penghitungan sebagai subrutin, karena setiap iterasi akan memakan waktue HAI(n+b) waktu. Jika ada d iterasi, total waktu berjalan menjadi HAI(d*(n+b)). Di sini, “O” berarti fungsi kompleksitas.

Linearitas Sortir Radix

Radix Sort adalah linier ketika

d adalah konstan, dimana d adalah banyaknya digit elemen terbesar.
b tidak lebih besar dibandingkan dengan n.

Perbandingan Radix Sort dengan algoritma komparatif lainnya

Seperti yang telah kita lihat, kompleksitas sort Radix didasarkan pada ukuran kata atau angka. Ia akan memiliki kompleksitas yang sama untuk kasus rata-rata dan kasus terbaik. Yaitu O(d*(n+b)). Ia juga berbeda menurut teknik sorting yang Anda gunakan di tengah. Misalnya, Anda dapat menggunakan counting sort atau quick sort untuk algoritma sorting menengah di dalam sort Radix.

Penerapan Algoritma Radix Sort

Aplikasi Penting Radix Sort adalah:

Radix Sort dapat digunakan sebagai algoritma pencarian lokasi yang menggunakan rentang nilai yang besar.
Ini digunakan dalam membangun array sufiks dalam algoritma DC3.
Ini digunakan dalam mesin akses acak berurutan yang ada di komputer biasa di mana catatan dikunci.

Anda mungkin ingin: