삽입 정렬(insertion sort) 자바로 구현.

Introduction To Algorithms, Third Edition 국내도서 저자 : 토머스 코멘(Thomas H. Cormen),찰스 레이서손(Charles E. Leiserson),로날드 리베스트(Ronald L. Rivest),클리포드 스타인(Clifford Stein) / 문병로역 출판 : 한빛아카데미 2014.06.30 상세보기

겨울 동안 연구실에서 대학원생들, 학부 인턴들 모두 모여 함께 공부할 책입니다. 학부 시절에 알고리즘 수업을 (아마도) 데이터구조론 시간과 네트워크와 알고리즘 시간(네트워크 또는 그래프 상에서 쓰는 알고리즘)에 배운 게 전부이므로, 더 깊이있게 공부하려고 고른 책입니다.

학교 도서관에서 영어 책으로 빌려서 보고 있었는데, 국내 도서가 있는 곳에 가보니 한글로 번역된 책이 있네요. 그래서 한글판으로 빌려서 읽고, 수도코드 부분이랑 약간 이해 안되는 부분 정도만 원서를 보고 있습니다.

지난 여름에 합병정렬(병합정렬)과 퀵 정렬은 구현해서 블로그에 글로 남겨두었는데요.

2015/07/09 - [노트정리/알고리즘 놀이] - 자바로 구현한 퀵 소트(quick sort), 자바 소스 코드

2015/07/04 - [노트정리/알고리즘 놀이] - 자바로 구현한 머지소트(merge sort, 합병정렬), 자바 소스 코드.

더블릿에서 문제 풀 때, 이게 삽입 정렬인지도 모르면서 그냥 구현해서 썼었습니다. 쉬운거지만 블로그에 남겨두려고 글로 써봅니다.

2장 insertion sort에서 삽입정렬의 수도코드는 다음과 같습니다.

for j = 1 to A.length
	key = A[j]
	
	i = j - 1
	
	while i >= 0 and a[i] > key
		A[i+1] = A[i]
		i = i - 1
	A[i+1] = key

(책과 달리 수도코드 그대로 코딩하면 구현되도록 i, j의 값을 바꿈)

그래서 자바로 구현하면 아래와 같습니다.

public class Main {
	public static void main (String[] args) {
		int[] a = {5,2,4,6,1,3};
		
		for(int j = 1; j < a.length; j++) {
			int key = a[j];
			int i = j-1;

			while(i >= 0 && a[i] > key) {
				a[i+1]=a[i];
				i = i - 1;
			}
			a[i+1]=key;
		}
		
		for(int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}
}