1) 선택 정렬(Selection Sort)

---

알고리즘을 공부하기 시작하면 가장 처음으로 만나는게 '정렬' 문제이다. 정렬만큼 알고리즘의 효율성 차이를 극명하게 보여주는 것이 없기 때문이다.

<다음의 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요.>

(1, 10, 8, 3, 5, 4, 7, 9, 2, 6)

가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘을 생각해보자.
이 알고리즘을 '선택 정렬'이라고 한다. 가장 원시적이고 기초적인 방법.

#include <iostream>
using namespace std;

int main() {
	int min, temp, index;
	int array[10] = { 1, 10, 8, 3, 5, 4, 7, 9, 2, 6 };
	for (int i = 0; i < 10; i++)
	{
		min = 9999;
		for (int j = i; j < 10; j++)
		{
			if (min > array[j]) {
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;

	}
	for (int i = 0; i < 10; i++)
	{
		cout << array[i];

	}
}

---

min은 가장 작은 숫자를 판별하기 위해 일시적으로 삽입한 변수이고 temp는 배열에서 두 숫자의 위치를 바꿔주기 위한 임시 변수이다.

가장 중요한 것은 데이터의 갯수가 N개일때 총 몇 번의 비교 연산을 해야 되는지이다.

현재의 문제로 따졌을때, 1 ~ 10까지의 숫자를 정렬하려면
10 + 9 + 8 + ... + 1 즉 등차수열이다.
이를 식으로 표현하면 다음과 같다.

-> 10 * (10 + 1) / 2 = 55 
   (10개의 값을 계산하기 위해 총 55번 비교한다.)
-> N * ( N + 1) / 2 
   (여기서 작은 +1과 /2는 컴퓨터 연산에서 무시하게 된다.)
-> N * N

즉 시간 복잡도는 N^2으로 O(N^2)가 된다.
이는 데이터의 개수가 많아질수록 효율이 떨어지는 것이다.
선택 정렬은 매우 비효율적인 알고리즘이다.