목차

1. 선택 정렬(Selection Sort)
2. 버블 정렬(Bubble Sort)
3. 삽입 정렬(Insert Sort)
4. 퀵 정렬(Quick Sort)
5. 병합 정렬(Merge Sort)

개념

특정 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 나열하는 알고리즘

1. 선택 정렬(Selection Sort)

인접한 두개의 요소를 비교하며 정렬
가장 작은걸 선택하여 왼쪽으로 보냄

#include <stdio.h>
int main(){
	for(i = 0; i < n-1; i++){
      min = i;
      for(j = i + 1; j < n; j++)
     	if(arr[j] < arr[min])
     		min = j;
    swap(&arr[min], &arr[i]);
    }
return 0;
}

시간 복잡도
최악의 경우 처음부터 끝까지 배열을 다 탐색 해야 한다
=> 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
=> n(n+1)/2
=> 0(n^2)

결론

구현이 쉽지만 비효율 적임

2. 버블 정렬(Bubble Sort)

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보냄
즉 가장 큰 값이 맨 뒤로 보내짐

#include <stdio.h>
int main(void) {
	int i, j, temp;
	int arr[10] = { 1,10,5,8,7,6,4,3,2,9 };
	for (i = 0; i < 10; i++) {
		for (j = 0; j < 9 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

시간 복잡도
=> 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
=> n(n+1)/2
=> 0(n^2)

결론

구현이 가장 쉽지만 가장 비 효율적임
선택 정렬보다 비 효율적인 이유는 버블 정렬은 다 비교 하면서 정렬 하기 떄문에 비 효율적이다

3. 삽입 정렬(Insert Sort)

각 숫자를 적절한 위치에 삽입 함
삽입 정렬은 맨 앞에 원소는 비교할 원소가 없어서 2번째 원소부터 진행 하면 된다

#include <stdio.h>
int main(void) {
	int i, j, temp;
	int arr[10] = { 1,10,5,8,7,6,4,3,2,9 };
	for (i = 0; i < 9; i++) {
		j = i;
		while (arr[j] > arr[j + 1]) {
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
		}
	}
}

=> 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1
=> n(n+1)/2
=> 0(n^2)

결론

선택 정렬과 버블 정렬은 원소들의 위치를 바꿔 주더라도 바꾼 원소 기준 앞에 원소들이 정렬이 안 되어 있어 연산을 또 수행하지만
삽입 정렬은 위치를 바꾼 해당 원소 기준 앞에 있는 원소들은 정렬이 되어 있어 연산을 수행하지 안 해도 돼 시간복잡도는 같지만 버블, 선택 정렬보다 빠르다.

4. 퀵 정렬 (Quick Sort)

특정한 값 기준으로 큰 숫자와 작은 숫자를 나눔
이때 사용하는게 pivot
pivot는 보통 배열의 첫번째 값 이나 중앙값을 사용 함
왼쪽에서 오른쪽으로 이동할땐 큰 값을 찾고
오른쪽에서 왼쪽으로 이동할 때는 작은 값을 찾음
큰값과 작은값 위치 변경

void quickSort(int *data, int start, int end) {
	if(start >= end){ // 원소가 1개인 경우
		return;
	}
	int pivot = start;
	int i = start + 1;
	int j = end;
	int temp;
	while(i <= j){//엇 갈릴 때 까지 반복
		while(data[i] <= data[pivot]){//피봇 값보다 큰 값을 만날때 까지
			i++;
		}
		while(data[j] >= data[pivot] && j > start){//피봇 값 보다 작은 값을 만날때 까지
			j--;
		}
		if(i > j){// 현재 엇 갈린 상태면 피콧 값과 교체
			temp = data[j];
			data[j] = data[pivot];
			data[pivot] = temp;
		}
		else {
			temp = data[j];
			data[j] = data[i];
			data[i] = temp;
		}
	}
	quickSort(data, start, j - 1);
	quickSort(data, j + 1, end);
}

퀵 정렬은 분할정복을 통하여 구현한다.
퀵 정렬의 평균 시간복잡도는 O(nlogn)
하지만
배열이 이미 정렬 되어 있는 경우는 O(n^2)

5. 합 정렬(Merge Sort)

#include <stdio.h>

#define NUMBER 8
int sorted[8]; //정렬 된 값을 담아줄 배열

void merge(int a[], int m, int middle, int n) {
int i = m;
int j = middle + 1;
int k = m;

// 작은 순서대로 배열에 삽입
while (i <= middle && j <= n) {
	if (a[i] <= a[j]) {
		sorted[k] = a[i];
		i++;
	}
	else {
		sorted[k] = a[j];
		j++;
	}
	k++;
}
if (i > middle) {
	for (int t = j; t <= n; t++) {
		sorted[k] = a[t];
		k++;
	}
}
else {
	for (int t = i; t <= middle; t++) {
		sorted[k] = a[t];
		k++;
	}
}
// 정렬된 배열에 삽입
for (int t = m; t <= n; t++) {
	a[t] = sorted[t];
}

}

void mergeSort(int a[], int m, int n) {
if (m < n) {
int middle = (m + n) / 2;
mergeSort(a, m, middle);
mergeSort(a, middle + 1, n);
merge(a, m, middle, n);
}
}

int main() {
int arr[NUMBER] = { 7,6,5,8,3,5,9,10 };
mergeSort(arr, 0, NUMBER - 1);
for (int i = 0; i < NUMBER; i++) {
printf("%d ", arr[i]);
}
return 0;
}