Latihan C++ #39 : Membuat Quick Sort

Anak Males – Artikel ini akan memberikan petunjuk untuk membuat sebuah kode program dengan bahasa C++ yang menerapkan teknik sorting quick sort.

Quick sort adalah metode pengurutan yang efisien dan cepat, yang menggunakan konsep pembagian dan penaklukan.

Ide dasarnya adalah untuk memilih elemen sentral dari daftar yang akan diurutkan (disebut pivot), kemudian menempatkan elemen lain ke dalam dua daftar terpisah, yaitu elemen yang lebih kecil dari pivot dan elemen yang lebih besar dari pivot.

Baca : Latihan C++ #38 : Bubble Sort

Ini kemudian dilakukan secara rekursif pada kedua daftar terpisah. Dengan cara ini, daftar akan terurut dari kecil ke besar (atau sebaliknya, tergantung pada implementasi yang digunakan).

Dalam tutorial ini, kita akan belajar bagaimana menulis program C++ yang menggunakan metode pengurutan quick sort.

Program C++ Membuat Quick Sort

Ini adalah contoh kode C++ yang menunjukkan cara menyortir elemen dalam suatu array menggunakan algoritma quicksort dan menerima input dari pengguna:

#include <iostream>
#include <algorithm>

void quicksort(int *arr, int kiri, int kanan) {
    int i = kiri, j = kanan;
    int tmp;
    int pivot = arr[(kiri + kanan) / 2];

    /* pembagian */
    while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
        }
    }

    /* rekursi */
    if (kiri < j)
        quicksort(arr, kiri, j);
    if (i < kanan)
        quicksort(arr, i, kanan);
}

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

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

    quicksort(arr, 0, n-1);

    std::cout << "Array yang terurut: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";

    delete[] arr;
    return 0;
}

Berikut adalah penjelasan lebih detail tentang masing-masing bagian dari kode program di atas:

#include <iostream>
#include <algorithm>

Baris ini menyertakan header library iostream dan algorithm

void quicksort(int *arr, int kiri, int kanan) {
    int i = kiri, j = kanan;
    int tmp;
    int pivot = arr[(kiri + kanan) / 2];

Ini adalah fungsi quicksort yang mengambil sebuah array, elemen pertama dan terakhir dari array sebagai parameter.

Baca : Latihan C++ #37 : Persegi Panjang Bintang

Dalam fungsi ini, itu mendeklarasikan dan menginisialisasi tiga variabel: i, j, tmp dan pivot sebagai elemen tengah dari array.

    /* pembagian */
    while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
        }
    }

Blok kode ini adalah tahap pembagian dari algoritma quicksort. ia memulai sebuah perulangan while yang akan berlanjut sampai i lebih besar dari j.

Dalam perulangan while, ia memulai dua perulangan while yang akan berlanjut sampai elemen di indeks i lebih besar dari atau sama dengan pivot dan elemen di indeks j lebih kecil dari atau sama dengan pivot masing-masing. itu akan menukar elemen dari indeks i dan j jika i kurang dari atau sama dengan j.

    /* rekursi */
    if (kiri < j)
        quicksort(arr, kiri, j);
    if (i < kanan)
        quicksort(arr, i, kanan);
    }

Blok kode ini adalah tahap rekursi dari algoritma quicksort. itu memulai dua pernyataan if yang akan dieksekusi jika kiri kurang dari j dan i kurang dari kanan masing-masing. Fungsi quicksort dipanggil secara rekursif pada subarray dari kiri ke j dan i ke kanan masing-masing.

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

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

    quicksort(arr, 0, n-1);

    std::cout << "Array yang terurut: ";
    for (int i = 0; i < n; i++)
        std::cout << arr[i] << " ";

Ini adalah perulangan yang digunakan untuk menampilkan elemen dari array yang sudah diurutkan.

delete[] arr;
return 0;
}

Baris ini digunakan untuk menghapus memori yang digunakan oleh array yang digunakan dan mengembalikan nilai 0 dari fungsi utama yang menandakan bahwa program telah berhasil dieksekusi.

Baca : Latihan C++ #36 : Belah Ketupat Bintang

Output Program C++ Membuat  Quick Sort

Output dari program diatas akan tergantung pada input yang diberikan oleh user. Namun, contoh output dari program diatas jika user memasukkan input sebagai berikut:

Masukkan jumlah elemen: 5
Masukkan elemen: 3 1 2 5 4
Array yang terurut: 1 2 3 4 5

Penutup

Sekian untuk tutorial C++ kali ini, sampai jumpa di tutorial C++ lainnya.