Sorting Algorithms — Insertion Sort {52/100}

Sorting merupakan salah satu hal penting yang ada di dunia komputer,sorting sering kali kita manfaatkan untuk mempermudah mendapatkan informasi tertentu secara cepat, contoh gampangnya, ketika kita ingin mencari sebuah nama di dalam buku telpon, kita cenderung akan melihat huruf pertama dari nama yang ingin kita cari dan kita akan membuka halaman dari buku telpon yang merujuk ke halaman yang notabene-nya berisi kumpulan nama-nama yang diawali huruf tersebut. Hal tersebut bisa kita lakukan karna buku telpon tersebut sudah di sortingberdasarkan alfabet.

Sorting merupakan hal yang penting di dalam pemrograman dan memilih teknik sorting yang benar merupakan hal yang sangat penting di dalam pemrograman.

Ada banyak teknik sorting yang bisa kita gunakan, Sebagai permulaan, maka malam ini kita akan membahas insertion sort.

Insertion sort pada dasarnya bekerja hampir sama seperti bubble sort, yang membedakan adalah, dalam insertion sort setelah 2 elemen selesai dibandingkan, algoritma ini tidak akan langsung membandingkan elemen selanjutnya, melainkan akan membandingkan lagi elemen yang baru selesai dibandingkan dengan elemen terakhir yang telah kita urutkan. Untuk mempermudah penjelasan mari kita visualisasikan.

Anggap kita mempunya list elemen array seperti ini

Proses pertama, kita membandingkan elemen pertama (14) dengan elemen kedua (33)

Hasilnya ternyata elemen pertama kita (14) dan elemen kedua (33) sudah terurut dengan benar

Selanjutnya kita lanjutkan ke proses kedua, dimana kita membandingkan elemen kedua (33) dengan elemen ketiga (27)

Setelah kita bandingkan ternyata elemen ketiga kita (27) lebih kecil dari elemen kedua (33) kita, lalu kita harus menukarnya (swap). Di proses ini, kita tidak akan lanjut membandingkan elemen ketiga (33) dengan keempat (10), sebagai gantinya kita akan membandingkan elemen pertama (14) dan elemen yang baru kita urut yaitu kedua (27). Ternyata setelah dibandingkan kedua elemen kita tersebut sudah terurut dengan benar, maka barulah algoritma ini akan melanjutnya proses membandingkan elemen ketiga dan keempat.

Elemen ketiga (33) ternyata lebih besar dibandingkan elemen keempat (10) maka kita harus menukarnya (swap)

Selanjutnya kita akan membandingkan elemen yang baru kita tukar/urut (10) dengan elemen terakhir yang sudah kita urutkan (27)

Ternyata elemen yang baru kita tukar/urut (10) lebih kecil dibandingkan elemen terakhir yang sudah kita urutkan (27), maka kita harus menukarnya

Selanjutnya kita akan membandingkan lagi elemen yang baru kita tukar/urut dengan elemen terakhir yang sudah kita urutkan (14)

Setelah dibandingkan ternyata kedua elemen tersebut harus ditukar. Proses seperti ini akan terus berjalan sampai benar-benar tidak ada lagi elemen yang harus ditukar posisinya

Algoritma

Step 1 − Jika sekarang adalah elemen pertama, itu berarti sudah terurut, dan return 1
Step 2 − Ambil elemen selanjutnya
Step 3 − Bandingkan dengan semua elemen yang sudah ada di list yang sudah terurut
Step 4 − Bandingkan elemen yang baru kita tukar dengan elemen terakhir yang ada di list yang sudah terurut
Step 5 − Masukan nilainya
Step 6 − Ulangi sampai tidak ada lagi elemen yang perlu kita tukar

Berikut cara penerapannya dengan Golang

package main
import (
  "fmt"
)
func swap(arrayzor []int, i, j int) {
   tmp := arrayzor[j]
   arrayzor[j] = arrayzor[i]
   arrayzor[i] = tmp
}
func insertionSort(array []int) {
   for i := 1; i < len(array); i++ {
    for j := i; j > 0 && array[j] < array[j-1]; j-- {
     swap(array, j, j-1)
    }
   }
}
func main() {
   array := []int{1, 6, 2, 4, 9, 0, 5, 3, 7, 8}
   fmt.Println("Unsorted array: ", array)
   insertionSort(array)
   fmt.Println("Sorted array: ", array)
}

https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm