관리 메뉴

don't stop believing

Insertion Sort - 삽입 정렬 본문

Golang/Basic

Insertion Sort - 삽입 정렬

Tongchun 2019. 5. 8. 18:43

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

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

 

Insertion sort - Wikipedia

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provide

en.wikipedia.org

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

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)
}

 

'Golang > Basic' 카테고리의 다른 글

Counting Sort - 계수 정렬  (0) 2019.05.09
Shell Sort - 쉘 정렬  (0) 2019.05.09
Insertion Sort - 삽입 정렬  (0) 2019.05.08
Heap Sort - 힙 정렬  (0) 2019.05.07
Odd-Even Sort - 홀짝 정렬  (0) 2019.05.01
Comb Sort - 빗질 정렬  (0) 2019.04.29
0 Comments
댓글쓰기 폼