무민이의 반반무많이

Insertion Sort(삽입 정렬) 본문

Algorithm/Theory

Insertion Sort(삽입 정렬)

M00min 2016.08.16 23:50

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)


Insert Sort(삽입 정렬)는 배열의 두 번째 값 부터 시작해서, 순서에 맞는 위치에 값을 삽입하는 방식을 말한다. 아래 예제를 통해 자세히 알아보자.


1. 먼저 배열에 아래와 같이 5개의 값이 있다고 하자. 우리는 이 값을 오름차순으로 정렬하고자 한다.


2. 먼저 두 번째 값을 기준으로 잡고, 기준보다 앞에 있는 값을 정확한 위치에 삽입하도록 하자. 여기서는 4가 5보다 작으므로 첫 번째 위치에 값이 삽입된다.


3. 첫 번째 기준 값인 4의 정렬이 완료되었다.


4. 다음으로 세 번째 값을 기준으로 잡고, 기준보다 앞에 있는 값을 정확한 위치에 삽입하도록 하자. 여기서 1은 5보다도 작고, 4보다도 작으므로 배열의 첫 번째 위치에 삽입된다.


5. 두 번째 기준 값인 1의 정렬이 완료되었다.


6. 다음으로 네 번째 값을 기준으로 잡고, 기준보다 앞에 있는 값을 정확한 위치에 삽입하도록 하자. 여기서 3은 5보다도 작고, 4보다도 작지만, 1보다는 크므로 배열의 두 번째 위치에 삽입된다.


7. 세 번째 기준 값인 3의 정렬이 완료되었다.


8. 마지막으로 다섯 번째 값을 기준으로 잡고, 기준보다 앞에 있는 값을 정확한 위치에 삽입하도록 하자. 여기서 2는 3, 4, 5보다는 작지만, 1보다는 크므로 배열의 두번째 위치에 삽입된다.


9. 네 번째 기준 값인 2의 정렬이 완료되었다.


지금까지 Insertion Sort(삽입 정렬)의 오름차순 정렬에 대해 알아보았다. 하나의 값을 기준으로 잡고, 기준 값을 기준의 앞에 있는 값들과 비교하여, 순서에 맞는 위치에 삽입한다고 하여 Insertion Sort(삽입 정렬)라고 부른다. 내림차순 정렬시에도 마찬가지로 기준보다 큰 값을 앞에서부터 정렬해 나가면 된다.


<오름차순 정렬>



<내림차순 정렬>

'Algorithm > Theory' 카테고리의 다른 글

Insertion Sort(삽입 정렬)  (0) 2016.08.16
Selection Sort(선택 정렬)  (0) 2016.08.16
Bubble Sort (버블 정렬)  (0) 2016.08.16
0 Comments
댓글쓰기 폼