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

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

Dalam dunia pemrograman, kemampuan algoritma untuk mengurutkan data merupakan salah satu hal penting yang perlu dikuasai. Salah satu algoritma yang umum digunakan untuk mengurutkan data adalah Insertion Sort. Algoritma ini terkenal dengan kesederhanaannya dan bekerja dengan cara menyisipkan elemen-elemen data satu per satu ke dalam array yang sudah terurut.

Permasalahan:

Diberikan sebuah array angka yang belum terurut. Tujuan kita adalah mengurutkan angka-angka tersebut dalam urutan menaik menggunakan algoritma Insertion Sort.

Solusi:

1. Inisialisasi Array:

int main() {
  int arr[] = {5, 3, 1, 2, 4};
  int n = sizeof(arr) / sizeof(arr[0]);

Dalam kode di atas, kita mendefinisikan sebuah array arr yang berisi angka-angka yang belum terurut. Variabel n menyimpan jumlah elemen dalam array.

2. Looping dari Elemen Kedua:

  for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;

Looping dimulai dari elemen kedua (indeks 1) hingga elemen terakhir (indeks n-1). Elemen pertama (indeks 0) dianggap sudah terurut. Variabel key menyimpan nilai elemen yang sedang dipertimbangkan untuk disisipkan. Variabel j menyimpan indeks elemen yang sedang dibandingkan dengan key.

3. Cari Posisi yang Tepat:

    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }

Looping ini mencari posisi yang tepat untuk menyisipkan key ke dalam array yang sudah terurut. Selama j tidak kurang dari 0 (artinya masih ada elemen yang belum dibandingkan) dan nilai elemen pada indeks j lebih besar dari key, maka elemen tersebut digeser ke kanan (indeks ditambah 1) dan j dikurangi 1. Ini dilakukan hingga posisi yang tepat untuk menyisipkan key ditemukan.

4. Sisipkan Elemen:

    arr[j + 1] = key;
  }

Setelah posisi yang tepat ditemukan, key disisipkan ke dalam array pada indeks j + 1.

5. Hasil Akhir:

Setelah semua elemen diurutkan, array arr akan berisi angka-angka yang sudah terurut dalam urutan menaik.

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

  cout << endl;

  return 0;
}

Contoh:

Misalkan kita memiliki array angka {5, 3, 1, 2, 4}. Setelah diurutkan menggunakan algoritma Insertion Sort, hasilnya adalah {1, 2, 3, 4, 5}.

Kompleksitas Algoritma:

• Waktu:
  • Terbaik: O(n)
  • Rata-rata: O(n^2)
  • Terburuk: O(n^2)
• Memori: O(1)