버블 알고리즘

버블 정렬이란?

서로 인접한 두 원소의 크기를 비교 (왼쪽이 오른쪽보다 크면 교환) 을 반복

버블 정렬의 성능

끝에 도달한 한 개의 수 씩 확정이 되므로 n-- 씩 진행
(n-1)+(n-2)+...+3+2+1

=> n(n-1)/2

버블 정렬 코드 (C)

#include <stdio.h>


void BubbleSort(int Data[], int LEN) {
	int boolean = 0;
	for (int i = 0; i < LEN; i++) {
		
		for (int j = 0; j < LEN-1; j++) {
			if (Data[j] > Data[j + 1]) {
				
				int Temp = Data[j];
				Data[j] = Data[j + 1];
				Data[j + 1] = Temp;
			}
		}

	
	}
}

int main(void) {
	int Data[] = { 6,1,3,2,5,4 };
	int LEN = sizeof Data / sizeof Data[0];
	
	BubbleSort(Data, LEN);
	
	for (int i = 0; i < LEN; i++) {
		printf("%d ", Data[i]);
	}

	return 0;
}

---

삽입 정렬

삽입 정렬이란?

순차적으로 순회하면서 순서에 어긋난 요소를 올바른 위치에 삽입해가는 정렬 알고리즘

삽입 정렬의 성능

삽입한 원소 하나씩 제거하므로
1+2+...+(n-2)+(n-1)

=> n(n-1)/2

삽입 정렬 코드 (C)

void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}


void Insert(int Data[], int LEN) {
	int j;
	for (int i = 0; i < LEN-1; i++) {
		j = i;
		while (Data[j] > Data[j + 1]) {
			Swap(&Data[j], &Data[j + 1]);
			j--;
		}
	}
}


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

	Insert(Data, LEN);
	
	for (int i = 0; i < LEN; i++) {
		printf("%d ", Data[i]);
	}

	return 0;
}

---

퀵 정렬

퀵 정렬이란?

기준 요소(Pivot) 선정을 해서 분활하여 각각 정렬하는 과정을 반복

퀵 정렬의 성능

O(N * LogN)

퀵 정렬의 주의사항

기준 요소 (Pivot)을 귀하는 과정이 필요.
1. 첫번째 요소를 기준으로 잡는다.
2. 첫번째부터 오른쪽으로 가면서 기준값보다 큰 값을 찾는다.
동시에 끝에서 왼쪽으로 가면서 기준값보다 작은 값을 찾는다.
3. 두 값을 찾고, 왼쪽이 오른쪽보다 작으면 서로 값을 교환.
3-2. 만약 왼쪽이 오른쪽과 같거나 크면 왼쪽에 있는 요소와 기준값 교환.
=> 그 기준값은 정렬 끝.

퀵 정렬 코드 (C)

#include <stdio.h>
void Swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int Partition(int Data[], int Left, int Right) {
	if (Left >= Right) { // 원소가 1개일 때
		return;
	}

	int Pivot = Left;
	int i = Left + 1;
	int j = Right;

	while (i <= j) { // 엇갈릴 때까지
		while (Data[i] <= Data[Pivot]) { // 왼쪽이 기준값보다 크기 전까지
			i++;
		}
		while (Data[j] >= Data[Pivot] && j > Left) { // 오른쪽이 기준값보다 작기 전까지
			j--;
		}
		
		if (i > j) { // 서로 엇갈리면, 기준값과 왼쪽에 있는 거 교환
			Swap(&Data[Pivot], &Data[j]);
			// 수행 후 반복문 탈출
		}
		else {// 안엇갈리면, 왼쪽과 오른쪽 교환
			Swap(&Data[i], &Data[j]);
			
		}
	}
	
    // 반복문(i > j, 즉 서로 엇갈리면 기준점이 옮겨진 위치 반환
	return j;
	
}

void QuickSort(int Data[], int Left, int Right) {
	if (Left < Right) {
		int idx = Partition(Data, Left, Right);

		
		QuickSort(Data, Left, idx - 1);
		QuickSort(Data, idx + 1, Right);
	}
}

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

	QuickSort(Data, 0, LEN - 1);

	for (int i = 0; i < LEN; i++) {
		printf("%d ", Data[i]);
	}

	return 0;
}