Insertion sort adalah teknik pengurutan sederhana yang ideal untuk kumpulan data kecil atau hampir terurut. Dalam setiap iterasi, algoritma menghapus elemen, membandingkannya dengan elemen sebelumnya, dan menempatkannya di posisi yang tepat.
Insertion sort beroperasi dalam O(n²) waktu dalam kasus terburuk dan rata-rata tetapi mencapai kinerja linier ketika array sudah terurut. Ini adalah pengurutan in-place, stabil yang membutuhkan ruang ekstra konstan saja.
Proses Algoritma Insertion Sort
Berikut adalah representasi visual dari alur kerja insertion sort:
Insertion Sort Algorithm Process
Contoh Program Java untuk Mengurutkan Array menggunakan Algoritma Insertion Sort:
package com.guru99; public class InsertionSortExample { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("Before Insertion Sort"); printArray(myArray); insertionSort(myArray);//sorting array using insertion sort System.out.println("After Insertion Sort"); printArray(myArray); } public static void insertionSort(int arr[]) { int n = arr.length; for (int i = 1; i < n; i++) { System.out.println("Sort Pass Number "+(i)); int key = arr[i]; int j = i-1; while ( (j > -1) && ( arr [j] > key ) ) { System.out.println("Comparing "+ key + " and " + arr [j]); arr [j+1] = arr [j]; j--; } arr[j+1] = key; System.out.println("Swapping Elements: New Array After Swap"); printArray(arr); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Code Output:
Before Insertion Sort 860 8 200 9 Sort Pass Number 1 Comparing 8 and 860 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 200 860 9 Sort Pass Number 3 Comparing 9 and 860 Comparing 9 and 200 Swapping Elements: New Array After Swap 8 9 200 860 After Insertion Sort 8 9 200 860
