재시민

void InsertionSort(vector<int>& v, int f,int n, int h) {
	int i, j,temp;
	for (i = f + h;i < n;i+=h) { //h 만큼의 격차를 벌림 h가 작으면 작을수록 셸이 작아짐
		temp = v[i];
		for (j = i-h;f <= j && temp < v[j]; j -= h) {
			v[j + h] = v[j];// 셸의 개수만큼 반복하여 삽입정렬
		}
		v[j + h] = temp; //for 의 조건을 만족하지 못한다면 재할당
	}
}

void ShellSort(vector<int>& v, int n) {
	int i, h;
	for (h = n / 2;h > 0;h /= 2) {
		if (h % 2 == 0) h++;//2의 배수일 경우 1증가 맨마지막에 h 가 1일경우 존재위해
		for (i = 0;i < h;i++) InsertionSort(v, i, n , h);// i 값을 증가시키면서 셸 변경
	}
}

시간 복잡도 

최선시간 복잡도 O(n)

최악시간 복잡도 O(n1.5)

제자리성 : 제자리 정렬

안정성 : 불안정

인접하지 않은 원소끼리의 비교

알고리즘

1. h 의 격차를 두고 셀 설정

2. 셀 내부에서 삽입정렬

3. i 값을 늘리면서 셀 변경

4. for 문을 통해 다시 삽입정렬

5. for 문을 통해 h 변경

void InsertionSort(vector<int>& v, int n) {
	int i, j,temp;
	for (i = 2;i < n;i++) { //v[0] = -1 더미값 세팅
		temp = v[i];
		j = i;
		while (v[j - 1] > temp) { //이전 값과 비교 후 크면 스왑
			swap(v[j], v[j - 1]);
			j--;
		}
	}
}

void insertionSort(vector<int>& v, int n) {
	int i, j;
	for (i = 1; i < n; i++) {
		for (j = i; j >0;j--) {
			if (v[j] < v[j - 1]) swap(v[j], v[j - 1]);
		}
	}
}

알고리즘

1. v[0] 에 더미값 세팅 

2. 삽입할 값 temp 에 저장

3. temp 값과 temp 이전 값들과 비교후 크면 스왑

void bubbleSort(vector<int>& v, int n) {
	int i, j,temp;
	for (i = n-1; i > 0;i--) {// n-1 완료되면 가장큰수 배열의 맨 끝에 위치 다음 n-2,n-3...,1
		for (j = 0;j < i;j++) {
			if (v[j] > v[j + 1]) swap(v[j], v[j + 1]);
		}
	}
}

for 문 한번 돌때마다 가장 큰 수가 맨 뒤에 위치하게 된다.

따라서, 매 회 n-i 순회 하며

안정성 : 안정된 정렬 (인접한 레코드끼리만 자리바꿈)

제자리성 : 제자리 정렬

평균시간복잡도 = O(n2)

최악시간복잡도 = O(n2) (역순으로 정렬)

알고리즘

1. 첫번째 for 에서 i 의 크기를 n-1 부터 순회

2. 두번째 for 에서 j 를 i 까지 순회하면서 v[j] > v[j+1] 이면 swap

void SelectionSort(int A[], int n) // input Array, index size
{
	int i, j, MinIndex;
    for(i = 0; i<n-1;i++){
    	MinIndex = i;
        for(j = MinIndex + 1; j<n;j++){
        	if(A[MinIndex] > A[j])
            	MinIndex = j;
                }
        if(MinIndex != i) swap(A[i], A[Minindex]);
       }
}

알고리즘 설명

1. MinIndex 로 배열의 비교 기준을 변화시켜 비교

2. A[MinIndex] > A[j] 이면 기준 인덱스와 비교 인덱스와 비교 후 MinIndex 변경

3. 두번째 포문이 끝나고 MinIndex 값이 바뀌었다면 스왑

i번째 단계에서 항상 n-i회 비교수행

평균시간복잡도 = O(n2)

최악시간복잡도 = O(n2)

제자리성 : 제자리 정렬

- i,j,MinIndex 상수크기 메모리

불안정한 정렬

- B b a c > a b B c