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

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

Merge sort adalah algoritma pengurutan yang efisien dan stabil yang bekerja dengan membagi daftar menjadi dua bagian, mengurutkan setiap bagian secara rekursif, dan kemudian menggabungkan hasil yang sudah diurutkan menjadi satu daftar yang sudah diurutkan. Merge sort memiliki kompleksitas waktu rata-rata O(n log n) dan kompleksitas waktu terburuk O(n^2), di mana n adalah jumlah elemen dalam daftar.

Contoh

Misalkan kita memiliki daftar bilangan bulat berikut yang ingin kita urutkan:

[5, 3, 1, 2, 4]

Kita dapat menggunakan algoritma merge sort untuk mengurutkan daftar bilangan bulat tersebut sebagai berikut:

1. Bagi daftar menjadi dua bagian:

[5, 3]
[1, 2, 4]

2. Urutkan setiap bagian secara rekursif:

[3, 5]
[1, 2, 4]

3. Gabungkan hasil yang sudah diurutkan menjadi satu daftar yang sudah diurutkan:

[1, 2, 3, 4, 5]

Permasalahan

Algoritma merge sort bekerja dengan membagi daftar menjadi dua bagian, mengurutkan setiap bagian secara rekursif, dan kemudian menggabungkan hasil yang sudah diurutkan menjadi satu daftar yang sudah diurutkan. Namun, jika daftar yang akan diurutkan sangat besar, maka proses pembagian dan penggabungan tersebut dapat memakan waktu yang lama.

Solusi

Untuk mengatasi permasalahan tersebut, kita dapat menggunakan teknik yang disebut merge sort pararel. Merge sort pararel bekerja dengan membagi daftar menjadi beberapa bagian secara bersamaan, mengurutkan setiap bagian secara rekursif, dan kemudian menggabungkan hasil yang sudah diurutkan menjadi satu daftar yang sudah diurutkan. Dengan menggunakan teknik ini, kita dapat mengurangi waktu yang dibutuhkan untuk mengurutkan daftar yang sangat besar.

Berikut adalah contoh kode program C++ untuk mengimplementasikan algoritma merge sort:

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& arr, int l, int m, int r) {
  int i, j, k;
  int n1 = m - l + 1;
  int n2 = r - m;

  vector<int> L(n1);
  vector<int> R(n2);

  for (i = 0; i < n1; i++)
    L[i] = arr[l + i];
  for (j = 0; j < n2; j++)
    R[j] = arr[m + 1 + j];

  i = 0;
  j = 0;
  k = l;

  while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    }
    else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }
}

void mergeSort(vector<int>& arr, int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    merge(arr, l, m, r);
  }
}

int main() {
  vector<int> arr = {5, 3, 1, 2, 4};

  mergeSort(arr, 0, arr.size() - 1);

  for (int i = 0; i < arr.size(); i++) {
    cout << arr[i] << " ";
  }

  cout << endl;

  return 0;
}

Output dari kode program tersebut adalah:

1 2 3 4 5