[Algorithm] Selection Sort(선택 정렬)

Code

python

def selection_sort(a):
    for i in range(0, len(a)-1):
        minimum=i;
        for j in range(i, len(a)):
            if(a[minimum] > a[j]):
                minimum=j;
        a[i], a[minimum] = a[minimum], a[i]

a = [10, 4, 5, 1, 8, 6, 2, 7, 9, 3]

print(a)
selection_sort(a)
print(a)

 

c++

#include <iostream>

using namespace std;

const int ARRAY_SIZE = 10;

void selection_sort(int a[]){
  for(int i=0; i<ARRAY_SIZE-1; i++){
    int minimum=i;
    for(int j=i; j<ARRAY_SIZE; j++){
      if(a[minimum]>a[j]) minimum=j;
    }
    swap(a[i], a[minimum]);
  }
}

int main(){
  int a[ARRAY_SIZE] = {10, 4, 5, 1, 8, 6, 2, 7, 9, 3};

  for(int i=0; i<ARRAY_SIZE; i++){
    cout << a[i] << ' ';
  }
  cout << '\n';
  selection_sort(a);
  for(int i=0; i<ARRAY_SIZE; i++){
    cout << a[i] << ' ';
  }
  return 0;
}

정리

아이디어

1. 전체 값 중에 가장 작은 값 선택

2. 선택한 값을 i번째 위치시킴 (i=0부터 배열사이즈-1까지 순서대로)

3. 1, 2번 반복

 

시간복잡도

항상 n-1, n-2, .. 2, 1번 비교연산

→ n*(n-1)/2번 연산

→ O(n^2)