2. 선택 정렬(Selection Sort)

#정렬알고리즘 분류

*Stable

: 정렬할 자료들 중 동일한 두 자료의 상대적인 위치가 정렬 후에도 유지되는 정렬 알고리즘

*In-place

: 정렬할 자료를 저장하는 메모리 공간 이외에 추가로 사용하는 메모리 공간이 O(1)인 정렬 알고리즘

 

 

#선택 정렬 알고리즘

각 루프마다

 1. 최대(최소) 원소를 찾는다.

 2. 최대(최소) 원소와 마지막(가장 앞에 있는) 원소를 교환한다.

 3. 마지막(가장 앞에 있는) 원소를 제외한다.

하나의 원소만 남을 때까지 위의 루프를 반복한다.

 

ex)

5

2

4

1

3

3

2

4

1

5

3

2

1

4

5

1

2

3

4

5

1

2

3

4

5

 

 

#구현

#include <iostream>
using namespace std;

void selectionsort(int* a, int n);
void swap(int* a, int* b);

int main(){
    int n;
    cin>>n;
    int* a = new int[n];
    
    for(int i=0; i<n; i++)
    	cin>>a[i];
        
    seletcionsort(a, n);
    
    for(int i=0; i<n; i++)
    	cout<<a[i]<<" ";
	
    return 0;
}

void selectionsort(int* a, int n){
	for(int i=n-1; i>0; i--){
    	int maxIndex=0;
        for(int j=1; j<i; j++)
            if(a[maxIndex] < a[j]) maxIndex=j;
        swap(a[maxIndex],a[i]);
    }
}

void swap(int* a, int* b){
	int tmp = *a;
    *a = *b;
    *b = tmp;
}

//방법2

void seletionsort(int* a, int n){
	while(n>0){
    	int maxIndex=0;
        for(int i=1; i<n; i++){
		    if(a[maxIndex]<a[i]) maxIndex=i;
        swap(a[maxIndex], a[n-1]);
        n--;
    }
}

 

 

#시간복잡도 분석

원소 비교횟수 = n-1 + n-2 + n-3 + ... + 3 + 2 + 1 = n(n-1)/2

=> O(n*n)