250911 - selectionSort : correctness

selection sort

선택정렬 :

#include<vector>

void selectionSort(std::vector<int> nums){
	for(int i=0;i<nums.size();i++){
    	int ind = i;
        for(int j=i+1;j<nums.size();j++){
        	if(nums[ind] > nums[j])
            	ind = j;
        }
        int tmp = nums[ind];
        nums[ind] = nums[i];
        nums[i] = tmp;
    }
}

 

i 번째 outer loop 를 돌고 나면, nums[0, ..., i] 가 오름차순으로 정렬되어 있다.

 

i = 0 ) nums[0] 는 숫자 1개이므로 정렬된 상태라고 볼 수 있다.

i-1번째 루프가 끝난 후, nums[0, ..., i-1] 은 정렬되어 있다고 가정한다.

i > 0 ) inner loop는 i부터 nums.size()-1(end) 까지, 가장 작은 값을 찾아 해당 인덱스 번호로 ind 값을 갱신한다. inner loop 가 끝난 뒤, tmp 변수를 사용해 num[i] 와 num[ind] 값을 swap 한다.

그럼 i번째 outer loop를 돈 이후에는 nums[i] 는 nums[i, ..., end] 중 최소값이 된다.

귀납 가정에 의해 nums[0, ..., i-1] 은 이미 정렬된 상태이다.

nums[i] 는 그 다음으로 작은 원소가 되며, 따라서 nums[0, ..., i] 는 오름차순으로 정렬됨을 알 수 있다.