삽입 정렬(Insert Sort)
삽입 정렬은 정렬이 되어 있는 부분집합(Sorted)과 정렬이 되어 있지 않은 부분집합(Unsorted)으로 나누어 정렬이 되어 있는 부분집합에 새로운 원소의 위치를 찾아 '삽입'하여 정렬한다.
첫 번째 원소를 정렬 되어 있는 부분집합으로 시작하고, 정렬되지 않은 부분집합에서 원소를 정렬 되어 있는 부분집합 마지막 원소부터 비교하여 위치를 찾는다.
평균 비교 횟수는 n(n-1)/4 이고 평균 시간 복잡도는 O(n^2)이다.
예시)
{57, 16, 41, 2, 50}
하나의 집합이지만 편의상 나눠서 설명.
1. 첫 번째 원소를 정렬된 부분집합 S로 정하고 나머지 부분집합 U의 첫 번째 원소를 비교하여 위치를 찾아 삽입한다.
S = {57} U = {16, 41, 2, 50}
===> 16을 S의 마지막 원소부터 비교하여 위치를 찾아 삽입한다.(16 < 57)
S = {16, 57} U = {41, 2, 50}
2. 나머지 부분집합 U의 첫 번째 원소를 비교하여 위치를 찾아 삽입한다.
S = {16, 57} U = {41, 2, 50}
===> 41을 S의 마지막 원소부터 비교하여 위치를 찾아 삽입한다.(16 < 41 < 57)
S = {16, 41, 57} U = {2, 50}
3. 나머지 부분집합 U의 첫 번째 원소를 비교하여 위치를 찾아 삽입한다.
S = {16, 41, 57} U = {2, 50}
===> 2를 S의 마지막 원소부터 비교하여 위치를 찾아 삽입한다.(2 < 16)
S = {2, 16, 41, 57} U = {50}
4. 나머지 부분집합 U의 첫 번째 원소를 비교하여 위치를 찾아 삽입한다.
S = {2, 16, 41, 57} U = {50}
===> 50을 S의 마지막 원소부터 비교하여 위치를 찾아 삽입한다.(41 < 50 < 57)
S = {2, 16, 41, 50, 57} U = {}
5. 정렬되지 않은 부분집합 U가 비었기 때문에 삽입 정렬을 종료한다.
{2, 16, 41, 50, 57}
프로그램 작성)
package test;
class Sort {
public void insertSort(int[] a) {
int i, j, temp, size;
size = a.length;
// 첫 번째 원소는 정렬된 부분집합이라 생각하고 시작하므로 1부터 시작
for(i=1; i<size; i++) {
temp = a[i];
j = i;
while(j > 0 && a[j-1] > temp) {
// 삽입될 위치를 찾을 때 까지 한 칸씩 뒤로 밀어 자리 만들기
a[j] = a[j-1];
j--;
}
a[j] = temp;
}
}
}
public class Test {
public static void main(String[] args) {
int a[] = {57, 16, 41, 2, 50};
System.out.println("정렬 전 원소 : ");
for(int i=0; i<a.length; i++) {
System.out.printf(" %d", a[i]);
}
System.out.println();
Sort s = new Sort();
s.insertSort(a);
System.out.println("정렬 후 원소 : ");
for(int i=0; i<a.length; i++) {
System.out.printf(" %d", a[i]);
}
}
}
실행 결과)
'정렬' 카테고리의 다른 글
병합 정렬(Merge Sort) (0) | 2021.04.02 |
---|---|
셸 정렬(Shell Sort) (0) | 2021.04.02 |
퀵 정렬(Quick Sort) (0) | 2021.04.02 |
버블 정렬(Bubble Sort) (0) | 2021.04.02 |
선택 정렬(Selection Sort) (0) | 2021.04.02 |