1) 알고리즘 : 정렬 - 선택정렬(selection sort)

- 선택정렬 : 전체 배열 중 가장 작은 것을 선택해서 맨 앞으로 보내는 것 (맨 앞에 숫자는 제일 작은 것에 있던 숫자의 자리로 값을 스와핑한다.)

 

5 2 6 1 3 4

1 2 6 5 3 4

1 2 6 5 3 4

1 2 3 5 6 4

1 2 3 4 6 5

1 2 3 4 5 6

 

- 1회차 : 6번 비교

- 2회차 : 5번 비교

- 3회차 : 4번 비교 ...

 

=> 6 + 5 + 4 + 3 + 2 + 1 (등차수열)

=> n*(n-1) / 2 (컴퓨터에서는 가장 큰 차수만 보기 때문에 -1 과 /2 제거)

=> n*n

=> 시간 복잡도 ? 데이터가 N개 일때 총 몇 번의 비교 연산을 하는가

 

시간복잡도 빅오 : O(N^2)

데이터가 10000개면 약 1억번 계산해야하는 비효율적인 알고리즘

 

 

//선택정렬 Selection Sort

#include <iostream>
using namespace std;

int main(void) {

	int min, index, temp;
	int array[6] = { 5,2,6,1,3,4 };

	for (int i = 0; i < 6; i++) {
		min = 999;
		for (int j = i; j < 6; j++) {
			if (array[j] < min) { //가장 작은 수 찾는 파트
				min = array[j];
				index = j;
			}
		}

		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}

	for (int i = 0; i < 6; i++)
		cout << array[i] << " ";

	return 0;
}