선택정렬(Selection Sort)

선택정렬은 가장 작은 것을 선택해서 제일 앞으로 보내는 것이다.

 

1 10 5 8 7 6 4 3 2 9 --> 가장 앞에 있는 1이 가장 작은 수이기 때문에 정렬이 이루어졌다.

 

1 10 5 8 7 6 4 3 2 9 --> 1 2 5 8 7 6 4 3 10 9  --> 나머지 9개의 수 중에 가장작은 수인 2와 10의 위치를 바꾼다. 

 

1 2 5 8 7 6 4 3 10 9 --> 1 2 3 8 7 6 4 5 10 9 --> 나머지 8개의 수 중에 가장 작은 수인 3과 5의 위치를 바꾼다.

 

1 2 3 8 7 6 4 5 10 9 --> 1 2 3 4 7 6 8 5 10 9 --> 나머지 7개의 수 중에 가장 작은 수인 4와 8의 위치를 바꾼다.

 

1 2 3 4 7 6 8 5 10 9 -->  1 2 3 4 5 6 8 7 10 9 --> 나머지 6개의 수 중에 가장 작은 수인 5와 7의 위치를 바꾼다.

 

1 2 3 4 5 6 8 7 10 9 --> 나머지 5개의 수 중에 가장 작은 수인 6이 가장 앞에 있기 때문에 정렬 완료

 

1 2 3 4 5 6 8 7 10 9 --> 1 2 3 4 5 6 7 8 10 9 --> 나머지 4개의 수 중에 가장 작은 수인 7과 8의 위치를 바꾼다.

 

1 2 3 4 5 6 7 8 10 9 --> 나머지 3개의 수 중에 가장 작은 수인 8이 가장 앞에 있기 때문에 정렬 완료

 

1 2 3 4 5 6 7 8 10 9 --> 1 2 3 4 5 6 7 8 9 10 --> 나머지 2개의 수 중에 가장 작은 수인 9와 10의 자리를 바꾼다.

 

1 2 3 4 5 6 7 8 9 10 --> 마지막 수가 가장 큰 수임을 확인한다.

 

정렬 결과 : 1 2 3 4 5 6 7 8 9 10 

 

[예제]

#include <stdio.h>

int main() {
    int i, j, min, index, temp;
	int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
	for(i=0; i<10; i++) {
		min = 9999;
		for(j=i; j<10; j++) {
			if(min > array[j]) {
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	} 
	for(i = 0; i<10; i++) {
		printf("%d ", array[i]);
	}
}

<변수>

i, j : 배열에 있는 원소들을 반복적으로 탐색하기 위해 사용되는 변수

min : 최소값 (최소값을 담아야 하기 때문에 초기값을 큰 값으로 넣어준다.)

index : 가장 작은 원소가 존재하는 위치

temp : 특정한 두 수를 서로 바꾸기 위해 사용되는 변수

 

 

for문을 통해 현재 탐색하고 있는 원소가 현재 최소값보다 더 작다면 최소값 변수 min에 현재 탐색하고 있는 원소의

 

값을 넣어준 뒤 index에 해당 위치 값을 넣어준다. 

 

한 번 탐색이 끝났을 때 가장 작은 값이 선택된 상태라면 그 값을 가장 앞으로 보내준다.

 

변수 temp를 활용하여 두 개의 원소값 위치를 바꿔준다. 즉, 가장 앞에 있는 값과 최소값을 바꾼다.

 

[결과]

선택정렬(Selection Sort) 결과

[선택 정렬의 시간 복잡도]

선택 정렬의 시간 복잡도는 O(N^2) 이다. 

 

1 2 3 4 5 6 7 8 9 10 와 같이 10개의 수가 있다면,

 

(1) 처음에 1~10까지 확인하기 위해 10번을 확인한다.

(2) 두번째 값 부터 마지막까지 살펴보기 위해 9번을 확인한다.

(3) 세번째 값 부터 마지막까지 살펴보기 위해 8번을 확인한다.

.

.

.

(4) 마지막 수를 확인한다.

즉, 이러한 과정을 표현하면 10 + 9 + 8 + ... + 1 = 55번이며, 10 * (10 + 1) / 2 와 같은 공식으로 풀 수 있다.

결과적으로, 총 10개의 정렬 계산을 위해서 최소한 55번의 비교 연산을 해야한다.

10 * (10 + 1) / 2 와 같은 공식을 수식으로 표현하면 N * (N+1) / 2 로 표현된다. 

컴퓨터에서는 위와 같이 2로 나눈 값같은 경우에는 N이 굉장히 크다는 가정 하에 별 의미가 없기 때문에 간단하게

나누거나 더하는 연산들은 다 무시한다. 그렇기 때문에 수식을 쉽게 표현하면 N*N 이며, 

시간 복잡도는 O(N^2)를 만족하는 것이다.

 

[소감]

기존에는 각 정렬에 대한 시간 복잡도를 무작정 외우기만 했었는데, 이번 학습을 통해 시간 복잡도를 만족시키는

 

과정을 차근차근 알 수 있었다. 다음 정렬 알고리즘에 대한 학습도 기대가 된다.

---

출처

https://blog.naver.com/ndb796/221226800661

2. 정렬의 개요와 선택 정렬(Selection Sort)