[알고리즘 이론] 정렬 Sort - 2-1. 비교 기반 알고리즘 (선택 정렬)

💡예시에 대한 가정
- 입력 크기 n
- 입력 배열 A[0…. n-1]
- 입력 데이터 : 양의 정수
- 정렬 방식 : 오름차순 (1, 2, 3, 4,…)

 

2-1) 선택 정렬 (Selection sort)

1. 입력 배열에서 가장 작은 값부터 순서대로 선택해서 나열하는 방식
2. 정렬 과정

📍배열 A = [60, 90, 30, 10]

(0단계) 1. 미정렬 부분에서 최솟값을 찾음 = 10 A = [60, 90, 30, 10] 2. 이 최솟값과 미정렬 부분의 첫 번째 데이터[60] 비교 10 과 60 비교 : 10 은 60보다 작다. (조건 만족) A = [60, 90, 30, 10] 3. 조건만족 시, 위치를 교환 -> 이 과정을 반복

A = [10, 90, 30, 60]               미정렬 부분에서 정렬 시작 (1단계) 최소값 30, 미정렬 첫 번 째 값 90 비교 A = [10, 90, 30, 60] A = [10,30, 90, 60] (2단계) 최소값 60, 미정렬 첫 번 째 값 90 비교 A = [10, 30, 90, 60] A = [10, 30, 60, 90] (결과) A = [10, 30, 60, 90] 데이터 갯수 : 4개 총 비교 횟수 : 4번 = (n-1) - i = (4 - 1) - 0 = 3

 

 

3. 특징

• 성능 : O(n²)
• 입력 데이터의 순서에 민감하지 않음
  → 항상 (n-1) - i 번의 비교가 필요 (항상 최소값 찾아서 비교)
  → 언제나 동일한 시간 복잡도
• 제자리 정렬 알고리즘 : 입력 배열 A이외 상수개(i, j, min, tmp)의 저장 공간만 필요
• 안정적이지 않은 정렬 알고리즘 : 동일한 값을 갖는 데이터가 여러 개일 경우, 결과적으로 위치가 바뀜

안정적이지 않은 알고리즘

 

 

[JS code]

function selectionSort(A) {
    const n = A.length;
    
    for (let i = 0; i < n - 1; i++) { // (n-1)번 반복
        // 최솟값의 인덱스를 i로 설정합니다.
        let min = i; 
        
        for (let j = i + 1; j < n; j++) { 
        // 1. A[i..n-1]에서 최솟값 찾기
        
        	// 만약 최소값 A[min]이 A[j]보다 크다면
            if (A[min] > A[j]) {
            	// min을 j로 갱신
                min = j;
            }
        }
        
        //2. A[i]와 A[min]의 위치를 교환합니다.
        
        // A[i]를 임시로 저장합니다.
        let temp = A[i];
        
        // 2. A[i]를 최소값과 A[min]으로 교체
        A[i] = A[min];
        //임시로 저장한 값temp을 A[min]에 대입
        A[min] = temp;
    }
    
    return A;
}