11.2 선택 정렬¶

선택 정렬(selection sort)의 원리는 매우 간단하다. 반복문을 실행하여 매번 정렬되지 않은 구간에서 가장 작은 원소를 고른 뒤 정렬된 구간의 끝에 놓는다.

배열의 길이가 \(n\)일 때 선택 정렬의 과정은 아래 그림(11-2)과 같다.

처음에는 모든 원소가 정렬되지 않았으므로 미정렬 구간(인덱스)은 \([0, n-1]\)이다.
구간 \([0, n-1]\)에서 가장 작은 원소를 골라 인덱스 \(0\)의 원소와 교환한다. 그러면 배열의 앞 1개 원소가 정렬된다.
구간 \([1, n-1]\)에서 가장 작은 원소를 골라 인덱스 \(1\)의 원소와 교환한다. 그러면 배열의 앞 2개 원소가 정렬된다.
같은 과정을 반복한다. \(n - 1\) 번 선택하고 교환하면 배열의 앞 \(n - 1\) 개 원소가 정렬된다.
남은 원소 하나는 반드시 가장 큰 원소이므로 정렬할 필요가 없으며, 배열 정렬이 완료된다.

그림 11-2 선택 정렬 단계

코드에서는 \(k\)로 미정렬 구간의 최소 원소를 기록한다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

selection_sort.py

def selection_sort(nums: list[int]):
    """선택 정렬"""
    n = len(nums)
    # 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for i in range(n - 1):
        # 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        k = i
        for j in range(i + 1, n):
            if nums[j] < nums[k]:
                k = j  # 최솟값의 인덱스를 기록한다
        # 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        nums[i], nums[k] = nums[k], nums[i]

selection_sort.cpp

/* 선택 정렬 */
void selectionSort(vector<int> &nums) {
    int n = nums.size();
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for (int i = 0; i < n - 1; i++) {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 최솟값의 인덱스를 기록한다
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        swap(nums[i], nums[k]);
    }
}

selection_sort.java

/* 선택 정렬 */
void selectionSort(int[] nums) {
    int n = nums.length;
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for (int i = 0; i < n - 1; i++) {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 최솟값의 인덱스를 기록한다
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

selection_sort.cs

/* 선택 정렬 */
void SelectionSort(int[] nums) {
    int n = nums.Length;
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for (int i = 0; i < n - 1; i++) {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 최솟값의 인덱스를 기록한다
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        (nums[k], nums[i]) = (nums[i], nums[k]);
    }
}

selection_sort.go

/* 선택 정렬 */
func selectionSort(nums []int) {
    n := len(nums)
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for i := 0; i < n-1; i++ {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        k := i
        for j := i + 1; j < n; j++ {
            if nums[j] < nums[k] {
                // 최솟값의 인덱스를 기록한다
                k = j
            }
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        nums[i], nums[k] = nums[k], nums[i]

    }
}

selection_sort.swift

/* 선택 정렬 */
func selectionSort(nums: inout [Int]) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for i in nums.indices.dropLast() {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        var k = i
        for j in nums.indices.dropFirst(i + 1) {
            if nums[j] < nums[k] {
                k = j // 최솟값의 인덱스를 기록한다
            }
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        nums.swapAt(i, k)
    }
}

selection_sort.js

/* 선택 정렬 */
function selectionSort(nums) {
    let n = nums.length;
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for (let i = 0; i < n - 1; i++) {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        let k = i;
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[k]) {
                k = j; // 최솟값의 인덱스를 기록한다
            }
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        [nums[i], nums[k]] = [nums[k], nums[i]];
    }
}

selection_sort.ts

/* 선택 정렬 */
function selectionSort(nums: number[]): void {
    let n = nums.length;
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for (let i = 0; i < n - 1; i++) {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        let k = i;
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[k]) {
                k = j; // 최솟값의 인덱스를 기록한다
            }
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        [nums[i], nums[k]] = [nums[k], nums[i]];
    }
}

selection_sort.dart

/* 선택 정렬 */
void selectionSort(List<int> nums) {
  int n = nums.length;
  // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
  for (int i = 0; i < n - 1; i++) {
    // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
    int k = i;
    for (int j = i + 1; j < n; j++) {
      if (nums[j] < nums[k]) k = j; // 최솟값의 인덱스를 기록한다
    }
    // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
    int temp = nums[i];
    nums[i] = nums[k];
    nums[k] = temp;
  }
}

selection_sort.rs

/* 선택 정렬 */
fn selection_sort(nums: &mut [i32]) {
    if nums.is_empty() {
        return;
    }
    let n = nums.len();
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for i in 0..n - 1 {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        let mut k = i;
        for j in i + 1..n {
            if nums[j] < nums[k] {
                k = j; // 최솟값의 인덱스를 기록한다
            }
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        nums.swap(i, k);
    }
}

selection_sort.c

/* 선택 정렬 */
void selectionSort(int nums[], int n) {
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for (int i = 0; i < n - 1; i++) {
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 최솟값의 인덱스를 기록한다
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

selection_sort.kt

/* 선택 정렬 */
fun selectionSort(nums: IntArray) {
    val n = nums.size
    // 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
    for (i in 0..<n - 1) {
        var k = i
        // 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
        for (j in i + 1..<n) {
            if (nums[j] < nums[k])
                k = j // 최솟값의 인덱스를 기록한다
        }
        // 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
        val temp = nums[i]
        nums[i] = nums[k]
        nums[k] = temp
    }
}

selection_sort.rb

### 선택 정렬 ###
def selection_sort(nums)
  n = nums.length
  # 바깥쪽 반복문: 정렬되지 않은 구간은 [i, n-1]이다
  for i in 0...(n - 1)
    # 안쪽 반복문: 정렬되지 않은 구간의 최솟값을 찾는다
    k = i
    for j in (i + 1)...n
      if nums[j] < nums[k]
        k = j # 최솟값의 인덱스를 기록한다
      end
    end
    # 이 최솟값과 정렬되지 않은 구간의 첫 원소를 교환한다
    nums[i], nums[k] = nums[k], nums[i]
  end
end

코드 시각화

전체 화면 >

11.2.1 알고리즘 특성¶

시간 복잡도 \(O(n^2)\), 비적응형 정렬: 바깥 반복문은 \(n - 1\) 번 실행된다. 안쪽 반복문은 첫 회에 \(n - 1\) 번, 마지막 회에 \(1\) 번 실행된다. 즉, 각 회의 실행 횟수는 \(n - 1\), \(n - 2\), \(\dots\), \(2\), \(1\)이고 합은 \(\frac{n(n - 1)}{2}\)이다.
공간 복잡도 \(O(1)\), 제자리 정렬: 포인터 \(i\)와 \(j\)는 상수 크기의 추가 공간을 사용한다.
불안정 정렬: 아래 그림(11-3)과 같이 원소 nums[i]가 자신과 값이 같은 원소의 오른쪽으로 교환되어 두 원소의 상대적 순서가 바뀔 수 있다.

선택 정렬의 불안정성 예시

그림 11-3 선택 정렬의 불안정성 예시

11.2 선택 정렬¶

11.2.1 알고리즘 특성¶

댓글로 의견이나 질문, 제안을 남겨 주세요