배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
논리
0번 인덱스는 정렬되있다고 가정한다.
1번 인덱스는 0번 인덱스와 비교하여 1번 인덱스가 작다면 앞으로 배치한다.
1번 인덱스가 크다면 상태를 유지한다.
next
2번 인덱스는 1번 인덱스, 0번 인덱스 순으로 비교하여 2번 인덱스가 작다면 앞으로 배치한다.
2번 인덱스가 크다면 상태를 유지한다.
next
....
이미지로 보기
특징
알고리즘이 단순하다.
대부분의 원소들이 정렬되어 있다면, 굉장히 효율적입니다.
안정 정렬 이다.(동일한 값을 가진 데이터들의 순서가 원래의 순서와 같이 유지되는 정렬방법)
동일 값이라도 그 데이터가 내포하는 의미는 다를 수 있다.
ex) 점수가 같은 학생
단점
데이터 크기나 정렬 상태에따라 성능 편차가 큰 정렬방식이다.
열의 길이가 길어질수록 비효율적이다.
n의 값에 따라 처리수도 1:1 비례해서 늘어난다.
100만개의 데이터가 있을 경우 100만번째 데이터는 99만번 비교해야 할 수도 있기 때문이다.
예제
[100,5,60,1000,30]이 [5,30,60,100,1000]가 되도록 정렬한다.
예제 코드
//배열 선언
int[] arr = new int[5];
//배열에 데이터 넣기
arr[0]=100;
arr[1]=5;
arr[2]=60;
arr[3]=1000;
arr[4]=30;
//비교 기준 값을 넣는 변수
int pivot;
//1번 인덱스 부터 반복
//기준 값 꺼내기
for(int i=1;i<arr.length;i++)
{
//기준 값 지정
pivot = arr[i];
int j;
//0번 인덱스 부터 반복
//비교 값 꺼내기
for(j=i-1;j>=0;j--)
{
//비교 값이 기준 값보다 크다면
if(arr[j] > pivot)
{
//비교 값을 한 칸 뒤로 넣는다
arr[j + 1] = arr[j];
//원래 비교 값 자리에 기준 값을 넣는다.
arr[j] = pivot;
}
}
}
