Sorting Algorithm

• 정렬 정의
  • 입력 : n개로 이루어진 수열 $\{a_1, a_2, a_3, \dots , a_n\}$
  • 출력 : $a'_1 \le a'_2 \le \cdots \le a'_n$ 이고 $\{a_1, a_2, a_3, \dots , a_n\} =\{a'_1, a'_2, \cdots, a'_n \}$ 을 만족하는 입력 수열의 재배열

Insertion Sort Algorithm

• 두번째 원소(a[1]) 부터 맨 마지막 원소(a[n-1]) 까지에 대하여 각 원소가 왼쪽에 있는 모든 원소들보다 크거나 같을 때까지 원소를 왼쪽으로 이동시킴

  사람이 기본적으로 수행하는 정렬 방법

#include <iostream>
using namespace std;

int* insertionSort(int* A, int n){
	int i, j, key;
	for(j = 1; j<n; j++){
		key = A[j];
		i = j-1;
		while(i>=0 && A[i]>key){
			A[i+1] = A[i];
			i--;
		}
		// for(i = j-1; i>=0 && A[i]>key;i--){
		// 	A[i+1] = A[i];
		// }
		A[i+1] = key;
		for(int ind = 0; ind<n; ind++){
		cout<<A[ind]<<" ";
		}
		cout<<endl;
	}
	return A;
}

int main() {
	int a[] = {5, 2, 4, 6, 1, 3};
	int n = sizeof(a)/sizeof(a[0]);

	for(int i = 0; i<n; i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	int* result;
	result = insertionSort(a, n);
	for(int i = 0; i<n; i++){
		cout<<result[i]<<" ";
	}
	cout<<endl;
}

/* 출력결과
5 2 4 6 1 3 
2 5 4 6 1 3 
2 4 5 6 1 3 
2 4 5 6 1 3 
1 2 4 5 6 3 
1 2 3 4 5 6 
1 2 3 4 5 6
*/

Insertion Sort 수행시간 분석

$\therefore T(n)=c_1n + c_2(n-1) + c_3(n-1) + \sum_{j=1}^{n-1} \{ c_4t_j + c_5(t_j-1) + c_6(t_j-1) \} + c_7(n-1)\newline = n(c_1+c_2+c_3-c_5-c_6+c_7) - (c_2+c_3-c_5-c_6+c_7) + (c_4+c_5+c_6)\sum_{j=1}^{n-1}t_j$

• 최악의 경우 : i= j-1에서 i≥0 의 조건이 걸릴 때 → 최대 j+1회 반복

  $\therefore \sum_{j=1}^{n-1}t_j ≤ \cfrac{n(n-1)}{2} - 1$

  $\therefore T(n) ≤ \cfrac{c_4+c_5+c_6}{2}n^2 + (c_1+c_2+c_3+\cfrac{c_4-c_5-c_6}{2} + c_7)n -(c_2+c_3-c_4+c_7)$

  $\therefore T(n) = an^2 + bn + c$ 의 형태

• 케이스 설명 : $t_j$ 에 따라 다름

  • 최적의 경우 : 완전히 배열된 경우 : 1회 비교 후 스위치X 다음배열로 넘어가기 - 1차식!
  • 최악의 경우 : 완전히 반대로 배열된 경우 → j+1 회 비교후 스위치 - 2차식

증가 차수

• 가장 중요한 항(최고차항)만 남기고 계수는 없앤다 → $\Theta(n)$ 함수
• insertion sort = $\Theta(n^2)$