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

Mengurutkan Angka dengan Algoritma Insertion Sort dalam C++

Pendahuluan

Dalam dunia pemrograman, mengurutkan data merupakan salah satu tugas yang umum dilakukan. Ada berbagai macam algoritma pengurutan yang dapat digunakan, salah satunya adalah algoritma insertion sort. Insertion sort adalah algoritma pengurutan yang sederhana dan mudah dipahami, sehingga menjadikannya pilihan yang tepat bagi pemula yang ingin belajar tentang algoritma pengurutan.

Cara Kerja Algoritma Insertion Sort

Algoritma insertion sort bekerja dengan cara mengurutkan data satu per satu. Dimulai dari elemen kedua, algoritma ini akan membandingkan elemen tersebut dengan elemen-elemen sebelumnya hingga menemukan posisi yang tepat untuk menyisipkannya. Proses ini diulang hingga semua elemen telah diurutkan.

Implementasi Algoritma Insertion Sort dalam C++

Berikut ini adalah implementasi algoritma insertion sort dalam bahasa C++:

#include <iostream>
#include <vector>

using namespace std;

void insertionSort(vector<int>& arr) {
  for (int i = 1; i < arr.size(); i++) {
    int key = arr[i];
    int j = i - 1;

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

    arr[j + 1] = key;
  }
}

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

  insertionSort(arr);

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

  cout << endl;

  return 0;
}

Analisis Algoritma Insertion Sort

Algoritma insertion sort memiliki kompleksitas waktu rata-rata O(n^2) dan kompleksitas waktu terburuk O(n^2). Kompleksitas ruang algoritma insertion sort adalah O(1).

Kelebihan dan Kekurangan Algoritma Insertion Sort

Kelebihan algoritma insertion sort adalah:

• Sederhana dan mudah dipahami
• Tidak memerlukan banyak memori tambahan
• Berjalan dengan baik pada data yang hampir terurut

Kekurangan algoritma insertion sort adalah:

• Tidak efisien untuk data yang besar
• Tidak stabil, artinya urutan elemen yang sama dapat berubah setelah diurutkan

Aplikasi Algoritma Insertion Sort

Algoritma insertion sort dapat digunakan dalam berbagai aplikasi, seperti:

• Mengurutkan data dalam array
• Mengurutkan data dalam daftar tertaut
• Mengurutkan data dalam tabel
• Mengurutkan data dalam file

Kesimpulan

Algoritma insertion sort adalah algoritma pengurutan yang sederhana, mudah dipahami, dan tidak memerlukan banyak memori tambahan. Algoritma ini berjalan dengan baik pada data yang hampir terurut, tetapi tidak efisien untuk data yang besar. Algoritma insertion sort dapat digunakan dalam berbagai aplikasi, seperti mengurutkan data dalam array, daftar tertaut, tabel, dan file.