선택정렬

가장 작은 것을 제일 앞으로 보낸다. 

-> 앞에서 부터 하나의 원소가 차례로 정렬된다. 이를 반복한다.

 

 

int Array[10] = {100, 32, 1, 23, 2, 5, 312, 33, 111, 122};

 

이 처럼 원소가 10개가 있다고 가정한다.

 

1단계 : 인덱스 바꾸지 않은 원소자리 ~ 9까지 반복해서 가장 작은 원소를 찾는다.

2단계 : 이 반복이 끝나고 그 인덱스를 기억하고 아직 바꾸지 않은 원소 자리와 바꾼다.

 

이 과정을 전체 원소의 갯수 만큼 반복처리 한다.

 

 

 

시간 복잡도 : N²

Why? 

등차수열로 시간 복잡도를 구할 수 있다.

N * (N + 1) / 2

가장 높은 항만 표시

N * N

 

등차수열로 계산 10 * (10 + 1) / 2 = 55

 

 

 

 

 

관련 코드

 

#include <iostream>

int main()
{
	int iMin, iIndex, iTemp;
	int arr[10] = {43, 653, 432, 53, 2, 1, 23, 1322, 32, 123};
	
	for (int i = 0; i < 10; i++)
	{
		iMin = 9999;
		for (int j = i; j < 10; j++)
		{
			if(iMin > arr[j])
			{
				iMin = arr[j];
				iIndex = j;				
			}
		}
		
		iTemp = arr[i];
		arr[i] = arr[iIndex];
		arr[iIndex] = iTemp;
	}
	
	for (int i = 0; i < 10; ++i)
	{
		std::cout << arr[i] << " ";	
	}
	
	return 0;
}

 

 

 

 

 

결과

 

1, 2, 5, 23, 32, 33, 100, 111, 122, 312