선택 정렬 (Selection Sort) 총 정리 - 개념, 원리, 동작 예시, 시간복잡도, C언어, Java, Python 예제코드, 주의점, 장단점

선택 정렬(Selection Sort)

 

 

 

 

1. 선택 정렬이란?

선택 정렬은 정렬되지 않은 리스트에서 가장 작은(또는 큰) 값을 찾아 맨 앞에 위치시키는 과정을 반복하여 정렬하는 알고리즘입니다. 구현이 간단하지만, 데이터 크기가 커질수록 성능이 떨어질 수 있습니다.

---

 

 

2. 원리

1. 정렬되지 않은 배열에서 최소값(또는 최대값)을 찾습니다.
2. 최소값을 배열의 첫 번째 요소와 교환합니다.
3. 나머지 배열에 대해 위 과정을 반복합니다.
4. 모든 요소가 정렬될 때까지 계속합니다.

---

 

 

3. 동작 예시 (구체적인 설명)

정렬할 배열: [5, 3, 8, 4, 2]

1. 첫 번째 단계:
   • 배열에서 최소값 2를 찾습니다.
   • 2와 첫 번째 요소 5를 교환합니다.
   • 결과: [2, 3, 8, 4, 5]
2. 두 번째 단계:
   • 나머지 배열 [3, 8, 4, 5]에서 최소값 3을 찾습니다.
   • 3은 이미 두 번째 위치에 있으므로 교환하지 않습니다.
   • 결과: [2, 3, 8, 4, 5]
3. 세 번째 단계:
   • 나머지 배열 [8, 4, 5]에서 최소값 4를 찾습니다.
   • 4와 8을 교환합니다.
   • 결과: [2, 3, 4, 8, 5]
4. 네 번째 단계:
   • 나머지 배열 [8, 5]에서 최소값 5를 찾습니다.
   • 5와 8을 교환합니다.
   • 결과: [2, 3, 4, 5, 8]

최종 정렬 결과: [2, 3, 4, 5, 8]

반응형

---

 

 

4. 시간 복잡도

• 최선의 경우: O(n²)
• 평균적인 경우: O(n²)
• 최악의 경우: O(n²)

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    selectionSort(arr, n);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

 

Java 코드

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        
        selectionSort(arr);
        
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

Python 코드

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

arr = [5, 3, 8, 4, 2]
selection_sort(arr)
print(arr)

---

 

 

6. 주의점

1. 데이터가 많을 경우 성능이 좋지 않으므로, 효율성이 중요한 프로젝트에는 적합하지 않습니다.
2. 안정 정렬이 아니기 때문에 동일한 값의 순서가 변경될 수 있습니다.

---

 

 

7. 장단점

장점

• 간단하고 직관적인 구조.
• 데이터 이동이 적어 쓰기 연산 비용이 낮음.

단점

• 시간 복잡도가 O(n²)로 비효율적.
• 안정 정렬이 아님.

 

 

 

8. 선택 정렬 성능 개선한 알고리즘 - 쉘 정렬(Shell Sort)

쉘 정렬은 선택 정렬을 기반으로 성능을 개선한 알고리즘입니다. 성능 개선 정도가 상당히 큽니다. 아래 링크에 자세히 정리했습니다.

2025.01.03 - [알고리즘] - 쉘 정렬(Shell Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

쉘 정렬(Shell Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의

 

 

 

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주