선택 정렬 (Selection Sort)

알고리즘 문제에서 정렬(Sort)는 중요한 기술이다.

여러가지 정렬 알고리즘이 있지만 기본적인 것 부터 하나하나 알아보자.

 

선택 정렬 (Selection Sort)

 

 단순한 정렬 알고리즘 중 하나이다.

 

배열의 첫 번째 원소에서 시작하여 배열 전체를 훓으면서 작은(큰) 값을 찾아 첫 번째 원소와 바꿔준다.

 

이 작업을 (배열의 길이 - 1 ) 만큼 진행한다.

 

선택 정렬은 Best, Average, Worst Case 모두 O(N^2) 의 효율이다

 

 - 원소를 바꾸는 횟수가 최대 n -1 이다. 즉 원소를 바꾸는 과정에서 많은 비용이 드는 경우에 효율적일 수 있다.

 - 선택 정렬은 다른 알고리즘에 비해 효율(performance) 가 좋지 않다.

 - stable을 만족하지 않는다.

 

#include <iostream>

using namespace std;

void selection_sort(int data[], int size);
void swap(int& a, int& b);

int main() {
  	int data[] = {3,7,9,4,5,1,3,4,6,9};
  	selection_sort(data,10);
  	for (int i = 0; i < 10; i++) cout << data[i] << " ";
  	return 0;
}

void selection_sort(int data[], int size) {
  	for (int i = 0; i < size - 1; i++) {
  		int min = i;
  		for (int j = i + 1; j < size; j++) {
  			if (data[min] > data[j]) min = j;
  		}
  		swap(data[min], data[i]);
  	}
}

void swap(int& a, int& b) {
  	int temp = a;
  	a = b;
  	b = temp;
}