Latihan C++ # 51: Membuat Tree Sort

Anak Males – Dalam dunia pemrograman, algoritma pengurutan adalah salah satu topik yang sangat penting dan relevan.

Algoritma pengurutan memungkinkan kita untuk menyusun kumpulan data menjadi urutan tertentu, baik secara menaik (ascending) maupun menurun (descending).

Salah satu algoritma pengurutan yang menarik dan unik adalah “Tree Sort” atau pengurutan dengan menggunakan pohon biner.

Dalam artikel ini, kita akan membahas tentang “Program C++ Tree Sort”. Tree Sort adalah metode pengurutan yang memanfaatkan struktur pohon biner untuk menyusun data secara terurut.

Konsep pohon biner memungkinkan kita untuk membagi data menjadi dua bagian berdasarkan relasi urutan, sehingga secara rekursif membentuk pohon biner yang terurut.

Metode ini menawarkan efisiensi waktu yang baik dan merupakan pilihan yang menarik untuk pengurutan data dalam program C++.

Mari kita eksplorasi lebih jauh tentang bagaimana Tree Sort bekerja, cara mengimplementasikannya dalam bahasa pemrograman C++, dan apa kelebihan serta kekurangannya.

Dalam artikel ini, kami akan memberikan penjelasan langkah demi langkah tentang algoritma Tree Sort, menyajikan contoh program C++ yang dapat langsung dijalankan, serta membahas tentang kompleksitas algoritma dan situasi terbaik untuk menggunakan Tree Sort.

Tanpa berlama-lama lagi, mari kita memahami bagaimana Tree Sort bekerja dan mengapa algoritma ini menjadi salah satu pilihan menarik untuk pengurutan data dalam bahasa pemrograman C++.

Baca : Latihan C++ # 50: Membuat Radix Sort

Program C++Tree Sort

berikut adalah program C++ untuk melakukan Tree Sort dengan menggunakan inputan dari pengguna:

#include <iostream>

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

void insert(TreeNode*& root, int data) {
    if (root == nullptr) {
        root = new TreeNode(data);
        return;
    }

    if (data < root->data) {
        insert(root->left, data);
    } else {
        insert(root->right, data);
    }
}

void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

void deleteTree(TreeNode*& root) {
    if (root == nullptr) {
        return;
    }

    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
    root = nullptr;
}

void treeSort(int arr[], int n) {
    TreeNode* root = nullptr;

    for (int i = 0; i < n; i++) {
        insert(root, arr[i]);
    }

    inorderTraversal(root);
    std::cout << std::endl;

    deleteTree(root);
}

int main() {
    int n;
    std::cout << "Masukkan jumlah elemen array: ";
    std::cin >> n;

    int* arr = new int[n];

    std::cout << "Masukkan elemen array:\n";
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    std::cout << "Array sebelum diurutkan: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }

    std::cout << std::endl << "Array setelah diurutkan: ";
    treeSort(arr, n);

    delete[] arr;
    return 0;
}

berikut adalah penjelasan baris per baris dari program di atas:

Baca : Latihan C++ # 49: Membuat Shell Sort

#include <iostream>

Baris 1: Ini adalah preprocessor directive untuk mengimpor pustaka input-output standar C++ yang diperlukan untuk operasi masukan/keluaran.

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

Baris 3-8: Mendefinisikan struktur data TreeNode yang merepresentasikan node dalam pohon biner. Setiap node memiliki tiga anggota: data untuk menyimpan nilai node, left untuk menunjukkan anak kiri, dan right untuk menunjukkan anak kanan.

Di sini juga didefinisikan konstruktor untuk node yang akan menginisialisasi nilai data dan menetapkan pointer left dan right ke nullptr.

void insert(TreeNode*& root, int data) {
    if (root == nullptr) {
        root = new TreeNode(data);
        return;
    }

    if (data < root->data) {
        insert(root->left, data);
    } else {
        insert(root->right, data);
    }
}

Baris 10-19: Ini adalah fungsi insert yang bertanggung jawab untuk menyisipkan elemen baru ke dalam pohon biner secara rekursif.

Fungsi ini mengambil dua argumen: root yang merupakan referensi ke pointer TreeNode yang menunjuk ke akar pohon biner, dan data yang merupakan nilai yang ingin dimasukkan.

Fungsi ini mencari tempat yang tepat untuk menyisipkan data sesuai dengan aturan pohon biner, yaitu data yang lebih kecil akan diletakkan di sebelah kiri, dan data yang lebih besar atau sama akan diletakkan di sebelah kanan.

void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

Baris 21-28: Ini adalah fungsi inorderTraversal yang melakukan traversal inorder pada pohon biner. Fungsi ini mengambil argumen root yang merupakan pointer ke node saat ini dalam pohon biner.

Fungsi ini akan mencetak elemen dari pohon biner dalam urutan terurut (urutan menaik).

void deleteTree(TreeNode*& root) {
    if (root == nullptr) {
        return;
    }

    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
    root = nullptr;
}

Baris 30-38: Ini adalah fungsi deleteTree yang bertanggung jawab untuk menghapus seluruh pohon biner secara rekursif. Fungsi ini mengambil argumen root yang merupakan referensi ke pointer TreeNode yang menunjuk ke akar pohon biner.

Baca : Latihan C++ #44: Membuat Heap Sort

Fungsi ini akan menghapus semua node dalam pohon biner, melepaskan memori yang dialokasikan, dan mengatur pointer root menjadi nullptr setelah penghapusan selesai.

void treeSort(int arr[], int n) {
    TreeNode* root = nullptr;

    for (int i = 0; i < n; i++) {
        insert(root, arr[i]);
    }

    inorderTraversal(root);
    std::cout << std::endl;

    deleteTree(root);
}

Baris 40-50: Ini adalah fungsi treeSort yang melakukan pengurutan menggunakan metode Tree Sort. Fungsi ini mengambil dua argumen: arr yang merupakan array integer yang akan diurutkan dan n yang merupakan jumlah elemen dalam array.

Fungsi ini membuat pohon biner dari array menggunakan fungsi insert, melakukan traversal inorder untuk mencetak array yang sudah terurut, dan akhirnya menghapus seluruh pohon biner dengan fungsi deleteTree.

int main() {
    int n;
    std::cout << "Masukkan jumlah elemen array: ";
    std::cin >> n;

    int* arr = new int[n];

    std::cout << "Masukkan elemen array:\n";
    for (int i = 0; i < n; i++) {
        std::cin >> arr[i];
    }

    std::cout << "Array sebelum diurutkan: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }

    std::cout << std::endl << "Array setelah diurutkan: ";
    treeSort(arr, n);

    delete[] arr;
    return 0;
}

Baris 52-69: Ini adalah fungsi main, titik masuk utama program. Fungsi ini meminta pengguna untuk memasukkan jumlah elemen array dan elemen-elemen array itu sendiri menggunakan std::cin. Kemudian, array tersebut akan diurutkan menggunakan fungsi treeSort.

Setelah pengurutan selesai, memori yang dialokasikan untuk array akan dibebaskan dengan delete[] arr sebelum program selesai.

Baca : Latihan C++ #43: Membuat Selection Sort

Output Program C++ Tree Sort

Berikut adalah output dari program C++ Tree Sort yang telah dibahas sebelumnya:

Masukkan jumlah elemen array: 7
Masukkan elemen array:
10 4 8 12 5 15 6
Array sebelum diurutkan: 10 4 8 12 5 15 6 
Array setelah diurutkan: 4 5 6 8 10 12 15 

Output di atas menunjukkan bahwa program meminta pengguna untuk memasukkan jumlah elemen dalam array, diikuti oleh elemen-elemen array tersebut.

Setelah itu, program akan mencetak array sebelum diurutkan, dan hasil pengurutan menggunakan Tree Sort. Hasil akhir menunjukkan bahwa array telah diurutkan secara ascending menggunakan Tree Sort.

Baca : Latihan C++ #42: Membuat Insertion Sort

Penutup

Dalam artikel ini, kita telah menjelajahi metode pengurutan yang menarik dan unik, yaitu “Tree Sort” dalam bahasa pemrograman C++.

Tree Sort menggunakan struktur pohon biner untuk menyusun data secara terurut, yang memberikan efisiensi waktu yang baik dalam proses pengurutan.

Kita telah memahami langkah-langkah untuk mengimplementasikan Tree Sort dalam bahasa pemrograman C++ dan melihat contoh program yang dapat langsung dijalankan.

Penggunaan pohon biner memungkinkan pengurutan data dengan memanfaatkan sifat relasi urutan yang terbentuk secara rekursif dalam pohon tersebut.

Tree Sort memiliki beberapa kelebihan, termasuk kinerja yang baik untuk data yang sudah hampir terurut atau memiliki distribusi yang hampir merata.

Namun, seperti halnya dengan algoritma pengurutan lainnya, Tree Sort juga memiliki kelemahan, terutama dalam hal kompleksitas ruang yang bisa menjadi lebih besar daripada metode pengurutan lainnya.

Baca : Latihan C++ #40: Membuat Merge Sort

Sebagai seorang pengembang, penting untuk memahami berbagai algoritma pengurutan dan memilih yang tepat sesuai dengan kebutuhan dan karakteristik data yang akan diurutkan.

Tree Sort dapat menjadi pilihan yang menarik terutama jika data memiliki distribusi yang cukup merata dan kita ingin menggali lebih dalam tentang konsep pohon biner.

Sekarang, dengan pemahaman lebih lanjut tentang Tree Sort, mari kita terus eksplorasi dan memperkaya pengetahuan kita tentang algoritma pengurutan lainnya.

Dengan menguasai berbagai teknik pengurutan, kita dapat mengoptimalkan kinerja program dan memberikan solusi efisien untuk berbagai masalah dalam dunia pemrograman.

Semoga artikel ini telah memberikan wawasan yang bermanfaat dan membantu Anda dalam memahami konsep Tree Sort dalam bahasa pemrograman C++.

Terima kasih telah membaca, dan selamat berpetualang dalam dunia algoritma dan pemrograman!