선택 정렬(selection sort)

선택 정렬이란?

선택 정렬은 리스트에서 가장 작은 값을 찾아 맨 앞의 값과 교체하는 과정을 반복하여 정렬을 수행하는 알고리즘입니다.

정렬 순서

1. 주어진 리스트 중에서 최솟값을 찾는다.
2. 찾은 최솟값을 맨 앞에 위치한 값과 교환한다. (이를 하나의 "패스(Pass)"라고 한다)
3. 맨 앞을 제외한 나머지 리스트에 대해 같은 방법을 반복한다.

이 과정을 리스트 전체가 정렬될 때까지 반복합니다.

의사 코드 (Pseudocode)

for i = 0 to n - 2:
    min_index = i
    for j = i + 1 to n - 1:
        if a[j] < a[min_index]:
            min_index = j
    swap a[i] and a[min_index]

시간 복잡도

선택 정렬은 모든 원소를 비교하며 최솟값을 찾기 때문에, 비교 횟수는 데이터 크기에 따라 **O(n²)**가 소요됩니다.

 

구분	복잡도
최선의 경우	O(n²)
평균적인 경우	O(n²)
최악의 경우	O(n²)
공간 복잡도	O(1) (추가 메모리 사용 없음)

• 비교 연산은 항상 일정하게 진행되므로, 데이터가 이미 정렬되어 있어도 시간 복잡도는 줄어들지 않습니다.

예제

초기 리스트:  `[9, 1, 6, 8, 4, 3, 2, 0]`

패스 번호	리스트 상태	선택된 최솟값
0	[9, 1, 6, 8, 4, 3, 2, 0]	0
1	[0, 1, 6, 8, 4, 3, 2, 9]	1
2	[0, 1, 6, 8, 4, 3, 2, 9]	2
3	[0, 1, 2, 8, 4, 3, 6, 9]	3
4	[0, 1, 2, 3, 4, 8, 6, 9]	4
5	[0, 1, 2, 3, 4, 8, 6, 9]	6
6	[0, 1, 2, 3, 4, 6, 8, 9]	8

장단점

장점

• 구현이 매우 간단하다
  → 알고리즘 구조가 직관적이며 코드가 짧고 이해하기 쉽다.
• 추가 메모리가 거의 필요 없다
  → 공간 복잡도: O(1)
  → 별도의 배열이나 자료구조 없이 주어진 배열 내에서만 정렬을 수행한다.
• 데이터의 크기가 작거나, 메모리 제한이 있는 경우 유리
  → 정렬 속도가 크게 중요하지 않은 환경에서 간단한 정렬을 원할 때 적합.

단점

• 시간 복잡도가 항상 O(n²)
  → 특히 이미 정렬되어 있는 경우에도 불필요한 비교가 계속 진행된다.
  → 최선, 최악, 평균 모두 O(n²)로, 데이터가 많을수록 매우 비효율적이다.
• 안정 정렬이 아니다
  → 동일한 값의 원소들이 정렬 후 원래 순서가 유지되지 않을 수 있다.
• 대규모 데이터 정렬에는 부적합
  → 효율성이 낮기 때문에, 대량의 데이터를 정렬할 경우 다른 고급 알고리즘(퀵 정렬, 병합 정렬 등)을 사용하는 것이 좋다.

코드 예시

C

void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

Java

void selectionSort(int[] list) {
    int indexMin, temp;

    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

Python

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x

정렬 알고리즘 시간복잡도 비교

알고리즘 이름	Best	Avg	Worst	공간복잡도
삽입 정렬	𝑂(𝑛)	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(1) (제자리 정렬)
선택 정렬	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(1) (제자리 정렬)
버블 정렬	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(𝑛²)	𝑂(1) (제자리 정렬)
셸 정렬	𝑂(𝑛)	𝑂(𝑛¹⋅⁵)	𝑂(𝑛²)	𝑂(1) (제자리 정렬)
퀵 정렬	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(𝑛²)	𝑂(log 𝑛) (재귀 호출 스택)
힙 정렬	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(1) (제자리 정렬)
병합 정렬	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(𝑛 log 𝑛)	𝑂(𝑛) (추가 배열 필요)

• 제자리 정렬(in-place sort): 추가 메모리를 거의 사용하지 않는 정렬, 주로 𝑂(1) 을 보장