코딩테스트 및 알고리즘
삽입정렬
영카이브
2024. 1. 28. 22:54
문제 . N개 숫자가 입력되면 오름차순으로 선택정렬하시오.
입력 예시
6
13 5 11 7 23 15
답 :
5 7 11 13 15 23
나의 답변
public class Main {
public int[] solution(int n, int[] arr) {
for( int i=1; i<n; i++ ) {
int temp_value = arr[i];
int j;
for( j=i-1; j>=0; j-- ) {
if(temp_value<arr[j]) {
arr[j+1]=arr[j];
} else break;
}
arr[j+1]=temp_value;
}
return arr;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for( int i=0; i<n; i++ ) {
arr[i] = sc.nextInt();
}
for( int x : T.solution(n, arr)) {
System.out.print(x + " ");
}
}
}
삽입정렬
- 임시로 인덱스 1의 값을 삭제하고 이 값을 임시변수에 저장한다.
- 공백 왼쪽값을 가져와 임시 변수 값과 비교한다.
- 공백 왼쪽값이 임시변수값보다 크면 그 값을 오른쪽으로 시프트한다.
- 값을 오른쪽으로 시프트했으므로 공백이 왼쪽으로 옮겨진다.
- 임시로 삭제한 값보다 작은 값을 만나거나 배열의 왼쪽 끝에 도달해야 시프트 단계가 끝난다.
- 임시로 제거한 값을 현재 공백에 삽입한다.
삽입정렬은 비교, 시프트, 삭제, 삽입 단계가 있다.
- 비교는 최대 1 + 2 + ... + N - 1 번 일어나므로 N^2 / 2 번이다.
- 시프트는 한 셀 옮기는 것을 뜻하고 한 셀 옮기면 비교가 일어나기때문에 N^2 / 2 번이다.
- 비교와 시프트는 합치면 N^2 / 2 *2 = N^2 이다.
- 삭제와 삽입은 패스스루당 한 번 일어나고 패스스스루는 총 N -1번이므로 삭제와 삽입도 N - 1번이다.
- N^2 + N - 1 + N - 1 = N^2 + 2N - 2
- 빅 오 표기법은 가장 높은 차수 N만 고려하고 상수는 제거한다.
- 따라서 시간복잡도는 O(n^2) 이다.
선택정렬 / 버블정렬 / 삽입정렬 비교
시간복잡도는 모두 O(n^2) 이다.
최선 / 최악의 시나리오는 자주 발생하지 않으므로 평균 시나리오에 대부분은 초점을 맞추는것이 좋으나 상황에 따라 최선 / 최악의 시나리오에 초점을 맞춰야 할 수도 있다.
- 선택 정렬
- 최솟값을 찾아서 맨 앞부터 채워나가는 방식
- 전체 모든 아이템을 스캔
- 어떤 데이터에도 동일한 시간이 소요되어 정렬과 역순의 영향이 없음
- 대부분 역순으로 정렬된 데이터를 다룰 시 삽입정렬보다 효율적임
- 버블 정렬
- 인접한 원소끼리 비교하여 교환하는 방식
- 가장 비효율적이지만 단순함
- 삽입 정렬
- 앞에서부터 차례대로 이미 정렬된 부분과 비교하여 교환하는 방식
- 필요한 아이템만 스캔
- 정렬이 될수록 비교적 많은 비교 및 이동 필요하지 않음
- 거의 정렬된 데이터를 다룰 시 선택정렬보다 효율적임
| 알고리즘 | 최선의 시나리오 | 평균 시나리오 | 최악의 시나리오 | 비고 |
| 선택 정렬 | N^2 / 2 | N^2 / 2 | N^2 / 2 | 교환: N | 삽입, 삭제 없음 |
| 버블 정렬 | N - 1 | N^2 / 2 | N^2 | 교환: N^2 / 2 | 삽입, 삭제 없음 |
| 삽입 정렬 | N | N^2 / 2 | N^2 | 삽입: N | 교환, 삭제 없음 |
https://www.youtube.com/watch?v=Bor_CRWEIXo
책 <누구나 자료구조와 알고리즘>