[Algorithm] Selection Sort(선택 정렬)

[Algorithm] Selection Sort(선택 정렬)

1. 정의

• 배열에서 자리를 선택한 후 특정 값을 찾아 교환하면서 정렬하는 방법
  • 오름차순일 경우 뒷 부분에서 가장 작은 값을 찾아서 교환한다.
• 시간복잡도
  • 최선 : $O(n^2)$
  • 평균 : $O(n^2)$
  • 최악 : $O(n^2)$

2. 동작 과정(오름차순)

1. 주어진 배열 중에 최소값을 찾는다.
2. 찾은 값을 첫번째 원소와 교환한다. → 첫번째 원소는 정렬되어 있는 상태가 됨
3. 정렬된 원소를 제외하고 가장 최소값을 찾아 정렬이 안된 첫번째 원소와 교환한다.
4. 반복

3. 장단점

• 장점
  • 자료 이동 횟수가 미리 결정 됨
  • 제자리 정렬
• 단점
  • 안정성을 만족하지 않음 → 상대적 위치가 바뀜
    • 같은 원소가 중복되어 있으면 중복된 원소의 순서를 보장하지 않음
  • 효율성이 떨어짐

4. 코드

void selectionSort(int[] arr) {
   for (int i = 0; i < arr.length - 1; i++) {
      int minIndex = i; // 현재 인덱스 값을 가장 작은 값으로 설정

      for(int j = i + 1; j < arr.length; j++) { 
         if (arr[j] < arr[minIndex]) { // 탐색하여 현재 최소 인덱스의 값보다 더 작으면
            minIndex = j; // 최소 인덱스의 값을 j로 바꿈
         }
      } 

      swap(arr, i, minIndex); // 교환
   }
}

void swap(int[] arr, int from, int to) {
   int tmp = arr[to];
   arr[to] = arr[from];
   arr[from] = arr[to];
}

---

※ 참고

• tech-refrigerator 선택 정렬 (Selection Sort)
• [알고리즘] 선택 정렬(selection sort)이란