삽입정렬(Insertion sort)
삽입 정렬은 정렬이 우리가 카드놀이 할때 카드를 받아 정렬하는 것 처럼 즉 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬 하는 방법 입니다. 예를 들어 5장의 카드 A, 4, 7, J, 2를 순서대로 받았을 때 A, 4, 7, J는 정렬된 부분이므로 손대지 않고 2를 A와 4 사이에 집어 넣는 것을 떠올리시면 됩니다.
배열 arr[5]={1, 4, 7, 10, 2} 을 가지고 삽입 정렬을 설명 해보겠습니다.
{ 1, 4, 7, 10, 2 } temp = 4
배열의 첫번째는 이미 정렬 되어 있다고 가정하고 2번째 값 (arr[1]) 부터 시작합니다.
먼저 배열의 2번째 값을 임시 변수(temp)에 저장하고 배열의 첫번째 값과 비교 합니다.
arr[0]<temp 이므로 두 수는 올바르게 정렬되어 있습니다. 따라서 임시 변수에 저장된 값은 다시 원래 위치에 넣어줍니다.
{ 1, 4, 7, 10, 2 } temp = 7
다음으로 arr[2]을 선택해 임시 배열의 저장하고 이전 배열의 값들과 비교 합니다.
arr[1]<temp 그리고 arr[0]<temp 이므로 다시 원래 위치로 넣어줍니다.
마찬가지 방법으로 배열은 arr[3] 까지 정렬 되어 있으므로 생략하겠습니다.
...
{ 1, 4, 7, 10, 2 } temp = 2
다음으로 arr[4]을 선택해 임시 배열의 저장하고 이전 배열의 값들과 비교 합니다.
arr[3]>temp 이므로 arr[3]을 arr[4]로 밀어냅니다. { 1, 4, 7, 10, 10 } temp=2
arr[2]>temp 이므로 arr[2]를 arr[3]으로 밀어냅니다. { 1, 4, 7, 7, 10 } temp=2
arr[1]>temp 이므로 arr[1]을 arr[2]로 밀어냅니다. { 1, 4, 4, 7, 10 } temp=2 (빨간숫자는 의미없는 값.)
arr[0]<temp 이므로 temp의 저장된 값을 비어 있는 칸(의미없는 값) 에 넣어주면 정렬이 완료 됩니다. { 1, 2, 4, 7, 10 }
삽입 정렬은 데이터가 역순으로 주어졌을때 최악의 
간단하게 구현할 수 있으므로 자료수가 적거나 배열이 거의 정렬 되 어있을때 유용 할 수 있습니다.
다음은 자바로 구현한 삽입정렬 입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | //정렬된 부분에 정렬되지 않은 데이터를 삽입하는 방법. //간단하게 구현 할 수 있음. //최악의 경우 시간복잡도 O(n^2) //자료수가 적거나 자료의 정렬 정도가 높을때 적용. public void sort(int[] arr) { for (int i = 1; i < arr.length; i++) { int temp = arr[i]; // 임시 변수에 대상 배열 값을 저장한다. int j; for (j = i - 1; j >= 0; j--) { if(arr[j]<temp){ //임시변수가 비교하는 대상보다 클때 탐색 종료. break; }else{ arr[j+1]=arr[j]; //임시변수가 비교 대상보다 작다면 대상을 한칸 밀어낸다. } } arr[j+1]=temp; //임시변수에 저장한 값을 비어있는 위치에 삽입한다. } } public static void main(String[] args) { int[] arr = {1, 4, 7, 10, 2}; new InsertSort().sort(arr); for (int a : arr) { System.out.print(a + " "); } //출력 : 1 2 4 7 10 } | cs |
덧) 삽입 정렬의 비교의 횟수를 줄이기 위해 이진 검색(Binary Search) 을 이용 할 수 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | //삽입정렬에서 탐색에 걸리는 시간은 최악의 경우 i번째반복시 O(i) //이진탐색을 통해 탐색시간을 O(Logi)로 줄일 수 있다. //그러나 전체 알고리즘은 삽입에 필요한 시간 때문에 O(n^2)을 가짐. public int serach(int[] arr, int left, int right, int x) { if (right >= left) { int mid = left + ((right-left)/ 2); //찾는 값(x)과 배열의 요소가 일치하면 배열의 인덱스를 반환한다. if (arr[mid] == x) return mid; //찾는 값(x)보다 배열의 요소가 크다면 배열의 오른쪽 절반을 무시한다. if (arr[mid] > x) return serach(arr, left, mid-1, x); //찾는 값(x)보다 배열의 요소가 작다면 배열의 왼쪽 절반을 무시한다. return serach(arr, mid+1, right, x); } //일치하는 값이 없다면 배열의 맨 왼쪽 인덱스 반환 return left; } public void sort(int[] arr) { int temp,find_Index,j; //임시변수, 탐색결과가 들어갈 변수 선언 for (int i = 1; i < arr.length; i++) { temp = arr[i]; // 임시 변수에 대상 배열 값을 저장한다. find_Index= serach(arr, 0, i, temp); //임시변수 값이 들어갈 인덱스를 이진탐색한다. serach() 메소드 참조 for (j = i - 1; j >= find_Index; j--) { arr[j+1]=arr[j]; } //선택된 배열부터 임시변수 값이 들어갈 자리까지 오른쪽으로 한칸씩 밀어낸다. arr[find_Index]=temp; //임시변수에 저장한 값을 이진탐색을 통해 찾은 인덱스에 삽입한다. } } | cs |
'알고리즘/자료구조 > Sorting' 카테고리의 다른 글
| 버블정렬(Bubble sort) 알고리즘 (0) | 2016.03.10 |
|---|---|
| 선택정렬(Selection srot) 알고리즘 (0) | 2016.03.09 |