insertion sort(삽입 정렬) 알고리즘

데이터 정렬 이유 : 탐색을 위해서 (정렬이 탐색보다 시간이 덜 걸린다 했나?..)

 

1. 삽입 정렬(Insertion Sort) 

Insert 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

 

 

. 버블 정렬 : 가장 쉽지만, 시간 복잡도 가능 높아 효율적이지 않음

 

 

. 선택 정렬 : 버블 정렬과 알고리즘 유사. 가장 큰 수 찾아 배열의 마지막 위치와 교환

 

 

 

 

 

 

 

 

참고

나무위키 정렬 알고리즘

Tony Medium - 정렬 알고리즘

알고리즘 공부 시작 방법

c++ sort 알고리즘

안경잡이 개발자