선택 정렬(Selection Sort)

선택 정렬 알고리즘 개념

 

선택 정렬은 원리가 간단하다 우선 배열 Arr[1......n]에서 가장 큰 원소를 찾아 이 원소와 배열의 끝자리에 있는 A[n]과 자리를 바꾼다. 방금 바뀐 맨 뒷자리 원소, 가장 큰 원소는 자기 자리를 찾았으므로 더 이상 신경 쓰지 않아도 된다. 이제 이원소를 제외한 나머지 원소들도 같은 작업을 반복하면 된다.

 

ex)

 

1   5   20   4   3  --> 정렬할 배열이 주어진다.

 

가장 큰수인 20을 찾는다

 

20을 맨 오른쪽 수와 자리 바꾼다.

 

1   5   3   4   20 

 

맨 오른쪽 수를 제외한 나머지에서 가장 큰 수를 찾는다.

1   5   3   4  -->5

 

5를 맨 오른쪽 수와 자리 바꾼다

 

1    4    3    5 

 

이를 반복한다 

 

선택 정렬의 수행 시간은 모든 경우에 대해서 O(n^2)이다. 

 

 

소스코드

 

#include <iostream>

using namespace std; 

void SelectionSort(int arr[], int MAX) { 
int i, j; 
int max; //최대값 설정
for (i = MAX-1; i >= 0; i--) { // 배열의 끝부터 시작하는 for문
max = i; 
for (j = 0; j < i; j++) { //첫번째부터 배열의 끝이 점점 줄어드는 for문
if (arr[j] > arr[max]) max = j;  //j 는 현재 값 max는 배열의 끝 값 
} 
swap(arr[i], arr[max]); // j for문이 끝날때마다 스왑을 해준다. 
} 
}


int main() {
int y[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int size3 = sizeof(y) / sizeof(y[0]);
SelectionSort(y, size3);
for (int i = 0; i < size3; i++) { 
cout << y[i] << " "; 
}
return 0; 
}

 

결과 값