Belajar Algoritma Insertion Sort untuk Pemula: Penjelasan Sederhana
Sebelum membahas tentang Algoritma Insertion Sort, pernahkah Anda merasa kesulitan dalam mengurutkan data secara efisien? Meskipun terdapat banyak algoritma pengurutan, namun setiap algoritma memiliki kelebihan dan kekurangan masing-masing. Algoritma Insertion Sort sendiri merupakan salah satu algoritma pengurutan yang cukup sederhana, namun sangat berguna dalam mengurutkan data dengan cepat dan efisien. Dalam artikel ini, kami akan membahas secara detail tentang Algoritma Insertion Sort, termasuk cara kerjanya, langkah-langkah implementasi, serta analisis kompleksitasnya. Dengan memahami Algoritma Insertion Sort, Anda akan memiliki dasar yang kuat dalam mengembangkan aplikasi atau program yang membutuhkan pengurutan data secara efisien.
Algoritma Insertion Sort adalah salah satu algoritma pengurutan sederhana yang bekerja dengan membandingkan setiap elemen satu per satu, kemudian menyisipkan elemen tersebut ke posisi yang tepat dalam urutan yang sudah terurut. Konsepnya seperti menyusun kartu dari tangan, dengan menyisipkan kartu yang baru ke dalam urutan yang sudah terurut, satu per satu.
Kelebihan utama dari Algoritma Insertion Sort adalah kecepatannya yang relatif cepat untuk mengurutkan data dalam jumlah yang kecil atau terurut secara parsial. Algoritma ini juga membutuhkan sedikit memori untuk diimplementasikan. Karena kesederhanaannya, algoritma ini mudah dipahami dan diimplementasikan oleh pengembang pemula.
Namun, Algoritma Insertion Sort memiliki beberapa kelemahan. Algoritma ini tidak efisien untuk mengurutkan data dalam jumlah yang besar, karena kompleksitas waktu-nya adalah O(n^2). Selain itu, algoritma ini tidak efektif untuk mengurutkan data yang sudah terurut secara terbalik.
Waktu yang tepat untuk menggunakan Algoritma Insertion Sort adalah ketika data yang diurutkan tidak terlalu banyak, atau data yang diurutkan sudah dalam keadaan terurut parsial. Algoritma ini sering digunakan sebagai bagian dari algoritma pengurutan yang lebih kompleks, seperti Merge Sort atau Quick Sort.
Dalam pengembangan perangkat lunak, Algoritma Insertion Sort digunakan untuk mengurutkan data dalam berbagai jenis aplikasi, seperti pengolahan data, pencarian data, analisis data, dan sebagainya. Algoritma ini juga digunakan dalam sistem pengurutan data dalam database atau spreadsheet.
berikut ini adalah contoh step by step penggunaan Algoritma Insertion Sort untuk mengurutkan sebuah array:
Misalkan kita memiliki sebuah array angka sebagai berikut: [5, 2, 4, 6, 1, 3]
- Langkah pertama adalah dengan memilih elemen pertama dari array sebagai elemen yang sudah terurut. Dalam hal ini, elemen pertama adalah angka 5.
- Selanjutnya, kita akan membandingkan elemen kedua (angka 2) dengan elemen yang sudah terurut. Karena angka 2 lebih kecil dari 5, maka kita akan memindahkan angka 5 ke posisi selanjutnya dan menempatkan angka 2 ke posisi pertama dalam urutan yang sudah terurut. Sekarang urutan yang sudah terurut adalah [2, 5], dan urutan yang belum terurut adalah [4, 6, 1, 3].
- Selanjutnya, kita akan membandingkan elemen ketiga (angka 4) dengan elemen yang sudah terurut. Kita akan membandingkannya dengan angka 5 terlebih dahulu, dan karena angka 4 lebih kecil dari 5, maka kita akan memindahkan angka 5 ke posisi selanjutnya dan menempatkan angka 4 di posisi sebelumnya dalam urutan yang sudah terurut. Sekarang urutan yang sudah terurut adalah [2, 4, 5], dan urutan yang belum terurut adalah [6, 1, 3].
- Langkah selanjutnya adalah membandingkan elemen keempat (angka 6) dengan elemen yang sudah terurut. Kita akan membandingkannya dengan angka 5 terlebih dahulu, dan karena angka 6 lebih besar dari 5, maka angka 6 tetap berada pada posisi saat ini. Urutan yang sudah terurut adalah [2, 4, 5], dan urutan yang belum terurut adalah [6, 1, 3].
- Kita akan membandingkan elemen kelima (angka 1) dengan elemen yang sudah terurut. Kita akan membandingkannya dengan angka 5 terlebih dahulu, dan karena angka 1 lebih kecil dari 5, maka kita akan memindahkan angka 5 ke posisi selanjutnya dan menempatkan angka 1 di posisi sebelumnya dalam urutan yang sudah terurut. Kita kemudian membandingkan angka 1 dengan angka 4 dan memindahkan angka 4 ke posisi selanjutnya. Kemudian kita membandingkan angka 1 dengan angka 2 dan memindahkan angka 2 ke posisi selanjutnya. Sekarang urutan yang sudah terurut adalah [1, 2, 4, 5], dan urutan yang belum terurut adalah [6, 3].
- Kita akan membandingkan elemen terakhir (angka 3) dengan elemen yang sudah terurut. Kita akan membandingkannya dengan angka 5 terlebih dahulu, dan karena angka 3 lebih kecil dari 5, maka kita akan memindahkan angka 5 ke posisi selanjutnya, lalu membandingkan angka 3 dengan angka 4 dan memindahkan angka 4 ke posisi selanjutnya. Kemudian kita membandingkan angka 3 dengan angka 2 dan memindahkan angka 2 ke posisi selanjutnya. Akhirnya, kita menempatkan angka 3 di posisi pertama dalam urutan yang sudah terurut. Sekarang urutan yang sudah terurut adalah [1, 2, 3, 4, 5], dan urutan yang belum terurut adalah [6].
- Karena hanya ada satu elemen yang belum terurut, maka urutan ini dianggap sudah terurut secara keseluruhan.
public static void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}
public static void InsertionSort(int[] arr) {int n = arr.Length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}