삽입 정렬의 핵심 개념

삽입 정렬 (Insertion Sort) 은 데이터를 하나씩 꺼내어 이미 정렬된 부분에 올바른 위치를 찾아 삽히는 방식입니다. 주로 부분적으로 정렬된 데이터를 처리하거나 데이터 크기가 작을 때 효율적입니다. 이 알고리즘은 불안정하지 않으며 시간 복잡도는 평균적・최악의 경우 O(n²) 입니다.

오름차순 정렬 구현

왼쪽에서 오른쪽으로 진행하며, 현재 인덱스의 요소를 기준으로 왼쪽에 있는 더 큰 값들을 오른쪽으로 밀어내고 적절한 자리를 찾습니다.

void sort_array_ascending(double* data, int size) {
    if (size < 2) return;
    
    // 첫 번째 원소는 이미 정렬된 상태로 간주하고 두 번째부터 시작
    for (int curr = 1; curr < size; ++curr) {
        double targetVal = data[curr];
        int prevIdx = curr - 1;

        // 이전 값이 타겟보다 크면 우측으로 이동
        while (prevIdx >= 0 && data[prevIdx] > targetVal) {
            data[prevIdx + 1] = data[prevIdx];
            --prevIdx;
        }
        // 타겟 값을 빈 공간에 저장
        data[prevIdx + 1] = targetVal;
    }
}

내림차순 정렬 구현

비교 연산자만 변경하면 내림차순으로도 쉽게 적용할 수 있습니다. 작은 값보다 큰 값을 먼저 배치하는 로직으로 전환합니다.

void sort_array_descending(double* data, int size) {
    if (size < 2) return;

    for (int curr = 1; curr < size; ++curr) {
        double targetVal = data[curr];
        int prevIdx = curr - 1;

        // 이전 값이 타겟보다 작으면 우측으로 이동
        while (prevIdx >= 0 && data[prevIdx] < targetVal) {
            data[prevIdx + 1] = data[prevIdx];
            --prevIdx;
        }
        data[prevIdx + 1] = targetVal;
    }
}

테스트 실행 소스

동적 메모리를 할당받아 사용자 입력을 받고, 위 함수들을 호출하여 결과를 출력하는 메인 루프입니다.

#include <iostream>
#include <vector>

void sort_array_ascending(double* data, int size);
void sort_array_descending(double* data, int size);
void display_array(const double* data, int len);

void run_check() {
    std::cout << "정렬할 원소의 개수를 입력하세요: ";
    int count = 0;
    std::cin >> count;

    if (count <= 0) {
        std::cout << "잘못된 크기입니다.\n";
        return;
    }

    double* buffer = new double[count]();
    std::cout << "초기화 상태: ";
    display_array(buffer, count);
    std::cout << "\n";

    std::cout << "원소들을 공백으로 구분하여 입력하세요: ";
    for (int i = 0; i < count; ++i) {
        std::cin >> buffer[i];
    }

    std::cout << "\n[오름차순 결과]\n";
    sort_array_ascending(buffer, count);
    display_array(buffer, count);

    // 다시 정렬을 위해 역순이나 초기값이 필요하지 않다면 새로운 데이터를 가져와야 함
    // 여기서는 원본 보존을 위해 복사본 사용 대신 재사용 (임시 수정)
    std::cout << "\n[내림차순 결과]\n";
    sort_array_descending(buffer, count);
    display_array(buffer, count);

    delete[] buffer;
}

void display_array(const double* data, int len) {
    for (int i = 0; i < len; ++i) {
        std::cout << data[i] << "\t";
    }
    std::cout << "\n";
}

int main() {
    run_check();
    return 0;
}

실행 로그 예시

$ ./sort_test
정렬할 원소의 개수를 입력하세요: 6
초기화 상태: 0	0	0	0	0	0	

원소들을 공백으로 구분하여 입력하세요: 
66 7.89 6.36 77.89 195779 1627.347

[오름차순 결과]
6.36	7.89	66	77.89	1627.35	195779	

[내림차순 결과]
195779	1627.35	77.89	66	7.89	6.36	
$