[알고리즘] 정렬(sorting) - 선택정렬(selection sort)

🔨 선택 정렬

선택하여 정렬하는 알고리즘으로, 최소값을 선택하여 앞부터 채워나가는 정렬 방법

👉 개념 요약

• 제자리 정렬(in-place sortring) 알고리즘의 하나
• 해당 순서에 원소를 넣을 위치는 정해져 있으며, 어떤 원소를 넣을 것인지 선택하는 알고리즘
• 선택정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가하는 정렬방법

👉 실행

{5, 10, 2, 1, 17, 6 } 이란 배열이 주어졌을 때

1. 배열의 첫번째 자리(5)에서 시작
2. 가장 작은 원소 찾기 (5를 {10, 2, 1, 17, 6}에서의 최소값과 비교)
3. 1이 가장 작은 값이기 때문에 5의 위치와 교환
=> {1, 10, 2, 5, 17, 6}
=>첫번째 자리는 정렬된 상태, 두번째 이후는 정렬이 되지 않은 상태
4. 위의 과정을 정렬되지 않은 상태의 첫번째 자리부터 다시 반복

👉 코드 구현

void selection_sort(int arr[], int n){
  int least_id, temp;

  // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복
  for(int i=0; i<n-1; i++){
    least_id = i;

    // 최솟값을 탐색
    for(int j=i+1; j<n; j++){ //비교 대상 i 보다 큰 i+1 부터 탐색
      if(arr[j]<arr[least_id])
        least_id = j;
    }

    // i 보다 작은 최솟값이 존재한다면 교환
    if(i != least_id){
        temp = arr[i];
        arr[i] = arr[least_id];
        arr[least_id] = temp;
    }
  }
}

👉 선택정렬 알고리즘 시간 복잡도

< 시간 복잡도 계산 >

• 비교 횟수
  - 두개의 for루프
  - 외부 루프 : n-1 번
  - 내부 루프 : n-1, n-2, n-3, ...2, 1번
• 교환 횟수
  - 외부 루프의 실행횟수와 동일(n-1) => 상수 시간 작업
  - swap 과정에서 필요한 세번의 이동 => 3(n-1)

• T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)
• 내부 루프 O(n), 외부 루프 O(n) = O(n^2)

다음 표를 보면 (삽입정렬,선택정렬, 버블정렬)은
다른 정렬에 비해 비효율적이다는 것을 알수있다.
하지만 코드 구현이 간단하다는 장점이 있다.

👉 선택정렬 알고리즘 특징

• 장점
  - 자료 이동 횟수가 미리 결정된다.
• 단점
  - 같은 값의 자료가 있는 경우 상대적인 위치가 변경될 수 있다.
  • 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교와 교환이 필요하다.

👉 관련된 post

• 삽입 정렬(insertion sort) : Insertion Sort