정렬 알고리즘 1

1) 버블 정렬 (Bubble sort)

인접한 두 원소를 비교해가며 정렬하는 방법이다.

공간 복잡도

• O(1)

시간 복잡도

• 최선의 경우 : O(n²)
• 평균의 경우 : O(n²)
• 최악의 경우 : O(n²)

2) 삽입 정렬 (Insertion sort)

0부터 n까지 인덱스 i가 진행될 때, i-1부터 0까지 탐색하여 삽입할 곳을 찾는 방법이다.

공간 복잡도

• O(1)

시간 복잡도

• 최선의 경우 : O(n)
• 평균의 경우 : O(n²)
• 최악의 경우 : O(n²)

3) 선택 정렬 (Selection sort)

최소 선택 정렬과 최대 선택 정렬이 있다. 현재 인덱스 i의 값과 i~n 중 최소값을 swap하여 정렬하는 방법이다.

공간 복잡도

• O(1)

시간 복잡도

• 최선의 경우 : O(n²)
• 평균의 경우 : O(n²)
• 최악의 경우 : O(n²)

- 코드 구현

#include <iostream>

using namespace std;

void Bubble_sort(int (&a)[10], int n)
{
	int tmp;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (a[i] > a[j])
			{
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			}
		}
	}
}

void Insertion_sort(int(&a)[10], int n)
{
	int i, j, key;
	for (i = 1; i < n; i++)
	{
		key = a[i];
		
		for (j = i - 1; j >= 0 && a[j] > key; j--)
		{
			a[j + 1] = a[j];
			
		}
		a[j+1] = key;
	}
}

void Selection_sort(int (&a)[10], int n)
{
	int min, min_idx, tmp;
	for (int i = 0; i < n; i++)
	{
		min = a[i];
		min_idx = i;
		for (int j = i + 1; j < n; j++)
		{
			if (min > a[j])
			{
				min = a[j];
				min_idx = j;
			}
		}
		tmp = a[i];
		a[i] = min;
		a[min_idx] = tmp;
	}
}

int main(void)
{
	int a[10] = { 9, 5, 3, 4, 6, 7, 1, 10, 2, 8 };
	Bubble_sort(a, 10);
	//Insertion_sort(a, 10);
	//Selection_sort(a, 10);
	for (int i = 0; i < 10; i++)
	{
		cout << a[i] << " ";
	}
	return 0;
}