삽입정렬이란
- 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
논리
- 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;
}
}
}
'알고리즘' 카테고리의 다른 글
[알고리즘] 선택정렬 (0) | 2023.11.29 |
---|---|
[알고리즘] 버블정렬 (0) | 2023.11.28 |
[알고리즘] 탐색 알고리즘 (0) | 2023.11.27 |
[알고리즘] 최소 값 찾기 알고리즘 (0) | 2023.11.27 |
[알고리즘] 최대 값 찾기 알고리즘 (0) | 2023.11.27 |