선택 정렬

1. selection sort 선택 정렬

: 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택해서 가장 앞의 데이터와 swap하는 방식이다.

실제로는 사용자가 설정하는 것에 따라 달라지지만 왼쪽부터 정렬되는 것을 기본으로 생각하자. 

 

 

arr[0]을 최소값으로 설정

arr[1], arr[2], arr[3], arr[4]과 비교

arr[0]보다 작은 값이 있으면 최소값으로 설정

 

최소값을

arr[2], arr[3], arr[4]과 비교

최소값으로 설정된 값보다 작은 값이 있으면 최소값이 바뀜

 

 

15 > 11, 11 > 1, 1 < 3, 1< 8

 

---

실습

 

 

1. 제일 작은 숫자를 찾기 위해 순차적으로 이동

 

2. outer loop가 한번 돌때마다 element 하나의 최종위치가 확정된다.

(확정된 요소 다음 요소들만큼 inner loop가 돌 때마다 element 하나의 최종위치가 확정된다.)

 

3. 탐색범위

outer loop : 0 ~ n-1

첫번째 요소를 최솟값으로 가정함

 

inner loop : 0 ~ i+1

이미 정렬된 부분을 제외

 

4. time complexity 시간 복잡도

최악worst : O(n^2)

평균average : O(n^2)

최고best : O(n^2)

 

c언어 코드

for ( i = 0; i < n-1; i++ ){
	min = i;
    for( j = i + 1; j < n; j++ )
    	if (arr[j] < arr[min])
        	min = j;
    swap(&arr[min], &arr[i]);
}

 

파이선 코드