[정렬] SelectionSort, BubbleSort, InsertionSort, MergeSort, QuickSort, HeapSort

최악의 경우

최악의 경우에는, 시간복잡도가 각각 quicksort는 n^(2), mergesort와 heapsort는 각각 n*log(n)

Selection Sort - 선택 정렬

1. 가장 큰 값을 찾고, 가장 큰 값을 맨 마지막 값과 바꾸기
29 10 14 37 13
->
29 10 14 13 || 37
2. 나머지도 반복 =마지막 두 개의 데이터가 남을 때 까지
3. 값이 하나가 남으면 더이상 할 필요 X

시간복잡도 T(n) = O(n^2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
void selectionSort(int A[], int n)
{
	for (int i = n - 1; i >= 0; i--) 
	{
		int max=A[i], maxNum = i;
		for (int j = 0; j < i; j++)
			if (A[j] > max) 
			{
				max = A[j];
				maxNum = j;
			}
		int temp = A[maxNum];
		A[maxNum] = A[i];
		A[i] = temp;
	}
}

int main(void)
{
	int* A;
	int n;
	scanf("%d", &n);
	A = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);

	selectionSort(A, n);

	for (int i = 0; i < n; i++)
		printf("%d ", A[i]);

	free(A);
	return 0;
}

 

Bubble Sort - 버블 정렬

1. 맨 처음값과 자기 다음값과 비교해서 자기가 더 크면 자리를 바꾼다. 
2. 끝까지 반복하면, 맨 마지막에 가장 큰 값이 오게 된다.
Like 그물로 물살이를 모는 방식

시간복잡도 = O(n^2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
void bubbleSort(int A[], int n)
{
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j < i; j++) {
			if (A[j] > A[j + 1]) {
				int temp = A[j];
				A[j] = A[j + 1];
				A[j + 1] = temp;
			}
		}
	}
}
int main(void)
{
	int n;
	scanf("%d", &n);
	int* A = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);
	bubbleSort(A, n);
	for (int i = 0; i < n; i++)
		printf("%d ", A[i]);
	free(A);
	return 0;
}

 

Insertion Sort - 삽입 정렬

1. 맨 첫번째 데이터는 정렬이 된 상태라고 생각.
2. 첫번째 데이터에 두번째 데이터를 추가해서, 두 개를 정렬한다고 생각.
Ex) 15 12 라면 12 15 로 정렬시킴
3. 여기에 다시 13을 끼워넣어서, 3개의 데이터를 만들어야 함.
Ex) 15 12 13 -> 12 13 15
4. 여기서 추가되는 숫자들의 크기는 자기보다 작은 값이 어딘가에 따라서 정렬되도록 함.

가정 : k - 1개가 정렬되어 있다. k번째 데이터를 넣어 정렬시킬 것이다.
과정 : k번째 데이터보다 처음으로 큰 값이 나타나면, 그 앞 자리가 k번째 데이터가 들어갈 곳이다.
or 뒤에서부터 해도 됨. 뒤에서부터 하는 것이 앞에서부터 하는 것과는 다르게, 모든 자리들을 건들지 않아도 된다!
그리고 나머지 값들을 뒤로 미루자.
결과 : k번째 데이터를 앞쪽에 잘 끼워넣어서 결과적으로 정렬된 데이터를 만들 것이다.

수행시간 : 최악의 경우 O(n^2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
void insertionSort(int A[], int n)
{
	int i, j, k, tmp;
	for (int i = 1; i < n; i++)
	{
		for (j = 0; j < i; j++) 
			if (A[i] < A[j]) 
				break;

		tmp = A[i];
		for (k = i; k > j; k--) 
			A[k] = A[k - 1];
		A[k] = tmp;
	}
}
int main(void)
{
	int n;
	scanf("%d", &n);
	if (n <= 0)
		return 0;
	int* A = (int*)malloc(sizeof(int) * n);
	if (A == NULL)
		return 0;
	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);
	insertionSort(A, n);
	for (int i = 0; i < n; i++)
		printf("%d ", A[i]);
	free(A);
	return 0;
}

 

Merge Sort - 합병 정렬

분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
정복 : 각각의 작은 문제를 순환적으로 해결
합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

void merge(int A[], int p, int q, int r, int temp[])
{
	int i = p, j = q + 1, k = p;

	while (i <= q && j <= r) {
		if (A[i] < A[j]) //더 작은 값을 temp에 차례대로 담는다.
			temp[k++] = A[i++];
		else
			temp[k++] = A[j++];
	}

	if (i > q) //남은 값들을 temp에 마저 담는다
		for (; j <= r; j++, k++)
			temp[k] = A[j];
	else
		for (; i <= q; i++, k++)
			temp[k] = A[i];

	for (int z = p; z <= r; z++) //다시 A배열로 옮겨준다
		A[z] = temp[z];
}

void mergeSort(int A[], int p, int r, int temp[])
{
	if (p < r) {
		int q = (p + r) / 2;
		mergeSort(A, p, q, temp);
		mergeSort(A, q + 1, r, temp);
		merge(A, p, q, r, temp);
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);
	if (n <= 0)
		return 0;
	int* A = (int*)malloc(sizeof(int) * n);
	int* temp = (int*)malloc(sizeof(int) * n); //A값을 담을 임시 변수
	if (A == NULL)
		return 0;
	if (temp == NULL)
		return 0;
	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);
	mergeSort(A, 0, n - 1, temp); //n-1을 넣는 이유 : x<=y 형식으로 merge 할 것이기 때문에
	for (int i = 0; i < n; i++)
		printf("%d ", A[i]);
	free(A);
	free(temp);
	return 0;
}

Quick Sort - 퀵 정렬 (빠른 정렬)

마지막 값을 피봇(pivot)으로 사용
피봇보다 작은 값들과, 피봇보다 큰 값들로 분할
==> 반반으로 쪼개진다고 보장 X
분할, 정복, 합병(합병단계에서는 할 일이 읎다~!)

<과정>
1. 마지막 수를 기준(pivot)으로 삼는다.
2. 피봇보다 작은 수는 왼쪽에, 나머지는 기준의 오른쪽에 오도록 재배치(분할)한다.
3. 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다. (정렬 완료)

<partition>
1. i는 p-1, j는 p부터 시작한다. why? 피봇보다 작다고 분류된 값이 아직 없다 <=> i=p-1
2. 피봇보다 크면 j++
3. 피봇보다 작으면 i자리와 j자리 바꾸기
.
.
마지막으로 피봇값을 i+1 자리로
partition하는데 걸리는 시간 n-1
항상 절반으로 분할되는 경우 O(nLogn), 최대 O(n^2)
최선과 최악의 경우의 타협선.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int partition(int A[], int p, int r)
{
	int i = p - 1, j, tmp;

	for (j = p; j < r; j++)
	{
		if (A[j] < A[r]) { //새로 비교하는 값이 pivot보다 작으면
			i++;
			tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
		}
	}

	i++;
	tmp = A[i];
	A[i] = A[r];
	A[r] = tmp;
	return i;
}

void quickSort(int A[], int p, int r)
{
	if (p < r) {
		int q = partition(A, p, r);
		quickSort(A, p, q - 1);
		quickSort(A, q + 1, r);
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);
	if (n <= 0)
		return 0;
	int* A = (int*)malloc(sizeof(int) * n);
	if (A == NULL)
		return 0;
	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);
	quickSort(A, 0, n-1);
	for (int i = 0; i < n; i++)
		printf("%d ", A[i]);
	free(A);
	return 0;
}

QuickSort 추가

stdlib 헤더파일에 존재, 비교함수(compare)만 추가적으로 짜면 됨.

int compare(const void* a, const void* b)
{
	if (*(int*)a > *(int*)b)
		return 1;
	else if (*(int*)a < *(int*)b)
		return -1;
	else
		return 0;
}

int compare(const void* a, const void* b) // 오름차순
{
	if (*(int*)a > *(int*)b) // void 포인터를 int 포인터로 변환한 뒤 역참조
		return 1;
	else if (*(int*)a < *(int*)b)
		return -1;
	else
		return 0;
}

int compare(const void* a, const void* b)
{
	const char* str1 = *(const char**)a;
	const char* str2 = *(const char**)b;

	return strcmp(str1, str2);
}

long long compare(const void* a, const void* b)
{
	return (*(long long*)a - *(long long*)b);
}

int compare(const void* a, const void* b)
{
	int ageA = ((Member*)a)->age;
	int ageB = ((Member*)b)->age;

	if (ageA <= ageB)
		return -1;
	else
		return 1;
}

사용 qsort(save, n, sizeof(long long), compare);

참조 https://edu-coding.tistory.com/27

Heap Sort - 힙 정렬

최악의 경우에도 시간복잡도 O(nLogn) 보장 // qsort 안 돼서 얘로 해볼 예정. 제발 돼라!!!!!
sorts in place - 추가 배열 불필요
이진 힙(binary heap) 자료구조를 사용

Heap의 두가지 조건
1. complete binary tree
마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 가장 오른쪽부터 연속된 몇 개의 노드가 비어있을 수 있음
2. heap property
max heap property = 부모는 자식보다 크거나 같다

+ 힙은 유일하지 않음. 동일한 데이터를 가진 서로 다른 힙이 존재함!
+ 힙은 일차원 배열로 표현가능: A[1..n] (트리의 맨 위부터 책 읽는 순서로)
A[i]의 부모 = A[i / 2]
A[i]의 왼쪽 자식 = A[2i]
A[i]의 오른쪽 자식 = A[2i + 1]

MAX-HEAPIFY
루트노드만 유일하게 heap의 조건을 만족하지 않는 경우, 이 트리를 heap으로 만들어준다.
1. 루트노드가 가장 작을 경우, 밑의 수 중 더 큰 수와 루트노드를 바꿔준다.(이때 더 작은 수의 부분은 heap의 조건을 여전히 만족한다.)
2. 바뀐 노드를 루트로 취급하며 동일하게 이 과정을 반복한다.
3. 자신의 자식이 모두 자신보다 작아지거나, 더 이상 비교할 값이 없으면 종료된다.

void MAX_HEAPIFY(int A[], int i)
{
	if 자식이 없으면
		return;
	k = 가장큰자식i 넣어주기;
	if (A[i] >= A[k])
		return;
	exchange A[i] < ->A[k];
	MAX_HEAPIFY(A, k);
}​

배열을 정렬해보자!
일단, 배열을 트리라고 생각을 하자.
배열을 역순으로 고려했을 때, 처음으로 leaf 노드가 아닌 노드부터 생각한다!
그 노드가 heap을 만족한다면 pass, 만족하지 않는다면 자식 노드 중, 더 큰 값과 자리를 바꾸고 그 자식이 자식이 있다면 맨 밑까지 반복한다.
END.

void BUILD_MAX_HEAP(int A[]) //시간복잡도 : O(n)
{
	heap - size[A] < -length[A];
	for (i < -length[A / 2] down to 1)
		do MAX_HEAPIFY(A, i);
}

Heap Sort
1. 주어진 데이터로 힙을 만든다.
2. 힙에서 최대값을 가장 마지막 값과 바꾼다.
3. 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.
4. 루트노드에 대해서 HEAPIFY(1)한다.
5. 2~4번을 반복한다.

void HEAP_SORT(int A[])
{
	BUILD_MAX_HEAP(A);
	for (i < -heap size downto 2 do) {
		exchange(A[1] < ->A[i]);
		heap_size < -heap_size - 1;
		MAX_HEAPIFY(A, 1);
	}
}

힙의 응용: 우선순위 큐
최대 우선순위 큐(maximum priority queue)

INSERT
맨 마지막에 집어넣고, 자기의 부모보다 작을 때까지 exchange를 계속한다.

void MAX_HEAP_INSERT(int A[], int key)
{
	heap_size = heap_size + 1;
	A[heap_size] = key;
	i = heap_size;
	while (i > 1 and A[PARENT(i)] < A[i]) {
		exchange A[i] and A[PARENT(i)];
		i = PARENT(i);
	}
}​

 

시간복잡도 : O(log(2)n)

EXTRACT_MAX()
하나의 노드를 삭제할 때, 힙 형태를 유지하기 위해 마지막 노드를 줄이는 형태로 간다. 따라서 마지막에 저장된 데이터를 루트노드로 보내고, 힙 조건을 만족시키기 위한 작업(max-heapify)을 진행한다.

void HEAP_EXTRACT_MAX(int A[])
{
	if (heap_size[A] < 1)
		then error "heap underflow";
	max < -A[1];
	A[1] < -A[heap_size[A]];
	heap_size[A] < -heap_size[A] - 1;
	MAX_HEAPIFY(A, 1);
	return max;
}​

 

[무료] 영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 | 강의

 

 

+ 이진탐색

int search(long long save[], int st, int ed, long long find)
{
	int mid = -1;

	while (st <= ed) {
		mid = (st + ed) / 2;

		if (save[mid] >= find) {
			if (save[mid] == find)
				return 1;
			ed = mid - 1;
		}
		else {
			st = mid + 1;
		}
	}
	return 0;
}

cf) https://blog.naver.com/tomash72565/222648455114

C의 기본 정렬 알고리즘이 포함된 좋은 참조 카드/치트 시트?