선택 정렬

Q: 선택 정렬의 시간 복잡도는?

선택 정렬은 최선, 평균, 최악의 모든 경우에서 `O(n²)`입니다. 각 최소값을 찾기 위해 항상 정렬되지 않은 영역 전체를 훑기 때문입니다. 추가 공간은 `O(1)`을 사용합니다.

Q: 선택 정렬은 언제 유용한가요?

메모리 쓰기 비용이 높을 때 유용합니다. 교환을 최대 `n-1`회만 수행하는데, 이는 원소를 이동하는 비교 기반 정렬에서 가능한 최소 횟수이기 때문입니다.

Q: 선택 정렬과 버블 정렬의 차이는 무엇인가요?

둘 다 `O(n²)` 비교 기반 정렬이지만, 선택 정렬은 교환이 최대 `n-1`회인 반면 버블 정렬은 최대 `O(n²)`회까지 교환할 수 있습니다. 또한 버블 정렬은 이미 정렬된 배열을 감지해 조기에 멈출 수 있지만, 선택 정렬은 항상 모든 패스를 실행합니다.

Q: 선택 정렬과 삽입 정렬 중 무엇을 써야 하나요?

대부분의 경우 삽입 정렬이 더 낫습니다. 안정적이고, 거의 정렬된 데이터에서 `O(n)`으로 동작하며, 평균적으로 더 빠릅니다. 선택 정렬은 쓰기 횟수 최소화가 최우선일 때만 선택하세요. 교환이 최대 `n-1`회임을 보장하기 때문입니다.

마지막 업데이트 2026년 7월 1일

선택 정렬은 배열을 왼쪽의 정렬된 영역과 오른쪽의 정렬되지 않은 영역으로 나눕니다. 각 패스마다 정렬되지 않은 영역을 훑어 가장 작은 원소를 찾은 다음, 그것을 첫 번째 정렬되지 않은 위치로 교환하여 정렬된 영역을 하나씩 늘립니다. 위의 재생을 눌러 탐색과 교환을 지켜보거나, 비교를 하나씩 단계별로 진행하세요.

선택 정렬은 입력에 관계없이 항상 같은 횟수의 비교를 수행하지만, 교환은 최대 n-1회에 그칩니다. 이는 버블 정렬보다 훨씬 적으며, 쓰기 비용이 클 때 중요합니다.

시간 및 공간 복잡도

경우	복잡도	비고
최선의 경우	O(n²)	정렬되어 있어도 비교는 수행됨
평균의 경우	O(n²)	무작위 순서
최악의 경우	O(n²)	역순 정렬
공간	O(1)	제자리 정렬
안정성	아니오	교환으로 같은 원소의 순서가 바뀔 수 있음

단계별 과정

단계	무슨 일이 일어나는가
1	배열 전체를 정렬되지 않은 것으로 간주한다.
2	정렬되지 않은 영역을 훑어 최소 원소를 찾는다.
3	그 최소값을 첫 번째 정렬되지 않은 위치로 교환한다.
4	경계를 오른쪽으로 한 칸 옮긴다(그 자리는 이제 정렬됨).
5	정렬되지 않은 원소가 하나 남을 때까지 반복한다.

풀이 예제

[5, 2, 4, 1] 정렬:

패스	배열	동작
시작	`[5, 2, 4, 1]`	배열 전체가 정렬되지 않음.
1	`[1, 2, 4, 5]`	`[5, 2, 4, 1]`을 훑으면 최소는 인덱스 3의 `1`; 인덱스 0과 교환한다.
2	`[1, 2, 4, 5]`	`[2, 4, 5]`를 훑으면 최소는 이미 인덱스 1에 있는 `2`; 자기 자신과 교환한다.
3	`[1, 2, 4, 5]`	`[4, 5]`를 훑으면 최소는 이미 인덱스 2에 있는 `4`; 이동이 필요 없다.
완료	`[1, 2, 4, 5]`	`5`만 남았으므로 이미 제자리에 있다.

선택 정렬을 언제 사용할까

사용하기 좋은 경우	피해야 하는 경우
쓰기 비용이 클 때 - 교환이 최대 `n-1`회에 그친다.	배열이 클 때 - `O(n²)` 비교가 지배적이다.
단순하고 구현하기 쉬운 제자리 정렬이 필요할 때.	같은 키의 순서를 보존하는 안정 정렬이 필요할 때.
메모리가 부족할 때 - 추가 공간을 `O(1)`만 사용한다.	데이터가 거의 정렬되어 있을 때 - 삽입 정렬처럼 조기에 끝낼 수 없다.
데이터셋이 아주 작고 예측 가능한 성능이 중요할 때.	처리량이 중요할 때 - 퀵 정렬 같은 `O(n log n)` 정렬이 훨씬 빠르다.

Selection Sort 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Selection Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Selection Sort 코드Python
1def selection_sort(a):2    n = len(a)3    for i in range(n - 1):4        # Find the smallest element in the unsorted tail5        min_idx = i6        for j in range(i + 1, n):7            if a[j] < a[min_idx]:8                min_idx = j9        a[i], a[min_idx] = a[min_idx], a[i]10    return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Selection Sort 코드JavaScript
1function selectionSort(a) {2    for (let i = 0; i < a.length - 1; i++) {3        let min = i;4        // Find the smallest element in the unsorted tail5        for (let j = i + 1; j < a.length; j++) {6            if (a[j] < a[min]) min = j;7        }8        if (min !== i) [a[i], a[min]] = [a[min], a[i]];9    }10    return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Selection Sort 코드Java
1import java.util.Arrays;2
3public class Main {4    static void selectionSort(int[] arr) {5        for (int i = 0; i < arr.length - 1; i++) {6            int minIndex = i;7            // Find the smallest value in the unsorted part8            for (int j = i + 1; j < arr.length; j++) {9                if (arr[j] < arr[minIndex]) minIndex = j;10            }11            int tmp = arr[i];12            arr[i] = arr[minIndex];13            arr[minIndex] = tmp;14        }15    }16
17    public static void main(String[] args) {18        int[] arr = {29, 10, 14, 37, 13, 5};19        System.out.println("Before: " + Arrays.toString(arr));20        selectionSort(arr);21        System.out.println("After:  " + Arrays.toString(arr));22    }23}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Selection Sort 코드C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11    for (size_t i = 0; i + 1 < a.size(); ++i) {12        // Find the smallest element in the unsorted suffix13        size_t minIdx = i;14        for (size_t j = i + 1; j < a.size(); ++j) {15            if (a[j] < a[minIdx]) minIdx = j;16        }17        std::swap(a[i], a[minIdx]);18    }19}20
21int main() {22    std::vector<int> data = {29, 10, 14, 37, 13, 5};23    std::cout << "Before: ";24    printVec(data);25    selectionSort(data);26    std::cout << "After:  ";27    printVec(data);28    return 0;29}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Selection Sort 코드C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4    for (int i = 0; i < n; i++) printf("%d ", a[i]);5    printf("\n");6}7
8void selectionSort(int a[], int n) {9    for (int i = 0; i < n - 1; i++) {10        // Find the smallest element in the unsorted suffix11        int minIdx = i;12        for (int j = i + 1; j < n; j++) {13            if (a[j] < a[minIdx]) minIdx = j;14        }15        int tmp = a[i];16        a[i] = a[minIdx];17        a[minIdx] = tmp;18    }19}20
21int main(void) {22    int data[] = {29, 10, 14, 37, 13, 5};23    int n = sizeof(data) / sizeof(data[0]);24    printf("Before: ");25    printArr(data, n);26    selectionSort(data, n);27    printf("After:  ");28    printArr(data, n);29    return 0;30}
이 코드를 C 플레이그라운드에서 실행하기

선택 정렬 자주 묻는 질문

선택 정렬의 시간 복잡도는?

선택 정렬은 최선, 평균, 최악의 모든 경우에서 O(n²)입니다. 각 최소값을 찾기 위해 항상 정렬되지 않은 영역 전체를 훑기 때문입니다. 추가 공간은 O(1)을 사용합니다.

선택 정렬은 안정 정렬인가요?

표준 제자리 버전은 안정적이지 않습니다. 멀리 있는 최소값을 제자리로 교환하면 같은 원소가 다른 원소를 앞질러 갈 수 있기 때문입니다. 안정적인 변형도 있지만 교환 대신 이동(shift)이 필요합니다.

선택 정렬은 언제 유용한가요?

메모리 쓰기 비용이 높을 때 유용합니다. 교환을 최대 n-1회만 수행하는데, 이는 원소를 이동하는 비교 기반 정렬에서 가능한 최소 횟수이기 때문입니다.

선택 정렬과 버블 정렬의 차이는 무엇인가요?

둘 다 O(n²) 비교 기반 정렬이지만, 선택 정렬은 교환이 최대 n-1회인 반면 버블 정렬은 최대 O(n²)회까지 교환할 수 있습니다. 또한 버블 정렬은 이미 정렬된 배열을 감지해 조기에 멈출 수 있지만, 선택 정렬은 항상 모든 패스를 실행합니다.

선택 정렬과 삽입 정렬 중 무엇을 써야 하나요?

대부분의 경우 삽입 정렬이 더 낫습니다. 안정적이고, 거의 정렬된 데이터에서 O(n)으로 동작하며, 평균적으로 더 빠릅니다. 선택 정렬은 쓰기 횟수 최소화가 최우선일 때만 선택하세요. 교환이 최대 n-1회임을 보장하기 때문입니다.

선택 정렬은 왜 정렬된 배열에서도 항상 O(n²)로 동작하나요?

선택 정렬은 정렬되지 않은 영역의 나머지를 훑지 않고서는 어떤 원소가 이미 최소인지 알 수 없기 때문에, 입력 순서와 무관하게 매 패스마다 모든 비교를 수행합니다. 그래서 최선의 경우가 최악의 경우와 같은 O(n²)가 됩니다. 조기에 중단할 수 있는 삽입 정렬이나 버블 정렬과는 다릅니다.