Insertion Sort - 삽입 정렬

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

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

Insertion sort - Wikipedia

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX