Algoritma Sortir Radix dalam Struktur Data

Apa itu Algoritma Radix Sort?

Radix Sort adalah algoritma pengurutan non-komparatif. Cara kerjanya adalah dengan mengelompokkanping Angka-angka individual dari elemen yang akan diurutkan. Kemudian, teknik pengurutan yang stabil digunakan untuk mengatur elemen berdasarkan basisnya. Ini adalah algoritma pengurutan linier.

Proses penyortiran melibatkan properti berikut:

• Menemukan elemen maksimum dan mendapatkan jumlah digit dari elemen tersebut. Ini memberikan jumlah iterasi yang dilakukan oleh proses pengurutan.
• Grouping Angka-angka individual dari elemen-elemen pada posisi signifikan yang sama di setiap iterasi.
• Kelompok ituping Proses dimulai dari angka yang paling tidak signifikan dan berakhir pada angka yang paling signifikan.
• Mengurutkan elemen berdasarkan angka pada posisi penting tersebut.
• Mempertahankan urutan relatif elemen yang memiliki nilai kunci yang sama. Sifat inilah yang menjadikan Radix Sort sebagai algoritma pengurutan yang stabil.

Iterasi terakhir mengembalikan daftar yang sudah sepenuhnya terurut.

Cara Kerja Algoritma Radix Sort

Daftar bilangan bulat yang akan diurutkan

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

Berikut adalah langkah-langkah untuk melakukan proses Radix Sort:

Langkah 1) Identifikasi elemen maksimum dalam daftar tersebut. Di sini, nilainya adalah 835.

Langkah 2) Hitung jumlah digitnya. 835 memiliki 3 digit, jadi jumlah iterasinya adalah 3.

Langkah 3) Tentukan basisnya. Karena ini desimal, basisnya adalah 10.

Langkah 4) Mulai iterasi pertama.

a) Iterasi pertama

Mengurutkan berdasarkan digit terakhir

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

Langkah 1) Lakukan operasi modulo pada bilangan bulat dengan 10 untuk mendapatkan angka satuan dari elemen-elemennya. Misalnya, 623 mod 10 menghasilkan 3, dan 248 mod 10 menghasilkan 8.

Langkah 2) Gunakan algoritma pengurutan hitungan (counting sort) atau pengurutan stabil lainnya untuk menyusun bilangan bulat berdasarkan angka terkecilnya. Dari gambar, 248 masuk ke dalam kelompok ke-8, 623 masuk ke dalam kelompok ke-3, dan seterusnya.

Setelah iterasi pertama, daftarnya sekarang terlihat seperti ini.

Daftar setelah iterasi pertama

Daftar ini belum diurutkan dan memerlukan iterasi lebih lanjut.

b) Iterasi kedua

Mengurutkan berdasarkan angka pada tempat puluhan

Pada iterasi ini, kita mempertimbangkan angka pada posisi puluhan untuk proses pengurutan.

Langkah 1) Bagilah bilangan bulat dengan 10. Misalnya, 248 dibagi 10 hasilnya 24.

Langkah 2) Modus operandi dari Langkah 1 dengan 10. 24 mod 10 hasilnya 4.

Langkah 3) Ikuti Langkah 2 dari iterasi sebelumnya.

Setelah iterasi kedua, daftar tersebut sekarang terlihat seperti ini:

Daftar setelah iterasi kedua

Daftar ini masih belum diurutkan sepenuhnya karena belum dalam urutan menaik.

c) Iterasi ketiga

Pengurutan berdasarkan angka pada tempat ratusan.

Untuk iterasi terakhir, kita ingin mendapatkan angka yang paling signifikan. Dalam hal ini, angka tersebut adalah angka ratusan untuk setiap bilangan bulat dalam daftar.

Langkah 1) Bagilah bilangan bulat dengan 100. Misalnya, 415 dibagi 100 hasilnya 4.

Langkah 2) Moduskan hasil dari Langkah 1 dengan 10. 4 mod 10 hasilnya 4.

Langkah 3) Ikuti Langkah 3 dari iterasi sebelumnya.

Daftar setelah iterasi ketiga

Daftar sekarang diurutkan dalam urutan menaik. Iterasi terakhir telah selesai, dan proses pengurutan telah berakhir.

Pseudocode Algoritma Radix Sort

Berikut adalah pseudocode 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 jth 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 in the jth place
    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 integer
    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 in 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

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

Keluaran:

[162, 248, 415, 623, 835]

Analisis Kompleksitas Pengurutan Radix

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 dari elemen terbesar dalam array.

Kompleksitas Ruang dari Urutan Radix

Dua fitur yang perlu difokuskan untuk kompleksitas ruang:

• Jumlah elemen dalam array, n.
• Basis yang digunakan untuk mewakili elemen-elemen tersebut, b.

Terkadang basis ini bisa lebih besar dari ukuran array. Dengan demikian, kompleksitas keseluruhannya adalah O(n + b).

Sifat-sifat elemen dalam daftar berikut dapat membuat Radix Sort tidak efisien dalam penggunaan ruang:

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

Kompleksitas Waktu dari Urutan Radix

Dengan menggunakan algoritma pengurutan hitungan (counting sort) sebagai subrutin, setiap iterasi membutuhkan waktu... O(n + b) waktu. Jika ada d iterasi, total waktu berjalan menjadi O(d * (n + b))Di sini, “O” menunjukkan fungsi kompleksitas.

Linearitas Sortir Radix

Radix Sort bersifat linear ketika:

• d adalah konstan, dimana d adalah banyaknya digit elemen terbesar.
• b tidak jauh lebih besar daripada n.

Perbandingan Radix Sort dengan Metode Pengurutan Lainnya Algorithms

Kompleksitas Radix Sort bergantung pada ukuran angka. Kasus terbaik dan kasus rata-rata keduanya adalah O(d * (n + b)). Kinerja bervariasi tergantung pada pengurutan bagian dalam — pengurutan hitungan adalah standar, tetapi pengurutan stabil apa pun dapat digunakan.

Penerapan Algoritma Radix Sort

Aplikasi penting dari Radix Sort adalah:

• Radix Sort dapat digunakan sebagai algoritma pencarian lokasi ketika rentang nilai yang terlibat sangat besar.
• Ini digunakan untuk membangun larik akhiran dalam algoritma DC3.
• Ini digunakan dalam mesin akses acak sekuensial di mana catatan dikunci oleh pengidentifikasi dengan lebar tetap.

Pertanyaan Umum Demo Slot