선택 정렬

 

정렬

 

다음 숫자들을 오름차순 정렬하시오

> 1 10 5 8 7 6 4 3 2 9

 

사람이라면 쓱 보고 순서대로 쓰겠지만 컴퓨터는 그게 가능하지 않다 그러기에 알고리즘을 정의해주어야 한다

 

선택정렬

 

가장 작은 것을 선택해 가장 앞으로 보내는 알고리즘을 생각해본다면 이것은 선택정렬이라고 할 수 있다. 가장 원시적이고 기초적인 알고리즘이다

#include<bits/stdc++.h>
using namespace std;

int main()
{
  int min,index,temp;
  int arr[10] = {1,10,5,8,7,6,4,3,2,9};
  for(int i=0; i<10; i++){
    min=9999;
    for(int j=i; j<10; j++){
      if(arr[j]<min){
        min = arr[j];
        index = j;
      }
    }
    temp = arr[i];
    arr[i] = arr[index];
    arr[index] = temp;
  }
  for(int i=0; i<10; i++)
    cout << arr[i] << ' ';
  return 0;
}

 

실행시켜보면 알겠지만 잘 실행된다는 것을 알 수 있다.

사진 삭제

사진 설명을 입력하세요.

 

시간복잡도

선택정렬의 시간복잡도는 O(N^2)이다.

 

10개의 수에서 가장 작은 수를 고르는 경우 10개

그 다음 남은 9개중에서 고르는 경우 9개

 

10 + 9 + 8 .... + 1 이라는 경우를 정리하면

 

10 x (10+1) / 2 = 55 가 되고 이를 정리하면

=> N * (N + 1) / 2

=> O(NxN) => O(N^2) 가 된다고 할 수 있다.

 

 

빅오표기법에서 간단한 사칙연산은 무시