[c++] 피보트 정렬

12 Dec 2023

피보나치 정렬은 피보나치 수열을 이용하여 배열을 정렬하는 알고리즘입니다. 피보나치 수열은 현재 숫자와 직전 숫자를 더하여 다음 숫자를 만들어내는 수열로, 이를 이용하여 정렬 알고리즘을 만들 수 있습니다.

알고리즘 동작 방식

피보나치 수열 생성: 배열의 크기에 해당하는 길이까지의 피보나치 수열을 생성합니다.
정렬 배열 생성: 주어진 원본 배열의 크기와 동일한 크기의 임시 배열을 생성합니다.
피보나치 수열을 이용한 인덱스 정렬: 피보나치 수열을 이용하여 임시 배열을 원본 배열의 인덱스로 정렬합니다.
결과 반환: 정렬된 임시 배열을 반환합니다.

C++로의 구현

#include <iostream>
#include <vector>

// 주어진 길이의 피보나치 수열 생성
std::vector<int> generateFibonacci(int length) {
    std::vector<int> fibonacci;
    fibonacci.push_back(0);
    fibonacci.push_back(1);
    while (fibonacci.size() < length) {
        int next = fibonacci[fibonacci.size() - 1] + fibonacci[fibonacci.size() - 2];
        fibonacci.push_back(next);
    }
    return fibonacci;
}

// 피보나치 수열을 이용한 인덱스 정렬
std::vector<int> sortUsingFibonacci(const std::vector<int>& input) {
    std::vector<int> sorted(input.size(), 0);
    std::vector<int> fibonacci = generateFibonacci(input.size());
    for (int i = 0; i < input.size(); i++) {
        sorted[fibonacci[i]] = input[i];
    }
    return sorted;
}

int main() {
    std::vector<int> input = {5, 3, 8, 2, 1};
    std::vector<int> sorted = sortUsingFibonacci(input);
    for (int num : sorted) {
        std::cout << num << " ";
    }
    return 0;
}

위의 예시는 C++로 구현된 피보나치 정렬 알고리즘의 간단한 예시입니다.

알고리즘 동작 방식

C++로의 구현

참고 자료