개인 공부/알고리즘
insertion sort(삽입 정렬) 알고리즘
_h.j
2021. 2. 9. 20:12
728x90
데이터 정렬 이유 : 탐색을 위해서 (정렬이 탐색보다 시간이 덜 걸린다 했나?..)
1. 삽입 정렬(Insertion Sort)
- 두 번째 원소부터 맨 마지막 원소까지 각 원소가 왼쪽에 있는 모든 원소 보다 크거나 같을 때 까지 왼쪽으로 이동
- 현재 위치보다 아래쪽 순회하며 알맞은 위치에 넣는 정렬
//insertion sort
#include <vector>
using namespace std;
template <typename T>
void insertSort( Vector<T>* v, const int l, const int r){
for(int i = l+1 ; i < r; i++){
for( j = i ; j > left && v[j] < v[j-1] ; j--){
swap(v[j-1],v[j]);
}
}
}
- 이미 정렬되어 있는 자료 구조에선 하나씩 삽입/제거 하는 경우엔 현실적을 최고의 정렬 알고리즘
- 탐색을 제외한 오버헤드 적음
- 배열이 작을 때 상당히 효율적
- 배열 사이즈 클 땐 O(nlogn) 알고리즘 쓰다가 정렬할 부분 작을 땐 삽입 정렬로 전환하는 것들도 있음
정렬 시간 복잡도
평균 : O(n²) ( O(n2) 중 빠른 편)
최선 : O(n) ( 가장 바깥 for문만 실행되기 때문에 )
최악 : 내림차순 배열되어 있다면
2.Merge Sort
. 버블 정렬 : 가장 쉽지만, 시간 복잡도 가능 높아 효율적이지 않음
. 선택 정렬 : 버블 정렬과 알고리즘 유사. 가장 큰 수 찾아 배열의 마지막 위치와 교환
참고
728x90