Go - 삽입정렬 구현하기

시간 복잡도

1. 최악의 경우(역으로 정렬 된 경우)

• 비교 횟수 : 외부 루프 안의 각 반복마다 i번의 비교 수행
  • (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)

1. 최선의 경우

• 비교 횟수 : 이동 없이 1번의 비교만 이루어진다.
  • (n-1)번 = O(n)

공간 복잡도

기존에 주어진 배열에서 원소 Swap만 이루어지므로 공간 복잡도는 O(n)이다.

특징

장점

1. 알고리즘 구현이 비교적 단순하다.
2. 대부분의 원소가 이미 정렬되어 있는 경우에 효율적이다.
3. 주어진 배열에서만 교환하므로 다른 메모리 공간이 필요하지 않다. => 제자리 정렬(in-place sorting)
4. 안정 정렬이다.
5. 다른 O(n^2) 알고리즘에 비해 상대적으로 빠르다.

단점

1. 시간 복잡도가 평균, 최악에서는 O(n^2)로 굉장히 비효율적이다.

 

Code

package main

import (
	"bufio"
	"fmt"
	"os"
)

func insertionSorting(arr []int) []int {
	for i := 1; i < len(arr); i++ {
		tmp := arr[i]
		idx := i - 1
		for 0 <= idx && tmp < arr[idx] {
			arr[idx+1] = arr[idx]
			idx--
		}
		arr[idx+1] = tmp
	}
	return arr
}

func main() {
	rd := bufio.NewReader(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)
	var n int
	fmt.Fscanf(rd, "%d\n", &n)
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscanf(rd, "%d\n", &arr[i])
	}
	sorted := insertionSorting(arr)
	for _, ele := range sorted {
		fmt.Fprintf(wr, "%d\n", ele)
	}
	wr.Flush()
}