삽입 정렬 (insertion sort)

주제(Subject)
--------------------------------------------------------
한글(약어) : 삽입 정렬()
영어(약어) : insertion sort()


관련개념(Related Concepts)
--------------------------------------------------------
정렬
알고리즘


개요(Summary)
--------------------------------------------------------
- 제자리정렬
- 안정적
- 범용 알고리즘으로는 부적합하나, 자료가 거의 정렬되어 있는 상태일 때에는 유효함
- 최초 자료배열의 순서에 매우 민감함
-  O(n²)


본문(Body)
--------------------------------------------------------
1. 병균 비교횟수

2. 소스코드
   1) Java (from Wanginator : Insertion Sort)

public class InsertionSort {
    public static void insertionsort (int[] a) {
        //Iterate over the list linearly, front part is sorted
        //insert element at correct position in sorted part
        for (int i=0; i < a.length; i++) {
            insert (a, i);
        }
    }
    private static void insert (int[] a, int i) {
        int k = a[i];  //k is element to be inserted
        int j = i;
        //shift all elements > k one position to the right
        while (j != 0 && a[j-1] > k) {
            a[j] = a[j-1];
            j--;
        }
        //insert k at correct position
        a[j] = k;
    }
}

3. 시뮬레이션
   1) Toshimi Minoura's(School of Electrical Engineering and Computer Science, Oregon State University, Corvallis , Oregon)
      http://web.engr.oregonstate.edu/~minoura/cs162/javaProgs/sort/InsertSort.html


모임,단체(Commutities)
--------------------------------------------------------


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)

* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Wikipedia : Insertion Sort
   http://en.wikipedia.org/wiki/Insertion_sort

2. Wanginator : Insertion Sort
   http://www.wanginator.de/studium/applets/insertionsort_en.html

3. Minoura's Demos : Sorting
   http://web.engr.oregonstate.edu/~minoura/cs162/demos.html