정렬 알고리즘 (Sorting Algorithms) - 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

선택 정렬은 단순하지만 비효율적인 정렬 알고리즘으로, 배열의 모든 요소를 반복하면서 가장 작은 값을 찾아 해당 값을 정렬되지 않은 부분의 첫 번째 요소와 교환하는 방식으로 동작합니다.

---

1. 작동 방식

1. 배열의 첫 번째 요소를 정렬되지 않은 부분의 시작점으로 간주합니다.
2. 정렬되지 않은 부분에서 가장 작은(혹은 가장 큰) 값을 찾습니다.
3. 해당 값을 정렬되지 않은 부분의 첫 번째 요소와 교환합니다.
4. 정렬되지 않은 부분의 시작점을 다음 요소로 이동합니다.
5. 배열의 모든 요소가 정렬될 때까지 반복합니다.

---

2. 특징

• 시간 복잡도:
  • 최선, 평균, 최악: O(n^2)
• 공간 복잡도:
  • 추가 메모리 사용이 거의 없음: O(1)
• 불안정 정렬:
  • 데이터의 상대적인 순서를 보장하지 않습니다.

---

3. 작동 예제

배열: [64, 25, 12, 22, 11]

1. 첫 번째 반복:
   • 최소값: 11
   • 교환: 11과 64 → [11, 25, 12, 22, 64]
2. 두 번째 반복:
   • 최소값: 12
   • 교환: 12와 25 → [11, 12, 25, 22, 64]
3. 세 번째 반복:
   • 최소값: 22
   • 교환: 22와 25 → [11, 12, 22, 25, 64]
4. 네 번째 반복:
   • 최소값: 25
   • 교환: 25와 25 → [11, 12, 22, 25, 64]
5. 다섯 번째 반복:
   • 정렬 완료.

---

4. 장점과 단점

장점:

• 구현이 간단하고 이해하기 쉽습니다.
• 추가 메모리를 거의 사용하지 않습니다.

단점:

• 시간 복잡도가 O(n^2)이므로, 데이터 크기가 커질수록 비효율적입니다.
• 정렬의 안정성이 없습니다.

반응형

---

5. Java 예제 코드

import java.util.Arrays;

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // 하나씩 배열의 요소를 정렬
        for (int i = 0; i < n - 1; i++) {
            // 정렬되지 않은 부분에서 최소값 찾기
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 최소값을 현재 위치와 교환
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("Original Array: " + Arrays.toString(arr));

        selectionSort(arr);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python 예제 코드

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find the index of the smallest element in the unsorted part
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # Swap the smallest element with the first element of the unsorted part
        arr[i], arr[min_index] = arr[min_index], arr[i]

# Example usage
if __name__ == "__main__":
    arr = [64, 25, 12, 22, 11]
    print("Original Array:", arr)

    selection_sort(arr)

    print("Sorted Array:", arr)

---

7. 동작 최적화

• 최적화된 루프 종료:
  • 현재 정렬된 부분에서 더 이상 교환이 필요하지 않으면 중단.
• 불필요한 교환 최소화:
  • 값이 이미 제자리일 경우, 교환을 생략하여 실행 시간을 줄일 수 있음.

---

8. 활용 사례

• 데이터 크기가 작거나, 간단한 정렬 알고리즘이 필요한 경우.
• 추가 메모리 사용을 피해야 할 경우.

선택 정렬은 이해하기 쉬운 알고리즘이지만, 성능이 좋지 않아 실무보다는 학습용이나 데이터 크기가 작은 상황에서 주로 사용됩니다.