2. 삽입정렬(Insertion Sort)

두번째는 첫번째에 버금가게(?) 쉬운 삽입정렬입니다. 이름에 대해서 정확히 알아놓는 것이 해당 알고리즘을 이해하는 기초라고 할 수 있습니다. 삽입정렬? 말 그대로 삽입을 해가면서 하는 정렬입니다. 우선 실 데이터가 어떻게 정렬되는지 확인해볼까요?

 

출처: wikipedia.org

 

보시면 아시겠지만 loop를 돌면서 정렬이 필요한 데이터에 대해서 위치를 찾아 삽입을 합니다. 그렇기 때문에 정렬이름이 삽입 정렬입니다. 그러면 이것을 어떻게 구현할지 먼저 pseudo code를 보겠습니다.

mark first element as sorted
for each unsorted element
  'extract' the element
  for i = lastSortedIndex to 0
    if currentSortedElement > extractedElement
      move sorted element to the right by 1
    else: insert extracted element

 

해당 코드를 한번 자세히 살펴보겠습니다. 

 

 

     . 첫번째 element를 정렬이 된것으로 표시합니다.

     . 정렬이 되지 않은 element에 대해서 loop를 돌립니다.

     . loop에서 하나씩 element를 뽑아내고 기존에 정렬이 된것들과 비교를 합니다.

     . 뽑아낸 element 보다 비교 대상인 정렬된 element보다 크면 오른쪽으로 이동, 아닌 경우 그 자리에 삽입을 합니다.

     . 모든 element에 대해서 완료되면 정렬이 된것으로 봅니다.

우선 검증을 위해서 테스트 코드를 만들겠습니다. 거품정렬 때와 동일한 코드를 사용할 수 있습니다.

@Test
public void insertionSortTest() {
     Sort.insertionSort(original_array);
     assertThat(original_array, is(sorted_array));
}

그러면 해당 테스트를 통과하기 위해서 pseudo code를 참고해서 작성을 해보겠습니다.

public static void insertionSort(int[] original_array) {
	 for (int lastSortedIndex=1; lastSortedIndex<original_array.length; lastSortedIndex++) {
		 int currentSortedIndex = lastSortedIndex;
		 while (currentSortedIndex>0 && original_array[currentSortedIndex-1]>original_array[currentSortedIndex]) {
			 int tmp = original_array[currentSortedIndex-1];
			 original_array[currentSortedIndex-1] = original_array[currentSortedIndex];
			 original_array[currentSortedIndex] = tmp;
			 currentSortedIndex--;
		 }
	 }
}

위 코드를 보시면 아시겠지만 pseudo code와는 약간 다르게 작성되었습니다. 내용만 보면 똑같지만, 구조가 약간 달라졌죠? pseudo code대로 작성하기에는 for문에서의 index에 대한 처리라던지 이런게 까다로웠습니다. 구조만 보면 extractedElement가 currentSortedElement보다 작으면 계속 이동하다가, 아니면 그 자리에 extractedElement를 삽입하는 것입니다. 여기까지도 별 다른 어려움이 없을거라 생각하기 때문에 많은 설명은 생략하도록 하겠습니다. 다들 즐코딩하세요:)

출처: wikipedia.org

 

PS. 요새 너무 게을러져서 포스팅이 많이 딜레이 되었네요. 다시 한번 열심히 해볼께요.