개발뚱땅

선택 정렬 (Selection Sort)

선택정렬은 반복적으로 정렬되지 않은 영역을 찾고, 정렬되지 않은 영역 내부에서 최소(최대)값을 찾아 영역 내의 제일 앞에 배치하여 정렬합니다.

이 알고리즘은 주어진 배열을 두개의 영역으로 나누어 사용합니다.

1) 이미 정렬된 영역

2) 아직 정렬되지 않은 영역

정렬의 매 순간 마다 정렬되지 않은 영역의 최소(최대) 원소는 선택되어 정렬된 영역으로 이동됩니다.

예)

{64, 25, 12, 22, 11}라는 배열이 주어진다면

처음엔 정렬된 영역{}, 정렬되지 않은 영역{64, 25, 12, 22, 11}으로 이루어지고,

오름차순을 가정

최소값을 찾아 정렬된 영역으로 이동 시킵니다.

{11}, 그럼 정렬되지 않은 영역에는 {64, 25, 12, 22}이 들어있습니다.

두번째엔

{11, 12}, {64, 25, 22}

...

{11, 12, 22}, {64, 25}

{11, 12, 22, 25}, {64}

{11, 12, 22, 25, 64} 순으로 정렬이 됩니다.

#include <bits/stdc++.h> 
using namespace std; 

void swap(int *xp, int *yp) 
{ 
	int temp = *xp; 
	*xp = *yp; 
	*yp = temp; 
} 

void selectionSort(int arr[], int n) 
{ 
	for(int i = 0; i<n-1;i++){
		int minidx = i;
		
		for(int j=i+1; j<n;j++){
			if(arr[minidx] > arr[j]){
				minidx = j;
			}
		}
		swap(&arr[i], &arr[minidx]);
	}
} 

void printArray(int arr[], int size) 
{ 	
	for (int i=0; i < size; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

int main() 
{ 
	int arr[] = {64, 25, 12, 22, 11}; 
	int n = sizeof(arr)/sizeof(int); 
	selectionSort(arr, n); 
	cout << "Sorted array: \n"; 
	printArray(arr, n); 
	return 0; 
}

시간복잡도: O(n^2) 2개의 루프문 때문.

불안정 정렬.

추가공간을 사용하지 않기에 제자리 정렬이다.

"선택 정렬은 정렬해야하는 원소를 선택해서 정렬된 영역으로 이동시켜 정렬한다."