[알고리즘] 선택 정렬 SelectionSort

정렬 알고리즘이란?

정렬 알고리즘은 배열의 원소들을 조건에 맞게 순서대로 정렬하는 알고리즘입니다. 원소들이 어떤 순서로 들어오는지에 따라 적절한 정렬 알고리즘을 선택할 수 있습니다.

선택 기준

1. 시간 복잡도: 알고리즘이 실행되는 데 소요되는 시간
2. 공간 복잡도: 알고리즘이 사용하는 메모리의 양
3. 안전성 (Stability): 동일한 값의 원소들의 순서가 유지되는지 여부

정렬 알고리즘 종류와 시간 복잡도

정렬 알고리즘 종류	최선 시간 복잡도	평균 시간 복잡도	최악 시간 복잡도
BubbleSort (버블 정렬)	O(n)	O(n^2)	O(n^2)
SelectionSort (선택 정렬)	O(n^2)	O(n^2)	O(n^2)
InsertionSort (삽입 정렬)	O(n)	O(n^2)	O(n^2)
MergeSort (병합 정렬)	O(n log n)	O(n log n)	O(n log n)
RadixSort (기수 정렬)	O(nk)	O(nk)	O(nk)
QuickSort (퀵 정렬)	O(n log n)	O(n log n)	O(n^2)

 

현재 정렬을 사용할 때는 대부분 퀵 정렬을 사용합니다. 병합 정렬이 최악의 조건에서 더 빠를 것 같다고 생각할 수 있지만, 정렬 알고리즘을 선택할 때는 시간 복잡도뿐만 아니라 공간 복잡도도 고려해야 합니다.

병합 정렬은 메모리를 많이 사용하므로, 여러 가지를 고려하여 정렬 알고리즘을 선택해야 합니다.

 

 

SelectionSort(선택 정렬)란?

선택 정렬(Selection Sort)은 배열의 요소를 정렬하는 간단한 알고리즘입니다. 이 알고리즘의 기본 아이디어는 배열을 여러 번 순회하면서 최솟값을 찾아서, 그 최솟값을 배열의 시작 위치와 교환하는 것입니다. 이 과정을 반복하여 배열이 정렬될 때까지 계속합니다.

선택 정렬의 과정 (오름차순 정렬)

1. 배열에서 최솟값 찾기:
   • 현재 검사할 위치를 시작점으로 설정합니다.
   • 배열의 나머지 부분을 순회하면서 최솟값을 찾습니다.
2. 최솟값과 시작 위치의 값 교환:
   • 찾은 최솟값과 현재 시작 위치의 값을 교환합니다.
3. 다음 위치로 이동하여 반복:
   • 다음 위치로 이동하여 다시 최솟값을 찾고 교환합니다.
   • 배열의 끝에 도달할 때까지 이 과정을 반복합니다.

예를 들어, 배열이 [64, 25, 12, 22, 11]이라고 가정합시다. 선택 정렬의 과정을 따라가며 정렬해보겠습니다.

상세 과정

1. 첫 번째 반복 (0번째 위치):
   • 최솟값 찾기: 배열 전체에서 11을 찾습니다.
   • 64와 11을 교환합니다.
   • 결과 배열: [11, 25, 12, 22, 64]
2. 두 번째 반복 (1번째 위치):
   • 최솟값 찾기: 25, 12, 22 중에서 12를 찾습니다.
   • 25와 12를 교환합니다.
   • 결과 배열: [11, 12, 25, 22, 64]
3. 세 번째 반복 (2번째 위치):
   • 최솟값 찾기: 25, 22 중에서 22를 찾습니다.
   • 25와 22를 교환합니다.
   • 결과 배열: [11, 12, 22, 25, 64]
4. 네 번째 반복 (3번째 위치):
   • 최솟값은 이미 25이므로 교환할 필요가 없습니다.
   • 결과 배열: [11, 12, 22, 25, 64] (변화 없음)

이 과정을 반복하면 배열이 정렬됩니다.

선택 정렬의 특징

1. 비효율적인 성능:
   • 최적화가 불가능한 정렬입니다. 어떤 배열이 주어져도 항상 O(n²)의 시간복잡도를 가집니다.
   • 시간 복잡도: 평균과 최악의 경우 모두 O(n²).
2. 메모리 사용:
   • 추가적인 메모리 사용이 거의 없습니다. 선택 정렬은 공간 복잡도가 O(1)입니다.
3. 단순성:
   • 구현이 간단하고 직관적입니다. 배열의 인덱스를 직접 사용하여 정렬하기 때문에 구현이 쉽습니다.
4. 안정성:
   • 선택 정렬은 안정적이지 않습니다. 같은 값의 요소들이 서로의 상대적인 위치를 유지하지 않기 때문입니다.

 

코드로 작성하기

직접 하시고 싶은 분들이 있을 수 있으니 코드는 숨기겠습니다.

코드를 보고 싶다면 더보기 클릭:

// 두 원소의 위치를 교환하는 메소드
public static void swap(int[] arr, int i, int j) {
    // 임시 변수에 arr[i] 값을 저장합니다.
    int tmp = arr[i];
    // arr[i]에 arr[j] 값을 저장합니다.
    arr[i] = arr[j];
    // arr[j]에 임시 변수에 저장된 값을 저장합니다.
    arr[j] = tmp;
}

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        int[] arr = {5, 3, 6, 1, 8, 10, 2, 9, 7, 4};
        selectionSort(arr);
        System.out.print(Arrays.toString(arr));
    }
    
    // 선택 정렬 알고리즘 구현
    public static void selectionSort(int[] arr) {
        // 배열의 길이 - 1 만큼 반복
        for (int i = 0; i < arr.length - 1; i++) {
            // 현재 위치의 최솟값을 찾기 위해 초기화
            int minNum = arr[i];
            int minIdx = i;
            
            // i 번째 인덱스부터 배열의 끝까지 반복하여 최솟값 찾기
            for (int j = i; j < arr.length; j++) {
                if (minNum > arr[j]) {
                    minNum = arr[j];
                    minIdx = j;
                }
            }
            
            // 최솟값을 i 번째 위치로 swap
            swap(arr, i, minIdx);
        }
    }
    
    // 두 원소의 위치를 교환하는 메소드
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}