Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- baekjoon
- 파이썬
- CS지식
- JPA
- 플러터
- Oracle
- 리눅스
- CS
- Java
- 자바
- springboot
- Spring Security
- 데이터베이스
- Flutter
- 네트워크
- postgresql
- 스프링부트
- python
- 데이터
- DB
- 자바스크립트
- 스프링
- 스프링 부트 쇼핑몰 프로젝트 with JPA
- spring
- 시큐리티
- backjoon
- 백준
- 자료구조
- 프로그래머스
- javascript
Archives
- Today
- Total
Jin's Dev Story
[알고리즘] 삽입 정렬(Insertion Sort) 본문
삽입 정렬
- 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘
- 순서에 맞게 삽입 시키는 정렬
- 평균과 최악 모두 수행 시간 복잡도는 O(n2)
Process (Ascending)
- 정렬은 2번째 위치(index)의 값을 temp에 저장
- temp와 이전에 있는 원소들과 비교하며 삽입
- '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){ // 1.
int temp = arr[index];
int prev = index - 1;
while( (prev >= 0) && (arr[prev] > temp) ) { // 2.
arr[prev+1] = arr[prev];
prev--;
}
arr[prev + 1] = temp; // 3.
}
System.out.println(Arrays.toString(arr));
}
시간복잡도
- 최악의 경우(역으로 정렬되어 있을 경우) (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 이다.
- 하지만, 모두 정렬이 되어있는 경우, 한 번씩 밖에 비교를 안하므로 O(n)
- 또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문
- 최선의 경우는 O(n)의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도
공간복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)
장점
- 알고리즘 단순
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적
- 정렬하고자 하는 배열 안에서 교환하는 방식, 다른 메모리 공간을 필요로 하지 않음 => 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort)
- Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠름
단점
- 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적
- Bubble Sort와 Selection Sort와 마찬가지로, 배열의 길이가 길어질수록 비효율적
'CS 지식 > [알고리즘]' 카테고리의 다른 글
[알고리즘] 선택 정렬(Selection Sort) (0) | 2023.07.18 |
---|---|
[알고리즘] 버블 정렬(Bubble Sort) (0) | 2023.07.18 |
[알고리즘]퀵 정렬(Quick Sort) (0) | 2023.07.18 |
[알고리즘]힙 정렬(Heap Sort) (0) | 2023.07.18 |
[알고리즘] 빅오표기법(big-O notation) (0) | 2023.07.17 |