Anak Males -Dalam artikel ini, kami akan menjelajahi algoritma radix sort dan memberikan gambaran tentang bagaimana mengimplementasikannya menggunakan bahasa pemrograman C++ Pada Radix Sort.
Radix sort adalah algoritma pengurutan non-banding yang efisien, terutama ketika digunakan untuk mengurutkan angka.
Ia bekerja dengan membagi angka-angka menjadi digit-digit individu dan mengurutkannya berdasarkan digit tersebut, mulai dari digit terendah hingga digit tertinggi.
Dalam proses ini, radix sort memanfaatkan sifat-sifat dasar bilangan desimal, yaitu bahwa digit-digit di posisi yang lebih tinggi secara intrinsik memiliki nilai yang lebih tinggi.
Salah satu keuntungan utama radix sort adalah bahwa ia dapat mengurutkan angka dengan jumlah digit yang sama dalam waktu yang konstan, tidak tergantung pada jumlah elemen yang diurutkan.
Hal ini menjadikannya algoritma pengurutan yang efisien untuk digunakan dalam situasi di mana jumlah elemen data sangat besar.
Dalam implementasi radix sort menggunakan C++, kita perlu memahami konsep dasar seperti konversi digit dan penggunaan struktur data seperti array dan queue.
Baca : Latihan C++ #43: Membuat Selection Sort
Kami akan membahas langkah-langkah umum yang terlibat dalam algoritma radix sort, termasuk bagaimana membagi angka menjadi digit-digit individu, mengumpulkan mereka dalam antrian (queue), dan menggabungkan digit-digit untuk membentuk urutan akhir.
Selain itu, artikel ini juga akan memberikan contoh kode C++ yang sederhana namun jelas untuk membantu Anda memahami implementasi radix sort.
Kami akan menjelaskan bagaimana mengatur array input, menulis fungsi-fungsi bantu, dan menjalankan algoritma radix sort untuk menghasilkan urutan yang benar.
Dengan demikian, bacaan ini akan memberikan pemahaman yang baik tentang algoritma radix sort dan bagaimana mengimplementasikannya menggunakan bahasa pemrograman C++.
Mari kita mulai menjelajahi keajaiban pengurutan cepat yang dapat diberikan oleh radix sort!
Apa itu Radix Sort ?
Radix sort adalah sebuah algoritma pengurutan non-banding yang efisien, terutama digunakan untuk mengurutkan angka atau data yang memiliki struktur digit.
Algoritma ini berdasarkan pada konsep membagi data menjadi digit-digit individu dan mengurutkannya berdasarkan nilai digit tersebut.
Prinsip dasar radix sort adalah mengurutkan data berdasarkan digit terendah (digit paling kanan) hingga digit tertinggi (digit paling kiri).
Pada setiap iterasi, digit-digit dari data diurutkan secara parsial, dan proses ini diulangi hingga seluruh digit telah diperiksa.
Baca : Latihan C++ #44: Membuat Heap Sort
Biasanya, digit-digit ini diurutkan menggunakan algoritma pengurutan stabil, seperti counting sort atau bucket sort.
Radix sort memanfaatkan sifat dasar bilangan desimal, yaitu bahwa digit-digit di posisi yang lebih tinggi secara intrinsik memiliki nilai yang lebih tinggi.
Dengan demikian, dengan mengurutkan digit-digit secara bertahap dari digit terendah ke digit tertinggi, kita dapat menghasilkan urutan akhir yang benar.
Keuntungan utama radix sort adalah bahwa ia dapat mengurutkan angka dengan jumlah digit yang sama dalam waktu yang konstan, tidak tergantung pada jumlah elemen yang diurutkan.
Ini menjadikannya algoritma pengurutan yang efisien untuk digunakan dalam situasi di mana jumlah elemen data sangat besar.
Baca : Latihan C++ #42: Membuat Insertion Sort
Namun, penting untuk diingat bahwa radix sort memiliki beberapa keterbatasan. Pertama, algoritma ini hanya berlaku untuk data yang memiliki struktur digit, seperti angka.
Selain itu, radix sort membutuhkan ruang memori tambahan untuk menyimpan antrian sementara, yang dapat menjadi masalah jika memori terbatas.
Dalam implementasinya menggunakan bahasa pemrograman, radix sort melibatkan konversi digit, penggunaan struktur data seperti array dan queue, serta penggunaan algoritma pengurutan stabil.
Dengan pemahaman yang baik tentang konsep dan implementasi radix sort, Anda dapat memanfaatkannya untuk meningkatkan kecepatan dan efisiensi program pengurutan Anda.
Program C++Radix Sort
Baca : Latihan C++ #40: Membuat Merge Sort
Berikut adalah contoh program C++ untuk implementasi algoritma radix sort dengan inputan dari pengguna:
#include <iostream>
#include <vector>
// Fungsi untuk mendapatkan digit pada posisi tertentu
int getDigit(int num, int pos) {
int divisor = 1;
for (int i = 0; i < pos; i++) {
divisor *= 10;
}
return (num / divisor) % 10;
}
// Fungsi untuk mendapatkan digit terbesar pada array
int getMaxDigit(std::vector<int>& arr) {
int maxDigit = 0;
for (int num : arr) {
int digitCount = 1;
while (num / 10 != 0) {
digitCount++;
num /= 10;
}
if (digitCount > maxDigit) {
maxDigit = digitCount;
}
}
return maxDigit;
}
// Fungsi untuk mengurutkan array menggunakan algoritma radix sort
void radixSort(std::vector<int>& arr) {
int maxDigit = getMaxDigit(arr);
int radix = 10;
for (int i = 0; i < maxDigit; i++) {
std::vector<std::vector<int>> buckets(radix);
for (int num : arr) {
int digit = getDigit(num, i);
buckets[digit].push_back(num);
}
int index = 0;
for (auto& bucket : buckets) {
for (int num : bucket) {
arr[index++] = num;
}
bucket.clear();
}
}
}
int main() {
int n;
std::cout << "Masukkan jumlah elemen: ";
std::cin >> n;
std::cout << "Masukkan elemen-elemen array:\n";
std::vector<int> arr(n);
for (int i = 0; i < n; i++) {
std::cin >> arr[i];
}
radixSort(arr);
std::cout << "Array setelah diurutkan menggunakan Radix Sort: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Berikut adalah penjelasan baris per baris dari kode yang telah disediakan:
#include <iostream>
#include <vector>
Baris ini mengimpor pustaka <iostream> dan <vector>, yang dibutuhkan untuk menggunakan fungsi input/output standar dan struktur data vektor pada C++.
int getDigit(int num, int pos) {
int divisor = 1;
for (int i = 0; i < pos; i++) {
divisor *= 10;
}
return (num / divisor) % 10;
}
Ini adalah fungsi getDigit, yang mengambil angka num dan posisi digit pos dan mengembalikan digit pada posisi tersebut. Fungsi ini melakukan operasi matematika untuk memisahkan digit yang diinginkan dari angka.
Baca : Latihan C++ #39 : Membuat Quick Sort
int getMaxDigit(std::vector<int>& arr) {
int maxDigit = 0;
for (int num : arr) {
int digitCount = 1;
while (num / 10 != 0) {
digitCount++;
num /= 10;
}
if (digitCount > maxDigit) {
maxDigit = digitCount;
}
}
return maxDigit;
}
Ini adalah fungsi getMaxDigit, yang mengambil referensi ke vektor arr dan mengembalikan jumlah digit terbesar dalam vektor tersebut.
Fungsi ini menggunakan perulangan untuk menghitung jumlah digit dalam setiap angka dalam vektor dan kemudian membandingkannya dengan maxDigit saat ini untuk mencari jumlah digit terbesar.
void radixSort(std::vector<int>& arr) {
int maxDigit = getMaxDigit(arr);
int radix = 10;
for (int i = 0; i < maxDigit; i++) {
std::vector<std::vector<int>> buckets(radix);
for (int num : arr) {
int digit = getDigit(num, i);
buckets[digit].push_back(num);
}
int index = 0;
for (auto& bucket : buckets) {
for (int num : bucket) {
arr[index++] = num;
}
bucket.clear();
}
}
}
Ini adalah fungsi radixSort, yang mengambil referensi ke vektor arr dan mengurutkan elemen-elemennya menggunakan algoritma radix sort.
Baca : Latihan C++ #38 : Membuat Bubble Sort
Fungsi ini menggunakan dua perulangan: perulangan luar untuk mengiterasi melalui setiap digit dalam angka, dan perulangan dalam untuk membagi angka-angka ke dalam “ember” berdasarkan digit pada posisi saat ini.
Setiap angka ditempatkan ke dalam ember yang sesuai dengan digit pada posisi saat ini. Setelah itu, angka-angka dikumpulkan kembali ke dalam vektor arr dalam urutan yang benar.
int main() {
int n;
std::cout << "Masukkan jumlah elemen: ";
std::cin >> n;
std::cout << "Masukkan elemen-elemen array:\n";
std::vector<int> arr(n);
for (int i = 0; i < n; i++) {
std::cin >> arr[i];
}
radixSort(arr);
std::cout << "Array setelah diurutkan menggunakan Radix Sort: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Ini adalah fungsi main yang merupakan titik masuk utama program. Di sini, pengguna diminta untuk memasukkan jumlah elemen yang akan diurutkan.
Kemudian, pengguna diminta untuk memasukkan elemen-elemen array satu per satu.
Setelah itu, fungsi radixSort dipanggil untuk mengurutkan array. Setelah array diurutkan, elemen-elemen array yang telah diurutkan dicetak ke layar.
Program kemudian mengembalikan 0 untuk menandakan bahwa program telah berakhir dengan sukses.
Output Program C++ Radix Sort
Baca : Latihan C++ # 49: Membuat Shell Sort
Berikut adalah contoh output program jika pengguna memasukkan jumlah elemen 6 dan elemen-elemen array ialah 42, 9, 31, 77, 5, dan 12:
Masukkan jumlah elemen: 6
Masukkan elemen-elemen array:
42
9
31
77
5
12
Array setelah diurutkan menggunakan Radix Sort: 5 9 12 31 42 77
Array hasil setelah diurutkan menggunakan algoritma Radix Sort adalah 5, 9, 12, 31, 42, dan 77.
Penutup
Kita telah menjelajahi algoritma radix sort dan memberikan gambaran tentang bagaimana mengimplementasikannya menggunakan bahasa pemrograman C++.
Radix sort adalah algoritma pengurutan yang efisien, terutama ketika digunakan untuk mengurutkan angka, karena memanfaatkan sifat dasar bilangan desimal.
Dalam artikel ini, kita telah mempelajari langkah-langkah umum yang terlibat dalam radix sort, mulai dari membagi angka menjadi digit-digit individu hingga mengumpulkan digit-digit tersebut dalam antrian dan menggabungkannya untuk membentuk urutan akhir.
Melalui contoh kode C++ yang disediakan, kita dapat melihat bagaimana mengatur array input, menulis fungsi-fungsi bantu, dan menjalankan algoritma radix sort dengan sukses.
Radix sort adalah algoritma yang sangat berguna dalam pengurutan data dengan jumlah digit yang sama, terutama dalam situasi di mana jumlah elemen data sangat besar.
Baca : Latihan C++ #48: Bilangan Ganjil & Genap
Dengan memahami konsep dan implementasi radix sort, Anda dapat meningkatkan kecepatan dan efisiensi program pengurutan Anda.
Namun, perlu diingat bahwa radix sort memiliki keterbatasan, seperti membutuhkan ruang memori tambahan untuk menyimpan antrian sementara dan hanya cocok untuk mengurutkan angka.
Oleh karena itu, sebelum memutuskan menggunakan radix sort, penting untuk mempertimbangkan jenis data yang akan diurutkan dan membandingkannya dengan algoritma pengurutan lainnya.
Dengan terus mempelajari dan mempraktikkan algoritma seperti radix sort, Anda dapat mengembangkan keterampilan pemrograman Anda dan meningkatkan efisiensi program Anda.
Baca : Latihan C++ #47: Menemukan Nilai ASCII
Teruslah berlatih dan eksplorasi dengan algoritma pengurutan lainnya untuk memperluas pengetahuan Anda dalam dunia pemrograman.
Semoga artikel ini memberikan pemahaman yang baik tentang radix sort dan mendorong Anda untuk menjelajahi lebih jauh tentang algoritma pengurutan yang menarik ini.
Terima kasih telah membaca, dan selamat mencoba menggunakan radix sort dalam proyek-proyek Anda!