Selection Sort(선택 정렬)

Selection sort 란?

선택 정렬(Selection Sort)은 배열 내의 최소값(또는 최대값)을 찾아서 맨 앞(또는 맨 뒤)에 위치한 값과 교환하는 방식으로 정렬을 수행하는 알고리즘입니다. 이 과정을 배열 전체에 대해 반복함으로써 전체 배열을 오름차순 또는 내림차순으로 정렬합니다. 선택 정렬은 이해하기 쉽고 구현하기 간단한 알고리즘 중 하나로, 작은 데이터 세트에 적합합니다.

 

Selection sort 사이클

선택 정렬의 한 사이클은 전체 배열에서 현재 선택된 위치를 기준으로 최소값을 찾는 과정을 포함합니다. 첫 번째 사이클에서는 전체 배열을 검사하여 최소값을 찾고, 이 값을 배열의 첫 번째 위치와 교환합니다. 두 번째 사이클에서는 첫 번째 원소를 제외한 나머지 배열에 대해 동일한 과정을 수행합니다. 즉, 두 번째 위치의 원소를 최소값으로 간주하고, 두 번째 원소 이후의 배열에서 실제 최소값을 찾아 두 번째 위치의 원소와 교환합니다. 이러한 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다.

 

Selection sort 시간복잡도와 공간복잡도

• 시간 복잡도
  • 최선, 평균, 최악의 경우 모두 𝑂(𝑛2)입니다. 이는 선택 정렬이 각 단계마다 나머지 배열에 대해 최소값을 찾기 위해 비교 연산을 반복해야 하기 때문입니다.
• 공간 복잡도
  • 𝑂(1)입니다. 선택 정렬은 추가적인 저장 공간을 필요로 하지 않으며, 정렬을 위해 원본 배열 내에서 값의 교환이 이루어집니다.

 

Selection sort 장단점

장점

• 간단하고 이해하기 쉬움: 선택 정렬의 알고리즘은 매우 단순하며, 구현하기 쉽습니다.
• 메모리 효율적: 추가적인 메모리 공간을 필요로 하지 않습니다.

단점

• 비효율적인 시간 복잡도: 𝑂(𝑛2)의 시간 복잡도는 대용량 데이터에 부적합합니다.
• 비안정 정렬: 선택 정렬은 동일한 값을 가진 요소의 상대적 순서를 유지하지 않습니다. 즉, 안정 정렬(stable sort)이 아닙니다.

 

Selection sort 코드

golang

package main

import "fmt"

// SelectionSort 함수는 선택 정렬을 구현한다.
func SelectionSort(arr []int) {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        minIdx := i
        for j := i + 1; j < n; j++ {
            if arr[j] < arr[minIdx] {
                minIdx = j
            }
        }
        // 최소값을 찾은 후 현재 위치(i)의 값과 교환
        arr[i], arr[minIdx] = arr[minIdx], arr[i]
    }
}

func main() {
    sample := []int{64, 25, 12, 22, 11}
    SelectionSort(sample)
    fmt.Println("Sorted array: ", sample)
}

 

java

public class SelectionSort {
    void sort(int arr[]) {
        int n = arr.length;
        // 하나씩 모든 원소를 이동
        for (int i = 0; i < n-1; i++) {
            // 최소 원소의 인덱스 찾기
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;
            // 찾은 최소값을 정렬된 부분의 맨 앞으로 이동
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    // 메인 메소드로 실행 예시
    public static void main(String args[]) {
        SelectionSort ss = new SelectionSort();
        int arr[] = {64, 25, 12, 22, 11};
        ss.sort(arr);
        System.out.println("Sorted array");
        for (int i=0; i<arr.length; i++)
            System.out.print(arr[i]+" ");
    }
}

 

python

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 현재 위치의 값을 최소값으로 가정
        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]

# 예제 배열
sample = [64, 25, 12, 22, 11]
selection_sort(sample)
print("Sorted array:", sample)

 

sort