알고리즘-선택정렬

알고리즘에서 정렬을 하는 방법은 여러가지가 있다.
그중에 선택정렬에 대해 포스팅 해보려고 한다.
선택정렬은 배열에서 가장 왼쪽부터 기준값으로 잡고 정렬되지 않은 값들중 가장 작은값과 기준값을 서로 바꾼다.
그렇게 되면, 앞쪽은 계속해서 정렬되지 않은 값들중 가장 작은 값이 채워질 것이다.
그렇게 되면 가장 작은값부터 가장 큰 값이 자연스럽게 정렬되게 된다.

선택 정렬의 시간 복잡도

• 선택정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
• 구현 방식에 따라 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.
  N+(N-1)+(N-2)+...+2
• 이는 (N^2+N-2)/2 로 표현할 수 있다.
• 빅오 표기법에 따라 O(N^2) 가 시간 복잡도가 된다.

선택 정렬을 구현한 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n=10;
int arr[10]={2,5,6,7,8,9,1,3,4,10};
int target;
int main(){
    
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);
    
    for(int i=0;i<n;i++){
        target=i;
        for(int j=i+1;j<n;j++){
            if(arr[target]>arr[j]){
                target=j;
            }
        }
        swap(arr[i], arr[target]);
    }
    
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    
    
    return 0;
}

이해가 안되는 부분이 있다면 댓글로 남겨주세요 😊👍
오늘도 화이팅 입니다