삽입 정렬 - Java

알고리즘 

손 안의 카드 정렬을 하는 것과 유사하다.  기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입! 왼쪽 리스트에 정렬이 완료된 요소를 1개, 2개 점점 개수를 늘려가면서 정렬이 완료된다.

 

출처 : Pixabay

 

구체적인 알고리즘

1. 인덱스 1부터 시작한다. 
2. 현재 삽입될 요소인 i번째 요소를 key 변수에 복사
3. i-1번째 부터 역순으로 조사
4. j가 0보다 작아지거나 key값보다 정렬된 배열에 있는 값이 크면
5. j번째는 j+1번째로 이동한다.
6. j를 하나 감소한다.
7. j번째 정수가 key보다 작으므로 j+1번째가 key값이 들어갈 위치이다.

---

코드

	// 정렬 - 삽입 정렬
        int i,j;
        for(i= 1; i< N; i++){
            int key = num[i];
            for(j = i-1; j>=0&&num[j]>key; j--){
                num[j+1] = num[j];
            }
            num[j+1] = key;
        }

 

시간 복잡도

 삽입 정렬은 입력 자료의 구성에 따라 시간 복잡도가 달라진다. 대부분의 레코드가 이미 정렬되어 있는 경우에 시간 복잡도는 O(n)으로 매우 효율적일 수 있다. 하지만 정렬이 되어있지 않는 경우 시간 복잡도는 O(n^2)으로 효율성이 극히 떨어진다.

 

최선일 때

• 비교 횟수 : n-1 -  외부 루프를 돌 때마다 1번의 비교
• 이동 횟수 : 2(n-1)  - 외부 루프를 돌 때 마다 2번의 이동 (key값 복사, key값 삽입)

최악일 때

• 비교 횟수 : n*(n-1)/2  - 외부 루프를 돌 때 마다 i번 비교
• 이동 횟수 : 2(n-1) - 외부 루프를 돌 때마다 i+2번 이동 (i번 한칸씩 뒤로 이동, key 값 복사, key 값 삽입)

 

특징

• 안전한 정렬 방법이다
• 대부분의 레코드가 이미 정렬되어 있는 경우 매우 효율적이다