[알고리즘] 삽입 정렬(Insertion Sort)

 

 

2번째 원소부터 한 원소씩 선택해서 해당 원소와 그 앞(왼쪽)의 원소와 비교하고 삽입 정렬하는 알고리즘

→ 모든 원소를 앞에서부터 차례대로 이미 정렬된 배열 부분(자신의 앞 원소들)과 비교해 자신의 위치를 찾아 삽입하는 정렬 알고리즘

 

♟ 과정

---

1. 2번째 위치의 값을 x에 저장
2. x와 앞의 원소들과 비교하며 삽입
3. 1번으로 돌아가 다음 위치의 값을 x에 저장하고 반복

  → 자료가 삽입될 위치를 찾으면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동

 

 

♟ 코드(c++)

 

void InsertSort(int arr[]){
	for(int i = 1; i < arr.length; i++){      //2번째 원소 ~ 마지막 원소
		int x = arr[i];                         //비교할 원소
		int prev = arr[i-1];                    //바로 앞 원소
		while((prev >= 0) && (arr[prev] > x)){  //앞의 원소가 x보다 큼 && 1번째 원소 이상
			arr[prev+1] = arr[prev];              //앞 원소와 값 교환(swap)
			prev--;                               //앞으로 이동
		}
		arr[prev+1] = x;                        
	}
}

→ while문을 나오게 되면, prev에는 현재 x보다 작은 값 중 제일 큰 값의 위치를 가리킨다. 그러므로 prev의 다음에 x를 넣어준다.

 

 

♟ 시간 복잡도

---

• 최악의 경우: 역으로 정렬된 경우 O(n^2) → for문 루프 안의 각 반복마다 i번의 비교 수행
• 최선의 경우: 이미 정렬된 경우 O(n) → 이동 없이 1번의 비교만 이루어짐(루프 n-1번)

 

♟ 공간 복잡도

---

주어진 배열 안에서 교환(swap)이 이루어져 정렬되므로 O(n)

 

💡 이미 정렬된 배열에 자료를 하나씩 삽입/제거하는 경우, 최고의 정렬 알고리즘 (탐색을 제외한 오버헤드가 매우 적기 때문!)

 

 

 

♟ 장점

---

• 단순
• 레코드 수가 적을 경우, 다른 복잡한 정렬보다 유리
• 이미 정렬된 경우, 매우 효율적
• 값을 교환(swap)하는 방식으로, 다른 메모리 공간 필요X (in-place sorting)
• 안정 정렬(stable sort)
• selection/bubble sort(O(n^2)) 에 비해 상대적으로 빠름

 

♟ 단점

---

• 평균/최악의 시간 복잡도: O(n^2)
• 배열의 길이가 길어질수록 비효율적 (O(n) 혹은 O(n^2) 이므로)

 

 

♟ Selection Sort와 Insertion Sort

---

두 정렬 모두 k번째 반복 이후, 첫번째 k요소가 정렬된 순서로 온다.

 

selection sort는 k+1 요소를 찾기 위해 나머지 모든 요소를 탐색

insertion sort는 k+1 요소를 배치하는데 필요한 만큼의 요소만 탐색

→ insertion sort가 훨씬 효율적

 

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!

 

 

 

 

 

 

참고: https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html