[기본 정렬 알고리즘] 3. 삽입 정렬(Insertion Sort)이란

 

 

1. 정렬 알고리즘이란? 

 

정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 그렇다면 왜 정렬 알고리즘을 사용해 데이터를 열거할까? 이유는 탐색하기 위해서다. 컴퓨터는 수 많은 데이터를 처리해야하는데 만약 데이터를 정렬하지 않는다면 데이터를 하나하나 일일이 탐색(순차 탐색)하여 원하는 데이터를 탐색해야 한다. 일반적으로 데이터를 삭제/삽입하기보다 탐색/조회하는 경우가 많기 때문에 매번 데이터를 탐색할 때마다 이런 식의 탐색은 매우 비효율적이다. 하지만 데이터가 일정한 규칙에 따라 순서대로 열거되었다면 다양한 탐색 방법을 이용하여 원하는 데이터를 빠르고 효율적으로 탐색할 수 있다. 

 

 

2. 삽입 정렬(Insertion Sort)이란? 

 

- 삽입 정렬이란 자료 배열/리스트의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열/리스트 부분과 비교하여, 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘이다. 

 

- 정렬 알고리즘 중 제자리 정렬 알고리즘 중 하나이다. 제자리 정렬 알고리즘이란 원소들의 갯수에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘으로, 삽입 정렬의 경우 이미 주어진 원소들을 옮긴 뒤 적잘한 위치에 원소를 삽입하는 연산을 반복하는데, 이 과정에서 원소들을 담는 공간 외에 추가로 사용될 수 있는 공간은 옮겨지는 원소가 저장되는 공간과 루프 변수 정도에 불과하다. 

 

- 선택 정렬 순서

 

• 두 번째 자료부터 시작하여 그 앞의 자료들과 비교한다. 
• 삽입할 위치를 찾으면 그 이후의 자료들을 뒤로 옮기고 자료를 삽입한다.
• 나머지 배열/리스트를 위와 같은 방법으로 정렬한다.  

  

- 선택 정렬은 레코드 수가 적거나 이미 정렬되어 있는 경우엔 알고리즘 자체가 매우 단순하므로 유용하다. 하지만 레코드 수가 많거나 정렬이 되어 있지 않는 경우엔 많은 레코드들이 이동하게 되므로 비효율적이다. 

 

3. 삽입 정렬의 예제 

 

 

 

4. 삽입 정렬의 코드

 

public class Insertion {

	public int[] sort(int[] data) {
		int tmp = 0 ; // 데이터 교체할 때 임시 저장 변수
		int j = 0; // 삽입할 인덱스 저장 변수 

		/* 첫번째 자료(0번 인덱스 값)은 이미 정렬된 것으로 가정함*/
		for(int i = 1; i < data.length; i++){

			tmp = data[i]; 	
	
			/* 알맞은 자리가 나올때까지 한칸씩 뒤로 옮기기*/
			for(j = i-1; j >= 0 && data[j]>key; j--) { 
				data[j+1] = data[j];
			}

			data[j+1] = tmp;
		}

		return data;
	}
}

 

 

 

5. 삽입 정렬의 복잡도 

 

 

- 공간 복잡도 

  : 별도의 추가 공간을 사용하지 않고 입력된 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)의 공간 복잡도를 가진다.

 

- 시간 복잡도 

  : 이미 정렬되어 있는 경우엔 한번씩만 비교를 하므로 O(n)의 시간 복잡도를 가진다.  그 외엔 총 두개의 for 루프를 이용하며 외부 루프를 통해 모든 인덱스에 접근하므로 기본적으로 O(N)의 시간 복잡도를 가진다. 이후 내부 루프를 통해 매 루프마다 앞 쪽에 미리 정렬되어 있는 값들과 비교하여 자신의 위치를 찾고 그 이후의 자료들은 뒤로 한칸씩 보내야하므로 추가적으로 O(N)의 시간이 필요하다. 그러므로 총 O(N²)의 시간 복잡도를 가진다. 

 

• 최선 시간 복잡도 : O(N)
• 평균 시간 복잡도 : O(N²)
• 최악 시간 복잡도 : O(N²)