[알고리즘] 선택 정렬(selection sort)(C++)

📌선택 정렬 : 가장 작은 값을 '선택'하여 정렬하는 알고리즘

✏️ 선택 정렬(selection sort) 알고리즘

• 오름차순 기준 정렬
• 해당 순서에 원소를 넣을 위치는 이미 정해짐, 어떤 원소를 넣을지 선택
  1. 첫 번째 순서에는 가장 작은 원소를 선택, 첫 번째 idx에 넣는다.
  2. 두 번째 순서에는 남은 값중 가장 작은 원소를 선택, 두 번째 idx에 넣는다.

• 상세 과정
  1. 첫 번째 인덱스를 기준으로 주어진 배열의 모든 원소를 비교하여 최솟값을 찾는다.
  2. 최솟 값을 첫 번째 값과 교체.
  3. 두 번째 인덱스 ~ 나머지 값을 같은 방법으로 교체.
  4. 하나의 원소가 남을 때까지 1-3 과정을 반복한다.(마지막 원소 자동 정렬)

💻 선택 정렬(selection sort) C++ 구현 코드

#include<iostream>
#include<vector>

void selectionSort(vector<int> &v){         #vector의 주소를 매개변수로 넘겨 받아야 원본이 변경됨
	for(int i=0; i<v.size()-1; i++){    #마지막 원소는 자동 정렬이므로 vector의 크기 -1
   	int key = i;
       for(int j = i+1; j<v.size(); j++){
       	if(v[j]<v[key]){
           	key = j;
           }
       if( i != key){			     #자기자신이 최솟값이면 교체X
       	swap(v[i], v[key])
           }
       }
    }
}

✏️ 선택 정렬의 시간 복잡도

1. 비교 횟수

• 두 개의 for 문 실행
  외부 for문 : (n-1)번
  내부 for문 : n-1, n-2,..., 2, 1번

2. 교체 횟수

• 외부 루프의 실행 횟수와 같다.
• 한 번 교체하기 위하여 3번의 이동(swap)이 필요하므로 3(n-1)번

3. T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)