선택 정렬(selection sort) 구현하기(c++)

idx값을 기준으로, idx+1부터 배열 끝까지 중 가장 작은 값과 idx값을 비교하여 

기준값이 더 크다면 위치를 바꿔주면 된다.

즉, idx값을 저장해놓고 바꾸는 식으로 진행된다.

 

*시간복잡도*

Best	Avg	Worst
O(n^2)	O(n^2)	O(n^2)

 

코드 첨부

// 선택 정렬 구현(오름차순)
#include <iostream>
#include <climits>
using namespace std;
 
// 초기 배열 상태
int arr[5] = {9, 6, 7, 3, 5};
 
void selection_sort(int arr[], int size)
{
    for(int i=0; i<size-1; i++){
        int MIN = INT_MAX;
        int IDX;
        for(int j=i+1; j<size; j++){
            if(MIN>arr[j]){
                MIN = arr[j];
                IDX = j;
            }
        }
 
        if(arr[i]>MIN){
            // i와 IDX위치의 값을 바꿔준다.
            int temp = arr[i];
            arr[i] = arr[IDX];
            arr[IDX] = temp;
        }
    }
}
 
int main()
{
    selection_sort(arr, 5);
 
    for(int i=0; i<5; i++){
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
}

 

 

위의 표는 아래 블로그에서 참조했습니다.

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog