Insertion Sort - 삽입 정렬

삽입 정렬입니다.
버블정렬과 비슷한데 배열의 1 번 자리에서부터 시작해 뒤로가면서 큰 값을 위치시킵니다.

https://en.wikipedia.org/wiki/Insertion_sort

Insertion sort - Wikipedia

어느정도 정렬이 되어있을 경우 효율이 좋은 방법입니다.

package main

import "fmt"

func main() {
	arr := [10]int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
	fmt.Println("Initial array is:", arr)
	fmt.Println("")

	if len(arr) <= 1 {
		fmt.Println("Sorted array is: ", arr)
		return
	}

	var i, j int

	// 1부터 시작해서 배열의 길이만큼 Loop를 실행합니다.
	for i = 1; i < len(arr); i++ {

		// 0 번째 자리에서부터 i 번째 자리보다 작을때 까지 Loop를 실행합니다.
		for j = 0; j < i; j++ {

			// i 번째 값과 이전 값들을 순차적으로 비교하고 i 번째 값보다 큰게 있다면 위치를 변경합니다.
			// 가장 큰 값이 점점 뒤로 이동하게 됩니다.
			if arr[j] > arr[i] {
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
	}

	fmt.Println("Sorted array is: ", arr)
}