4. 선택정렬과 이중 선택정렬에 대해서 알아보자.

정렬 알고리즘의 기초 개념

정렬의 대상: 레코드(Record)

struct Student {
    int id;           // 학번
    string name;      // 이름
    int score;        // 점수
};

정렬의 대상: 레코드(Record)

- 정렬키 : 정렬의 기준이 되는 필드

- 위 예시에서 id, name, score 중 어느 것이든 정렬키가 될 수 있다.

정렬 방향

- 오름차순 (Ascending) : 작은 값 -> 큰 값

- 내림차순 (Descending) : 큰 값 -> 작은 값

정렬 분류 : 메모리 사용에 따른 분류

1. 내부 정렬 (internal Sorting)

- 정렬 대상을 한꺼번에 메인 메모리에 로딩 가능 할 때,

- 대부분의 기본 정렬 알고리즘이 해당된다.

- 빠른 접근 속도, 랜덤 엑세스가 가능하다.

2. 외부 정렬 (External Sorting)

- 정렬 대상을 메인 메모리에 한꺼번에 로딩할 수 없을 때,

- 메인 메모리와 보조 메모리(디스크)를 함께 사용한다.

- 대용량 데이터 처리에 필요하다.

정렬 분류 : 안정성에 따른 분류.

1. 안정 정렬(Stable Sort)

- 값은 키 값을 갖는 데이터 간의 정렬 전 순서가 정렬 후에도 유지된다.

- 예시 : Insertion SOrt, Merget Sort, Bubble Sort

2. 불안정 정렬(Not Stable Sort)

- 같은 키 값을 갖는 데이터의 순서가 바뀔 수 있는 정렬.

- 예시 : Quick OSrt, Heap Sort , Selection Sort

안정성 예시

정렬 전: [(3, A), (1, B), (3, C), (2, D)]

안정 정렬 후: [(1, B), (2, D), (3, A), (3, C)]

-> 같은 키 값 3을 가진 A와 C의 순서 유지

불안정 정렬 후: [(1, B), (2, D), (3, C), (3, A)]

-> A와 C의 순서가 바뀜

정렬 분류 : 정렬 방식에 따른 분류

1. 직접 정렬

- 실제 데이터의 위치를 바꿈

- 메모리 사용량은 적지만 데이터 이동 비용 발생

2. 간접 정렬

- 인덱스(포인터)만 바꾸고 실제 데이터는 그대로

- 데이터 접근이 한단계 더 필요하지만 대용량 레코드에 유리하다.

선택 정렬이란?

선택 정렬(Selection Sort)**은 가장 직관적인 정렬 알고리즘 중 하나로,
매 단계에서 가장 큰(또는 작은) 원소를 선택하여 올바른 위치에 배치하는 방식이다.

핵심 아이디어

전체 배열에서 가장 큰(또는 작은) 원소를 찾음
그 원소를 올바른 위치(끝 또는 시작)와 교환
정렬된 부분을 제외하고 위 과정을 반복

처리 과정

비교 → 선택(최대/최소값의 위치 찾기) → 교환

선택 정렬의 동작 원리

오름차순 정렬 과정

초기 배열: [64, 25, 12, 22, 11, 90]

1단계: 최대값 90을 마지막 위치로

[64, 25, 12, 22, 11, 90]
                    ↑   (최대값 90 찾음)

[64, 25, 12, 22, 11, 90]  (이미 올바른 위치)
정렬된 부분: [90]

2단계: 남은 부분에서 최대값 64를 끝으로

[64, 25, 12, 22, 11] | [90]
 ↑                     (최대값 64 찾음)

[11, 25, 12, 22, 64] | [90]  (64와 11 교환)
정렬된 부분: [64, 90]

3단계: 남은 부분에서 최대값 25를 끝으로

[11, 25, 12, 22] | [64, 90]
     ↑             (최대값 25 찾음)

[11, 22, 12, 25] | [64, 90]  (25와 22 교환)
정렬된 부분: [25, 64, 90]

4단계: 남은 부분에서 최대값 22를 끝으로

[11, 22, 12] | [25, 64, 90]
     ↑         (최대값 22 찾음)

[11, 12, 22] | [25, 64, 90]  (22와 12 교환)
정렬된 부분: [22, 25, 64, 90]

5단계: 남은 두 원소 비교

[11, 12] | [22, 25, 64, 90]
 ↑        (최대값 12 찾음)

[11, 12] | [22, 25, 64, 90]  (교환 필요 없음)
최종 결과: [11, 12, 22, 25, 64, 90]

코드 구현과 분석

기본 클래스 구조

#pragma once
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;

// 정렬 알고리즘 기본 클래스
class Sort {
protected:
    vector<int> m_data;
    int m_size;

public:
    Sort() {}
    ~Sort() {}

    void initData(vector<int> data) {
        m_data = data;
        m_size = data.size();
    }

    void printAll() {
        for (int i = 0; i < m_size; i++) {
            cout << m_data[i] << " ";
        }
        cout << endl;
    }

    virtual void sorting() = 0;  // 순수 가상 함수
};

선택 정렬 구현 (오름차순)

#pragma once
#include "sorting.h"

class Selection : public Sort {
public:
    void sorting() override;
};

void Selection::sorting() {
    // 마지막 위치부터 첫 번째 위치까지 역순으로 진행
    for (int last = m_size - 1; last >= 1; --last) {
        int largestIndex = 0;  // 최대값의 인덱스

        // 0부터 last까지 범위에서 최대값 찾기
        for (int cur = 1; cur <= last; cur++) {
            if (m_data[cur] > m_data[largestIndex]) {
                largestIndex = cur;
            }
        }

        // 최대값을 현재 마지막 위치로 이동
        swap(m_data[last], m_data[largestIndex]);
    }
}

코드 상세 분석

1. 외부 루프 (정렬 범위 제어)

for (int last = m_size - 1; last >= 1; --last)

- last : 현재 정렬할 마지막 위치

- m_size -1 부터 1 까지 : 배열 끝에서부터 시작해서 점진적으로 범위 축소

- last >= 1. : 원소 하나 남으면 자동으로 정렬 완료.

2. 최대값 찾기

int largestIndex = 0;  // 최대값 인덱스 초기화

for (int cur = 1; cur <= last; cur++) {
    if (m_data[cur] > m_data[largestIndex]) {
        largestIndex = cur;  // 더 큰 값 발견 시 인덱스 갱신
    }
}

3. 교환 연산

swap(m_data[last], m_data[largestIndex]);

- C++ STL의 swap 함수 사용

- 최대값값을 현재 정렬 범위의 마지막 위치로 이동.

실행 과정 추적

입력 배열: [10, 7, 9, 1, 3, 2, 8, 6, 4, 5]

패스정렬 범위최대값최대값 위치교환 후 배열

1	[0..9]	10	0	[5, 7, 9, 1, 3, 2, 8, 6, 4, 10]
2	[0..8]	9	2	[5, 7, 4, 1, 3, 2, 8, 6, 9, 10]
3	[0..7]	8	6	[5, 7, 4, 1, 3, 2, 6, 8, 9, 10]
4	[0..6]	7	1	[5, 6, 4, 1, 3, 2, 7, 8, 9, 10]
5	[0..5]	6	1	[5, 2, 4, 1, 3, 6, 7, 8, 9, 10]
6	[0..4]	5	0	[3, 2, 4, 1, 5, 6, 7, 8, 9, 10]
7	[0..3]	4	2	[3, 2, 1, 4, 5, 6, 7, 8, 9, 10]
8	[0..2]	3	0	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
9	[0..1]	2	1	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

시간 복잡도 분석

수학적 분석

비교 횟수 계산

1번째 패스: n-1번 비교 (전체 배열)
2번째 패스: n-2번 비교 (마지막 원소 제외)
3번째 패스: n-3번 비교
...
(n-1)번째 패스: 1번 비교

총 비교 횟수:

T(n) = (n-1) + (n-2) + (n-3) + ... + 1
     = n(n-1)/2
     = (n² - n)/2
     = O(n²)

교환 횟수 계산

각 패스마다 최대 1번의 교환
총 교환 횟수: 최대 n-1번 = O(n)

경우별 분석

최선의 경우 (Best Case)

배열이 이미 정렬된 경우
비교 횟수: O(n²) (변화 없음)
교환 횟수: 0번 (최대값이 이미 올바른 위치)
전체 시간 복잡도: O(n²)

최악의 경우 (Worst Case)

배열이 역순으로 정렬된 경우
비교 횟수: O(n²)
교환 횟수: n-1번
전체 시간 복잡도: O(n²)

평균의 경우 (Average Case)

비교 횟수: O(n²)
교환 횟수: 평균 n-1번
전체 시간 복잡도: O(n²)

공간 복잡도

O(1): In-place 정렬로 추가 메모리 거의 사용 안함

버블 정렬과의 비교

공통점

시간 복잡도: 둘 다 O(n²)
공간 복잡도: 둘 다 O(1) (In-place)
안정성: 둘 다 기본적으로 불안정 (선택 정렬)

차이점 비교

구분선택 정렬버블 정렬

핵심 전략	최대/최소값을 찾아 한 번에 이동	인접 원소끼리 비교하며 점진적 이동
교환 횟수	각 패스마다 최대 1번	각 패스마다 여러 번
총 교환 횟수	최대 n-1번	최대 n(n-1)/2번
최선의 경우	O(n²)	O(n)
실제 성능	버블 정렬보다 빠름	선택 정렬보다 느림
조기 종료	불가능	가능 (이미 정렬된 경우)

성능 차이의 원인

선택 정렬의 장점:

// 한 패스에서 교환은 최대 1번만
int maxIndex = findMaxIndex(0, last);
if (maxIndex != last) {
    swap(arr[last], arr[maxIndex]);  // 1번의 교환
}

버블 정렬의 단점:

// 한 패스에서 여러 번의 교환 발생
for (int i = 0; i < n-1; i++) {
    if (arr[i] > arr[i+1]) {
        swap(arr[i], arr[i+1]);  // 여러 번의 교환
    }
}

내림차순 구현

알고리즘 수정

오름차순에서는 최대값을 뒤로 보냈다면, 내림차순에서는 최대값을 앞으로 보냅니다.

void Selection::sorting() {
    // 첫 번째 위치부터 마지막 위치까지 순서대로 진행
    for (int first = 0; first < m_size - 1; ++first) {
        int bigIndex = first;  // 최대값의 인덱스

        // first+1부터 끝까지 범위에서 최대값 찾기
        for (int cur = first + 1; cur < m_size; cur++) {
            if (m_data[cur] > m_data[bigIndex]) {
                bigIndex = cur;
            }
        }

        // 최대값을 현재 첫 번째 위치로 이동
        swap(m_data[first], m_data[bigIndex]);
    }
}

동작 과정 예시

입력 배열: [10, 7, 9, 1, 3, 2, 8, 6, 4, 5]

1단계: 최대값 10을 첫 번째 위치로

[10, 7, 9, 1, 3, 2, 8, 6, 4, 5]
 ↑                               (최대값 10, 이미 올바른 위치)

결과: [10, 7, 9, 1, 3, 2, 8, 6, 4, 5]
정렬된 부분: [10]

2단계: 남은 부분에서 최대값 9를 두 번째 위치로

[10] | [7, 9, 1, 3, 2, 8, 6, 4, 5]
           ↑                        (최대값 9 찾음)

[10, 9, 7, 1, 3, 2, 8, 6, 4, 5]    (9와 7 교환)
정렬된 부분: [10, 9]

이중 선택 정렬이란?

일반 선택정렬은 한번에 하나의 원소만 정렬하지만, 이중 선택 정렬은 한번에 두개의 원소를 정렬한다.

- 최대값 : 정렬 범위의 끝으로 이동

- 최소값 : 정렬 범위의 시작으로 이동.

#pragma once
#include <cassert>
#include <vector>
#include <iostream>
using namespace std;

// 정렬 알고리즘 기본 클래스
class Sort {
protected:
    vector<int> m_data;
    int m_size;

public:
    Sort() {}
    ~Sort() {}

    void initData(vector<int> data) {
        m_data = data;
        m_size = data.size();
    }

    void printAll() {
        for (int i = 0; i < m_size; i++) {
            cout << m_data[i] << " ";
        }
        cout << endl;
    }

    virtual void sorting() = 0;  // 순수 가상 함수
};

class DoubleSelection : public Sort
{
public:
    void sorting() override;
};

void DoubleSelection::sorting()
{
    for(int first = 0; first < m_size / 2; ++first)
    {
        int last = m_size-1-first;
        int bigIndex = last;    // 최대값 인덱스
        int smallIndex = first; // 최소값 인덱스
        
        for(int cur = first; cur <= last; ++ cur)
        {
            if(m_data[cur] < m_data[smallIndex])
            {
                smallIndex = cur;
            }
            if(m_data[cur] > m_data[bigIndex])
            {
                bigIndex = cur;
            }
        }
        
        if(smallIndex != first)
        {
            swap(m_data[first], m_data[smallIndex]);
        }
        
        if(bigIndex == first)
        {
            bigIndex = smallIndex;
        }
        
        if(bigIndex != last)
        {
            swap(m_data[last], m_data[bigIndex]);
        }
    }
}

특별한 처리가 필요한 경우

1. 불필요한 교환 방지

if (smallIndex != first)  // 이미 올바른 위치가 아닐 때만 교환
if (bigIndex != last)     // 이미 올바른 위치가 아닐 때만 교환

2. 인덱스 갱신

if (bigIndex == first) {
    bigIndex = smallIndex;
}

최대값이 첫 번째 위치에 있었는데 최소 값과 교환했다면, 최대값의 새 위치를 갱신해야 한다.

동작 과정 예시

입력 배열: [29, 10, 14, 37, 13]

1회전 (first = 0, last = 4)

범위: [29, 10, 14, 37, 13]
최소값: 10 (인덱스 1) → 위치 0으로
최대값: 37 (인덱스 3) → 위치 4로

결과: [10, 29, 14, 13, 37]
정렬된 부분: [10] ... [37]

2회전 (first = 1, last = 3)

범위: [29, 14, 13] (인덱스 1~3)
최소값: 13 (인덱스 4) → 위치 1로
최대값: 29 (인덱스 1) → 위치 3으로

결과: [10, 13, 14, 29, 37]
정렬된 부분: [10, 13] ... [29, 37]

3회전 (first = 2, last = 2)

범위: [14] (인덱스 2)
원소가 하나뿐이므로 정렬 완료

최종 결과: [10, 13, 14, 29, 37]

시간 복잡도 분석

비교 횟수

일반 선택 정렬과 동일: O(n²)
하지만 실제 비교 횟수는 약 절반

교환 횟수

각 패스마다 최대 2번 교환
총 교환 횟수: 최대 n번

전체 성능

점근적 복잡도: 여전히 O(n²)
실제 성능: 일반 선택 정렬보다 약 2배 빠름

장단점 분석

장점

1. 직관적이고 이해하기 쉬움

"가장 큰 것을 찾아서 뒤로 보낸다"는 명확한 논리
디버깅과 검증이 용이

2. 교환 횟수가 적음

각 패스마다 최대 1번의 교환 (일반 버전)
교환 비용이 큰 경우 유리

3. In-place 정렬

추가 메모리 공간 거의 불필요
메모리 제약이 있는 환경에서 유용

4. 예측 가능한 성능

입력 데이터에 관계없이 항상 O(n²)
최선/최악의 경우 성능 차이가 거의 없음

단점

1. 느린 시간 복잡도

O(n²)로 대용량 데이터에 부적합
n이 커질수록 급격한 성능 저하

2. 불안정 정렬

같은 키 값을 가진 원소들의 순서가 바뀔 수 있음
안정성이 필요한 경우 부적합

3. 조기 종료 불가능

이미 정렬된 배열이어도 전체 비교 수행
버블 정렬 대비 적응성 부족

4. 캐시 효율성 부족

비연속적인 메모리 접근 패턴
현대 CPU의 캐시 시스템에 비효율적

실제 활용과 한계

사용하기 좋은 경우

1. 교육 목적

정렬 알고리즘 학습의 첫 단계
알고리즘 분석 연습에 적합

2. 매우 작은 데이터

10~20개 이하의 원소
구현 단순성이 성능보다 중요한 경우

3. 교환 비용이 큰 경우

struct LargeRecord {
    char data[1000];  // 큰 데이터 구조
    int key;
};

교환 횟수를 최소화해야 하는 상황

4. 메모리 제약이 극심한 환경

임베디드 시스템
추가 메모리를 전혀 사용할 수 없는 경우

사용하지 말아야 할 경우

1. 대용량 데이터

1000개 이상의 원소
O(n log n) 알고리즘 사용 권장

2. 성능이 중요한 시스템

실시간 시스템
웹 서버, 데이터베이스 등

3. 안정성이 필요한 경우

다중 키 정렬
사용자 인터페이스 정렬

실제 성능 테스트

#include <chrono>
#include <random>
#include <algorithm>

void performanceComparison(int size) {
    vector<int> data(size);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(1, 10000);

    for (int& num : data) {
        num = dis(gen);
    }

    // 선택 정렬 테스트
    vector<int> selectionData = data;
    auto start = chrono::high_resolution_clock::now();

    Selection selectionSort;
    selectionSort.InitData(selectionData);
    selectionSort.sorting();

    auto end = chrono::high_resolution_clock::now();
    auto selectionTime = chrono::duration_cast<chrono::milliseconds>(end - start);

    // 이중 선택 정렬 테스트
    vector<int> doubleData = data;
    start = chrono::high_resolution_clock::now();

    DoubleSelection doubleSort;
    doubleSort.InitData(doubleData);
    doubleSort.sorting();

    end = chrono::high_resolution_clock::now();
    auto doubleTime = chrono::duration_cast<chrono::milliseconds>(end - start);

    // 표준 정렬과 비교
    vector<int> stdData = data;
    start = chrono::high_resolution_clock::now();
    sort(stdData.begin(), stdData.end());
    end = chrono::high_resolution_clock::now();
    auto stdTime = chrono::duration_cast<chrono::milliseconds>(end - start);

    cout << "크기 " << size << "일 때:" << endl;
    cout << "선택 정렬: " << selectionTime.count() << "ms" << endl;
    cout << "이중 선택: " << doubleTime.count() << "ms" << endl;
    cout << "표준 정렬: " << stdTime.count() << "ms" << endl;
    cout << endl;
}

예상 성능 결과

데이터 크기선택 정렬이중 선택표준 정렬비고

100개	1ms	0.5ms	0.01ms	교육용으로 적합
1,000개	10ms	5ms	0.1ms	성능 차이 명확
10,000개	1000ms	500ms	1ms	실용성 없음
100,000개	100s	50s	10ms	사용 불가

다른 O(n²) 정렬과의 비교

성능 순서 (일반적인 경우)

삽입 정렬 - 거의 정렬된 데이터에서 최고 성능
선택 정렬 - 교환 횟수가 적어 안정적
버블 정렬 - 가장 비효율적

특성 비교표

정렬 알고리즘	시간복잡도	안정성	교환횟수	적용성	추천도
선택 정렬	O(n²)	불안정	O(n)	없음	중간
삽입 정렬	O(n²)	안정	O(n²)	높음	좋음
버블 정렬	O(n²)	안정	O(n²)	중간	별로

마무리

핵심 정리

1. 선택정렬은 직관적이고 구현이 간단한 기본정렬 알고리즘.

2. 교환 횟수가 적어 교환 비용이 큰 경우에 유리.

3. 시간복잡도는 O(n^2)로 대용량 데이터에는 부적합.

4. 이중 선택 정렬로 실제 성능을 약 2배 향상시킬 수 있음.

5. 교육목적과 소규모 데이터를 제외하고는 실무에서 사용하지 않음.

'Game DevTip > Algorithm' 카테고리의 다른 글

5. 삽입정렬에 대해서 (3)	2025.07.27
3. 버블정렬 알고리즘에 대해서 (3)	2025.07.25
2. Algorithm : 알고리즘에 대해서 (6)	2025.06.09
1. Algorithm : 피보나치 수열 & 다이나믹 프로그래밍 (0)	2025.06.09