삽입 정렬이란?

전체 리스트를 왼쪽 리스트와 오른쪽 리스트로 구분한 뒤, 오른쪽 리스트에서 임의의 레코드를 꺼내어 왼쪽 리스트의 적합한 위치에 삽입하는 방법.

이때, 왼쪽의 리스트는 정렬된 리스트이고 오른쪽 리스트는 정렬할 리스트로 가정한다.

(7, 3, 9, 4, 1, 6)을 삽입 정렬로 정렬한 순서

삽입 정렬의 단점

삽입 정렬은 배열로 이루어진 리스트들의 중간에 새로운 레코드를 삽입하려면 삽입될 위치의 오른쪽에 있는 레코드들은 한 칸씩 오른쪽으로 밀어야 한다. 그러므로 레코드의 크기가 크다면 얼마나 많은 시간을 레코드의 이동에 소모해야하는지 상상해보자.

따라서 삽입 정렬은 레코드 양이 많고 레코드 크기가 클 경우에 적합하지 않다. 반면에 대부분의 레코드가 이미 정렬되어 있는 경우에 효율적이다.

삽입 정렬의 비교횟수

삽입 정렬은 레코드의 수가 n일 경우 (n-1)번의 삽입을 필요로 하며, 매ㅓㄴ 삽입할 때마다 정렬된 리스트의 레코드를 비교해서 삽입될 위치를 찾아야 한다.

이때 필요한 평균 비교횟수는 이미 정렬된 왼쪽 리스트의 크기의 반으로 가정할 수 있으며, 그 크기는 1, 2, 3, ..., (n-2), (n-1)과 같이 증가한다.

삽입정렬의 이동횟수

레코드의 이동횟수는 비교횟수와 같으므로 삽입정렬은 비교 및 이동 측면에서 번의 연산이 필요하므로이다.

시간복잡도

삽입정렬 코드 (Java)

public int[] sort() {
	int temp = 0;
		
	for(int i = 1; i < array.length; i++) {
		temp = array[i];
		for(int j = i - 1; j >= 0 && array[j] > temp; j--) {
			array[j + 1] = array[j];
			array[j] = temp;
		}
	}
		
	return array;
}

정렬이란?

· 크기 순서에 무관하게 나열된 데이터를 크기 순서대로 다시 나열하는 작업.

· 데이터를 탐색하는데 반드시 필요한 작업.

· 크기가 커지는 순서로 정렬 → 오름차순 정렬.

· 크기가 작아지는 순서로 정렬 → 내림차순 정렬.

정렬 알고리즘의 효율을 평가하는 기준

· 비교횟수

· 데이터의 이동횟수

· 사용되는 메모리의 양

내부 정렬이란?

레코드를 모두 메모리 안으로 읽어 들여 리스트를 정렬하는 것.

* 레코드 : 정렬해야 할 대상.

* 리스트 : 레코드의 집합.

내부 정렬 방법

· 기본 정렬 방법 : 삽입 정렬, 선택 정렬, 버블 정렬.

· 성능 개선 방법 : 퀵 정렬, 합병 정렬, 쉡 정렬, 힙 정렬, 기수 정렬. 

외부 정렬이란?

외부 기억장치에 있는 레코드의 집합인 파일을 대상으로 레코드를 정렬하는 것.

* 파일 : 외부(보조)기억장치에 저장되는 레코드의 집합.

내부 정렬과 외부 정렬의 비교

· 내부 정렬은 메모리 안에서 정렬이 이루어지기에 접근 속도가 빠른 반면 외부 정렬은 상대적으로 접근 속도가 매우 느림.

· 용량의 차이는 내부 정렬이 메모리를 사용하기에 외부 정렬보다 상대적으로 매우 적다.

· 내부 정렬에서 레코드들을 비교 및 이동하는데 걸리는 시간은 메모리 접근 빈도수에 비례, 외부 정렬에서는 블럭 위의 파일 접근 빈도수에 비례.

· 내부 정렬의 효율은 데이터의 비교나 이동횟수를 줄임으로써 향상, 외부 정렬은 파일 I/O 횟수를 줄이는 것이 정렬시간을 줄이는 역할.

[출처] 정렬 탐색 프로그래밍