[알고리즘] 선택 정렬(Selection Sort)

숫자 배열 7 3 2 1 4 가 있을 때 선택정렬의 진행순서는 아래와 같다.

1 3 2 7 4  ->   1 2 3 7 4  ->  1 2 3 4 7

 

아주 쉽게 설명하면 범위 안의 숫자 중 가장 작은 숫자를 맨 앞에 숫자와 바꾸고 범위를 하나씩 좁히는 식의 정렬 방법이다.  

시간 복잡도는 O(N^2)임으로 굉장히 좋지 못하다.

 

//  				 Selection Sort

#include<iostream>
#include<time.h>

int main(){
	clock_t start, end;
	double result;
	
	start = clock();
	int N;
	std::cout << "Plz enter the array numbers : ";
	std::cin >> N;
	
	int* arr = new int[N];
	std::cout << "Now enter all the elements of your array : ";
	for(int i = 0; i < N; i++){
		std::cin >> arr[i];
	}
	
	char show_process;
	while(1){
		std::cout << "Do u want to see the process?[y/n] : ";
		std::cin >> show_process;
		if(show_process == 'y' || show_process == 'n'){
			break;
			std::cout << "Plz enter between 'y' and 'n' " << '\n';
		}
		else
			std::cout << "Plz enter between 'y' and 'n' " << '\n';
		
	}
	
	int min = 2147483647;			// 2147483647 = 2^32 - 1
	int index, temp;
	for(int i = 0; i < N; i++){
		min = 2147483647;
		for(int j = i; j < N ; j++){
			if(arr[j] < min){
				min = arr[j];
				index = j;	
			}
		}
		temp = arr[index];
		arr[index] = arr[i];
		arr[i] = temp;
		if(show_process == 'y'){
			std::cout << i+1 << " round : ";
			for(int z = 0; z < N; z++){
				std::cout << arr[z] << " ";
			}
			std::cout << '\n';
		}
	}
	
	std::cout << "The final result is : ";
	for(int i = 0; i < N; i++){
		std::cout << arr[i] << " ";
	}
	std::cout << '\n';
	
	end = clock();
	result = (double)(end-start);
	std::cout << "Compile time : " << result << "ms"<< "\n";
	return 0;
}

위 코드는 각 반복문마다 어떻게 숫자들이 정렬되는지 알 수 있게 설정해놓았다. 만약 정렬 시간을 정확히 알고 싶다면 정렬한 숫자를 출력하는 절차는 꺼주고 실행하길 바란다.

 

아주 간단한 알고리즘임으로 이해하기 쉽다.