목차
정렬이란?
- 임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 (오름차순) 또는 큰 순서부터 (내림차순) 늘어놓은 것임
- 정렬되어 있는 데이터들은 다음과 같은 작업을 수행할 때 응용
① 데이터를 탐색할 때
② 리스트에 있는 다른 항목들을 비교할 때
삽입정렬
- O(\(n^2\)) 알고리즘
- 정렬을 확장해 가는 방법
① 처음 두개의 데이터를 정렬
② 세번째 데이터를 자신의 정렬 위치에 삽입
③ 해당 방법을 반복
수도코드
insertSort(A):
for j = 2 to A.length
value = A[j]
// code of A[j] insert
i = j -1
// 비교하는 대상이 작으면 이동, i=0까지 이동하면 안됨
while i>0 and A[i]>value
// 한칸씩 뒤로 떙기기
swap A[i+1] = A[i]
// j전 인덱스와 계속 비교
i = i-1
// 위치를 찾으면 그곳에 삽입
// 마지막에 아닌데도 i = i-1을 해줬으니 다시 더해주자
A[i+1]
코드 설명
시간 복잡도
배열 전체를쭉 살펴보는 것을 n번
- while 문이 n인데 A가 정렬이 잘 되어있을수록 걸리는 시간은 내려감
하지만 최악의 경우는 \(n^2\)이므로 시간 복잡도는 O(\(n^2\))
평가
시간 복잡도는 O(\(n^2\)) 이지만 A가 정렬이 잘 되어있을수록 걸리는 시간은 내려감
보통 버블정렬보단 성능이 좋음
구현
파이썬 구현
def insertSort(A):
for j in range(1,len(A)): #2번째 위치에 있는 데이터 부터 기준으로 잡아야 하므로
value = A[j] # 이제 얘를 기준으로 비교할거다
i = j-1 # j전의 인덱스를 비교할 건데 그 비교하는 인덱스
#비교할 코드
while i>0 and value<A[i]:
A[i+1] = A[i] #뒤로 땡기기
i-= 1
# 자리를 찾았으면 while문 빠져나옴
A[i+1] = value
자바 구현
public class InsertSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int [] A = {3,44,38,5,47,15,36,26};
int value = 0;
for(int j = 1; j<A.length;j++) {
value = A[j];
int i = j-1; //비교 기준
//비교해야지
while(i>0 && value<A[i]) {
A[i+1] = A[i]; // 뒤로 떙겨주고
i-=1;
}
// while문 끝났으니 이제 해당 위치에 넣어 줌
A[i+1] = value;
}
// 모두 끝낸 A를 출력하는
for(int k = 0; k<A.length-1; k++) {
System.out.println(A[k]);
}
}