Kode Program C++: Mengurutkan Angka (Algoritma Merge Sort)

Latihan kode program C++ kali ini akan membahas cara mengurutkan angka menggunakan algoritma merge sort. Algoritma sorting banyak dipakai dalam pembahasan materi algoritma dasar di kampus-kampus IT.

Soal Mengurutkan Angka dengan Algoritma Merge Sort

Buatlah kode program C++ untuk mengurutkan angka menggunakan algoritma merge sort. Program meminta 1 nilai input untuk menentukan jumlah angka yang akan diurutkan, kemudian user memasukkan angka tersebut satu per satu. Setelah itu program menampilkan hasil urutan dari nilai terkecil ke terbesar (ascending).

Berikut contoh tampilan akhir yang diinginkan (1):

##  Program C++ Mengurutkan Angka (Merge Sort) ##
=================================================

Input jumlah element array: 5

Input 5 angka (dipisah dengan enter):
Angka ke-1: 23
Angka ke-2: 76
Angka ke-3: 10
Angka ke-4: 77
Angka ke-5: 34

Array setelah diurutkan: 10 23 34 76 77

Berikut contoh tampilan akhir yang diinginkan (2):

##  Program C++ Mengurutkan Angka (Merge Sort) ##
=================================================

Input jumlah element array: 7

Input 7 angka (dipisah dengan enter):
Angka ke-1: 123
Angka ke-2: 567
Angka ke-3: 897
Angka ke-4: 233
Angka ke-5: 664
Angka ke-6: 726
Angka ke-7: 176

Array setelah diurutkan: 123 176 233 567 664 726 897

Silahkan coba sebentar membuat kode program ini.

Tips Membuat Kode Program Mengurutkan Angka

Soal ini melatih pemahaman terkait array dan algoritma sorting. Berikut tutorial pendahuluan yang bisa diikuti:

Setiap angka yang akan diurutkan perlu di simpan ke dalam sebuah array. Array inilah yang akan kita proses menggunakan algoritma merge sort.

# Pengertian Algoritma Merge Sort

Merge sort adalah algoritma pengurutan yang bekerja dengan cara membagi array menjadi dua bagian yang sama besar, kemudian mengurutkan setiap bagian tersebut secara rekursif. Setelah itu, kedua bagian yang sudah terurut digabung menjadi satu array.

Algoritma merge sort memiliki langkah-langkah sebagai berikut:

Bagi array menjadi dua bagian yang sama besar. Proses ini dilakukan secara rekursif sampai array hanya memiliki satu elemen.
Urutkan setiap bagian secara rekursif.
Gabungkan kedua bagian yang sudah terurut. Element yang lebih kecil akan diletakkan di bagian depan, dan element yang lebih besar akan diletakkan di bagian belakang.

Ilustrasi cara kerja algoritma merge sort

Kelebihan algoritma merge sort:

Merge sort memiliki kompleksitas waktu O(n log n), yang berarti algoritma ini efisien untuk mengurutkan array berukuran besar.
Merge sort adalah algoritma yang stabil, dimana urutan element yang sama akan tetap sama setelah diurutkan.

Kekurangan algoritma merge sort:

Algoritma merge sort cukup kompleks dan agak susah dipahami.
Merge sort butuh ruang tambahan untuk menyimpan array sementara.

Secara umum, algoritma merge sort cocok digunakan untuk mengurutkan array berukuran besar.

Kode Program C++ Mengurutkan Angka dengan Algoritma Merge Sort

Berikut salah satu solusi dari soal mengurutkan angka array dengan algoritma merge sort menggunakan bahasa pemrograman C++:

#include <iostream>
using namespace std;

// Buat function dengan algoritma merge sort
void merge(int arr[], int low, int mid, int high) {
  // Buat array sementara untuk menyimpan hasil merge
  int temp[high - low + 1];

  // Indeks awal dan akhir array kiri
  int i = low;
  // Indeks awal dan akhir array kanan
  int j = mid + 1;
  // Indeks array sementara
  int k = 0;

  // Masukkan element dari array kiri dan kanan ke dalam array sementara
  while (i <= mid && j <= high) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }

  // Masukkan sisa element dari array kiri atau kanan ke array sementara
  while (i <= mid) {
    temp[k++] = arr[i++];
  }

  while (j <= high) {
    temp[k++] = arr[j++];
  }

  // Salin element-element dari array sementara ke array asli
  for (int i = low; i <= high; i++) {
    arr[i] = temp[i - low];
  }
}

void mergeSort(int arr[], int low, int high) {
  // Jika array hanya memiliki satu element, maka array itu sudah terurut
  if (low >= high) {
    return;
  }

  // Bagi array menjadi dua bagian yang sama besar
  int mid = (low + high) / 2;

  // Urutkan bagian kiri dari array
  mergeSort(arr, low, mid);

  // Urutkan bagian kanan dari array
  mergeSort(arr, mid + 1, high);

  // Gabungkan kedua bagian yang sudah terurut
  merge(arr, low, mid, high);
}

int main() {
  cout << "##  Program C++ Mengurutkan Angka (Merge Sort) ##" << endl;
  cout << "=================================================" << endl;
  cout << endl;

  int i, n;

  // Baca angka input dari user
  cout << "Input jumlah element array: ";
  cin >> n;
  cout << endl;

  int arr[n];
  cout <<  "Input "<< n << " angka (dipisah dengan enter): ";
  cout << endl;

  for(i = 0; i < n; i++){
    cout << "Angka ke-" << i+1 <<": ";
    cin >> arr[i];
  }

  // Urutkan array dengan algoritma merge sort
  mergeSort(arr, 0, n-1);

  // Tampilan hasil pengurutan
  cout << endl;
  cout << "Array setelah diurutkan: ";
  for (i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;

  return 0;
}

Pada awal kode program di baris 5-38 terdapat deklarasi fungsi merge() untuk menggabungkan dua array yang sudah terurut. Fungsi ini menerima empat parameter, yaitu array yang akan diurutkan (arr), indeks awal (low), indeks tengah (mid), dan indeks akhir (high).

Fungsi merge() bertanggung jawab untuk menggabung dua bagian array yang sudah terurut menjadi satu array. Pertama, buat array sementara (temp) untuk menyimpan hasil merge. Kemudian gunakan tiga variabel i, j, dan k untuk melacak indeks pada array kiri, array kanan, dan array sementara.

Selama kedua indeks masih berada dalam rentang yang valid, fungsi merge() akan membandingkan element pada kedua array dan memasukkannya ke dalam array sementara sesuai urutan yang benar.

Setelah itu sisa element dari array kiri atau kanan dimasukkan ke dalam array sementara. Terakhir, element-element dari array sementara disalin kembali ke array asli menggunakan perulangan.

Kemudian di ikuti deklarasi fungsi mergeSort() di baris 40-57 untuk mengurutkan array dengan algoritma merge sort.

Fungsi mergeSort() menerima tiga parameter, yaitu array yang akan diurutkan (arr), indeks awal (low), dan indeks akhir (high). Fungsi ini merupakan implementasi rekursif dari algoritma Merge Sort.

Di awal, fungsi ini akan melakukan pemeriksaan, yakni jika indeks awal lebih besar atau sama dengan indeks akhir, maka array tersebut sudah terurut dan fungsi berhenti. Jika tidak, fungsi mergeSort() membagi array menjadi dua bagian yang sama besar dengan mencari indeks tengah (mid).

Kemudian, fungsi mergeSort() dipanggil secara rekursif untuk mengurutkan bagian kiri dan bagian kanan dari array. Setelah kedua bagian terurut, fungsi merge() dipanggil untuk menggabung kedua bagian menjadi satu array terurut.

Masuk ke dalam kode program utama, di baris 67-67 user diminta untuk menginput jumlah angka yang ingin diurutkan. Angka ini akan disimpan ke dalam variabel n.

Kode program lalu membuat array sejumlah n dengan perintah int arr[n] di baris 71. Perulangan for dipakai untuk membaca setiap data dan disimpan ke dalam variabel arr.

Algoritma merge sort dijalankan dengan memanggil fungsi mergeSort(arr, 0, n-1).

Hasilnya, variabel arr akan berisi array yang sudah terurut, untuk selanjutnya ditampilkan dengan perulangan for di baris 86-88.

Itulah bahasan kita tentang implementasi algoritma sorting merge sort dalam bahasa pemrograman C++. Algoritma ini memang lebih kompleks jika dibandingkan algoritma sorting lain seperti bubble sort dan selection sort.

Semoga latihan soal ini bisa bermanfaat.