[알고리즘 개념] 정렬 알고리즘 - 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

정렬 순서 (오름차순 정렬 기준)

1. 주어진 리스트에서 최소 값을 찾는다.
2. 최소 값을 유효 범위 내에서 맨 앞의 값과 swap한다.
3. swap된 위치를 제외 한 나머지 공간이 1개가 될때까지 1 ~ 2를 반복한다.

 

예시

1, 2 회전 후 결과

3, 4 회전 후 결과

장점

• 구현이 쉽고 이해하기 쉽다.
• In-place Sorting Algorithm
  • 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n)

 

단점

•  O(n²)의 시간복잡도
• 불안정 정렬 (Unstable sorting)
  • 중복 값 순서 보장 못함

 

시간 복잡도 

• 외부 루프: (n-1)번 반복
• 최솟값 탐색: n-1, n-2, n-3, ... ,2, 1
• T(n) =  1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2 ∈ O(n²) 

 

Code (C/C++) 

#include <stdio.h>
#define LENGTH 5

// Selection Sort
void selectionSort(int* arr){

    // 맨 마지막 원소는 알아서 정렬이 되기 때문에 l-2까지 반복
    for(int cur = 0; cur < LENGTH -1 ; cur++) { 
       int min = cur;
       
       // 최소값 찾기
       for(int j = cur + 1; j < LENGTH; j++) {
           if(arr[min] > arr[j])
                min = j;
       }
       
       // 최소값이 자기 자신인 경우 swap이 필요없다.
      if(min == cur)
        continue;
            
      int tmp = arr[min];
      arr[min] = arr[cur];
      arr[cur] = tmp;
    }
}

int main() {
    int arr[LENGTH] = {7,4,2,9,5};
    printf("Before Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    selectionSort(arr);

    printf("After Sorting: ");
    for(int i = 0; i<LENGTH; i++) {
        printf("%d ", arr[i]);
    }
}

Code (Java)

public class sorting {
    public static void main(String[] args) {
        int[] arr = {7,4,2,9,5};
        System.out.print("Before Sorting: ");
        printArr(arr);
        selectionSort(arr);
        System.out.print("After Sorting: ");
        printArr(arr);
    }

    // Print Array
    static void printArr(int[] arr) {
        int l = arr.length;
        for(int i = 0; i<l; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    // Selection Sort
    static void selectionSort(int[] arr) {
        int l = arr.length;
        
        // 맨 마지막 원소는 알아서 정렬이 되기 때문에 l-2까지 반복
        for(int cur = 0; cur < l-1; cur++) {   
            int min = cur;
            
            // 최소값 찾기
            for(int j = cur + 1; j < l; j++) {
                if(arr[min] > arr[j])
                    min = j;
            }
            
            // 최소값이 자기 자신인 경우 swap이 필요없다.
            if(min == cur)
                continue;
                
            // swap
            int tmp = arr[min];
            arr[min] = arr[cur];
            arr[cur] = tmp;
        }
    }
}