[C++] 정렬과 버블 정렬 구현, 함수 포인터

데이터 정렬(Sort) 함수 - 버블 정렬

• 버블 정렬은 2개씩 비교하면서 오름차순 또는 내림차순으로 정렬한다.

• 역순일 때 최악인 이유 : 처음에 제일 큰 숫자만 제일 오른쪽으로 가고 나머지는 뒤죽박죽 섞여있는 경우 데이터의 개수만큼 비교해야 한다.

함수 포인터

• 함수의 주소를 저장할 수 있는 변수로, 함수를 변수처럼 다룰 수 있게 해 준다.

• 저장된 함수의 주소를 통해 다른 함수 안에서 동적으로 해당 함수를 호출할 수 있다.

ex) 정렬 함수를 여러 개 만들고, 이 중 하나가 필요할 때마다 동적으로 선택해서 실행할 수 있다.

• 코드의 유연성과 재사용성을 높여준다.

// 반환타입(*포인터이름)(매개변수타입);
void (*funcptr)(int);

• 반환 타입 : 함수가 반환하는 값의 타입

• 포인터 이름 : 함수 포인터의 이름

• 매개변수 타입 : 함수가 받는 인자들의 타입

함수 포인터는 언제 사용할까?

1) 콜백 함수(Callback Function)

• 특정 시점에 호출될 함수를 제공하고 호출하는 방식이다.

• 작업 완료 후 특정 작업을 수행해야 할 때 함수 포인터를 통해 원하는 함수를 전달하고 호출할 수 있다.

• 만약 전달된 함수가 없다면, `nullptr`로 설정하여 아무 동작도 하지 않게 만들 수 있다.

내가 작성한 기능을 다른 사람에게 제공하며, 그들의 프로그램에서 사용할 수 있게 만드는 방법이다.

다른 사람의 작업이 완료됐을 때 내가 제공한 콜백 함수가 호출되어 작업을 처리한다.

이런 경우에 유용하다.

① 여러 사람이 각각 다른 함수를 실행해야 할 때

② 정확한 동작을 사전에 예측할 수 없을 때 원하는 함수의 주소를 전달받아 필요시 호출한다.

관심법이 있지 않는 이상 다른 사람들이 구현하려는 기능을 미리 예측해서 구현해 놓을 수 없다.

 

▷ 예시

#include <iostream>
#include <functional>  // std::function을 사용하는 헤더 파일로, 객체, 람다, 함수 래퍼(wrapper)를 지원한다.

using namespace std;

// 작업 완료 후 호출할 콜백 함수
void OnTaskComplete() {
    cout << "작업이 완료됨." << :endl;
}

// 작업을 수행하는 함수
void DoTask(void (*callback)()) {
    cout << "작업 수행 중" << endl;
    // 작업 완료 후 콜백 함수 호출
    if (callback != nullptr) {
        callback();
    }
}

int main() {
    DoTask(OnTaskComplete);  // 콜백 함수 전달
    DoTask(nullptr);         // 콜백 없이 호출
    
    return 0;
}

 

2) 분기 처리 (선택적으로 코드를 실행시키는 것)

• 특정 상태에 따라 다른 함수를 호출해야 하는 경우, 조건문 대신 함수 포인터를 상태에 맞는 함수로 설정하여 처리할 수 있다.

• 코드의 유연성과 효율성을 높이는 데 유용하다.

조건문(ex. if-else if-else)처럼 매번 검사하면서 어떤 함수를 호출할지 결정하는 대신, 현재 상태에 따라 적절한 함수의 주소를 함수 포인터에 할당할 수 있다.

상태가 변경되면 함수 포인터를 업데이트하여 변경된 상태에 맞는 함수를 가리키게 한다.

이를 통해 조건을 반복적으로 평가하지 않고, 함수 포인터를 직접 호출하여 관련 작업을 수행할 수 있다.

즉, 해당 함수를 가리키도록 한 번만 세팅해 놓고, 함수 포인터만 호출하면 원하는 상태 또는 상태가 바뀌더라도 그에 맞는 함수가 항상 호출된다.

 

▷ 예시

#include <iostream>

using namespace std;

// 상태에 따라 호출될 함수들
void StateA() {
    cout << "상태 A 동작" << endl;
}

void StateB() {
    cout << "상태 B 동작" << endl;
}

// 상태를 기반으로 함수 포인터를 업데이트하고 호출
int main() {
    void (*currentStateFunc)() = nullptr;  // 현재 상태를 가리키는 함수 포인터
    
    // 상태를 A로 설정
    currentStateFunc = StateA;
    currentStateFunc();  // 상태 A 동작
    
    // 상태를 B로 변경
    currentStateFunc = StateB;
    currentStateFunc();  // 상태 B 동작
    
    return 0;
}

---

▷ 버블 정렬, 함수 포인터 사용 예시

가변 배열 안에 넣은 데이터 정렬을 버블 정렬을 사용하여 구현한다.
- 가변 배열 안에 무작위로 숫자를 집어넣어서 순차적으로 채운다.
- `Sort()`로 호출하면 오름차순이든 내림차순이든 숫자의 크기에 맞게 순서대로 정렬된다.

Arr.h

#pragma once

// 가변 배열 자료형 tArr (int)
typedef struct _tagArr
{
	int* pInt;
	int iCount;
	int iMaxCount;
} tArr;

// 배열 초기화 함수
void InitArr(tArr* _pArr);

// 데이터 추가 함수
void PushBack(tArr* _pArr, int _iData);

// 공간 추가 확장 함수
void Reallocate(tArr* _pArr);

// 배열 메모리 해제 함수
void ReleaseArr(tArr* _pArr);

// 데이터 정렬 함수
void Sort(tArr* _pArr, void(*SortFunc)(int*, int));  // 원래부터 함수의 주소를 받도록 설계되어있어야 한다.
// 두 번째 인자는 기능을 받겠다고 해서 함수의 주소를 받는 인자 타입을 선언했어야 그 함수가 인자로 들어올 수 있다.
// void(*SortFunc)(int*, int) => BubbleSort()의 경우 int이므로 이에 맞는 함수의 주소를 받아야 한다.

 

Arr.cpp

#include <iostream>
#include "Arr.h"

// 배열 초기화
void InitArr(tArr* _pArr) {
    _pArr->pInt = new int[2];  // new를 사용해 동적으로 메모리 할당
    _pArr->iCount = 0;
    _pArr->iMaxCount = 2;
}

// 공간 추가 확장
void Reallocate(tArr* _pArr) {
    // 1. 2배 더 큰 공간을 동적할당한다.
    int* pNew = new int[_pArr->iMaxCount * 2];  // new를 사용해 더 큰 배열 할당

    // 2. 기존 공간에 있던 데이터들을 새로 할당한 공간으로 복사시킨다.
    for (int i = 0; i < _pArr->iCount; ++i) {
        pNew[i] = _pArr->pInt[i];
    }

    // 3. 기존 공간은 메모리 해제
    delete[] _pArr->pInt;  // delete[]를 사용해 동적으로 할당된 배열을 해제

    // 4. 배열이 새로 할당된 공간을 가리키게 한다.
    _pArr->pInt = pNew;

    // 5. iMaxCount 변경점 적용
    _pArr->iMaxCount *= 2;
}

// 데이터 추가
void PushBack(tArr* _pArr, int _iData) {
    if (_pArr->iMaxCount <= _pArr->iCount) {
        Reallocate(_pArr);
    }
    _pArr->pInt[_pArr->iCount++] = _iData;
}

// 배열 메모리 해제
void ReleaseArr(tArr* _pArr) {
    delete[] _pArr->pInt;  // delete[]로 배열 메모리 해제
    _pArr->iCount = 0;
    _pArr->iMaxCount = 0;
}

void Sort(tArr* _pArr, void(*SortFunc)(int*, int)) {
    // 예외 처리 => 데이터가 0개, 1개면 정렬을 할 필요가 없다.
    // 데이터가 1개 이하면 정렬하지 않는다.
    if (_pArr->iCount <= 1)
        return;

    // 오름차순 정렬
    while (true) {
        bool bFinish = true;  // true => 더이상 정렬할 것이 없다.
        // 정렬이 완료되면 if문에 걸리지 않는다.
        int iLoop = _pArr->iCount - 1;  // 데이터가 n개라면 비교 횟수는 (n-1)번
        for (int i = 0; i < _pArr->iCount - 1; ++i) {  // 수정: i + 1의 범위가 벗어나지 않도록
            // 왼쪽 숫자가 오른쪽 숫자보다 크다면
            // 주의! 데이터의 위치를 바꿀 때 기존의 데이터를 덮어쓰지 않도록 해야 한다.
            // => 임시 데이터 필요
            if (_pArr->pInt[i] > _pArr->pInt[i + 1]) {
                int iTemp = _pArr->pInt[i];
                _pArr->pInt[i] = _pArr->pInt[i + 1];
                _pArr->pInt[i + 1] = iTemp;
                bFinish = false;  // false => 아직 정렬할게 남아있다.
            }
        }

        // true이면 while문 탈출
        if (bFinish)
            break;
    }

    // _pArr이 관리하는 데이터를 SortFunc()를 이용해야 한다.
    SortFunc(_pArr->pInt, _pArr->iCount);
}

 

main.cpp

#include <stdio.h>
#include <iostream>
#include <time.h>
#include "Arr.h"

// 버블 정렬
    // 어디까지 정렬해줄지는 시작 주소와 그로부터 int 데이터가 몇 개가 연속적으로 채워져있는지 알아야 한다.
    // 가변 배열 전용이 아니다. 때문에 아무나 사용할 수 있다.
void BubbleSort(int* _pData, int _iCount)
{
    // 예외 처리 => 데이터가 0개, 1개면 정렬을 할 필요가 없다.
// 데이터가 1개 이하면 정렬하지 않는다.
    if (_iCount <= 1)
        return;

    // 오름차순 정렬
    while (true)
    {
        bool bFinish = true;  // true => 더이상 정렬할 것이 없다.
        // 정렬이 완료되면 if문에 걸리지 않는다.

        int iLoop = _iCount - 1;  // 데이터가 n개라면 비교 횟수는 (n-1)번
        for (int i = 0; i < iLoop; ++i)
        {
            // 왼쪽 숫자가 오른쪽 숫자보다 크다면
            // 주의! 데이터의 위치를 바꿀 때 기존의 데이터를 덮어쓰지 않도록 해야 한다.
            // => 임시 데이터 필요
            if (_pData[i] > _pData[i + 1])
            {
                int iTemp = _pData[i];
                _pData[i] = _pData[i + 1];
                _pData[i + 1] = iTemp;

                bFinish = false;  // false => 아직 정렬할게 남아있다.
            }
        }

        // true이면 while문 탈출
        if (bFinish)
            break;
    }
}

// 함수의 주소를 받는 법
void Test()
{
	// 코드 내용 생략
}

int main()
{
    // Test() 함수의 주소 받는 법
    void(*pFunc)(void) = Test;  // 반환 타입이 void이고, 인자도 없는 함수의 주소를 받는다.
    pFunc = Test;  // pFunc이 함수의 주소를 받는 변수이다.
    pFunc();  // 따라서 pFunc을 호출한다는 뜻은 Test() 함수를 호출한다는 것과 같다.
    // 대신에 선언 당시의 함수의 타입과 매치되는 함수의 주소만 받을 수 있다.
    // BubbleSort() 함수의 경우 int이므로 이에 맞는 함수의 주소를 받아야 한다.

    // BubbleSort() 이용
    int iArr[10] = { 80, 654, 213, 405, 22, 16, 248, };
    BubbleSort(iArr, 10);

    tArr s1 = {};
    // 배열 초기화
    InitArr(&s1);

    // 난수(랜덤) : 정의된 범위 내에서 무작위로 추출된 수
    //rand(); // 랜덤 함수

    // 무작위 숫자 테이블에서 숫자를 리턴한다.
    // 이때 숫자 테이블은 항상 일정해서 프로그램을 실행할 때마다 랜덤이어도 동일한 숫자가 나올 수 있다.
    // 그래서 랜덤 값 테이블에서 시작지점을 의미하는 seed를 사용한다.
    // 사용법 : srand(seed값);
    srand(time(nullptr));  // 시간은 중복이 될 수 없기 때문에 seed값으로 시간값을 넣어주면 된다.
    // 시간은 함수를 호출했을 때 당시의 시간값을 말한다.
    // 정수값으로 했을 때의 시, 분, 초, 날짜 이런 것들을 정수 안에 넣어서 그 값을 seed값으로 쓰기 때문에 절대 겹칠 수가 없다.
    // 지금 이 순간의 시간은 지금밖에 없다.
    // 시간 값을 읽어와서 랜덤 함수 페이지에 seed값을 활용하고 해당 페이지의 값을 랜덤으로 읽어온다.
    // 물론 이것도 완벽한 난수는 아니다.
    // 3D에서 쉐이더에서 사용할 수 없다.
    // 쉐이더에서는 동일 시간대의 난수를 만들어내야 된다.
    // 어떤 상황에는 시간의 영향을 받지 않고 나와야 되는 경우도 있다.

    // 1~100 사이의 숫자를 넣고 싶다.
    // 나온 무작위 숫자를 100으로 나누면 나머지는 0~99가 나온다.
    // 여기에 각각 1씩 더하면 1~100 사이가 나온다.
    for (int i = 0; i < 10; ++i)
    {
        int iRand = rand() % 100 + 1;

        PushBack(&s1, iRand);
    }

    // 그냥 출력
    printf("정렬 전\n");
    for (int i = 0; i < s1.iCount; ++i)
    {
        printf("%d\n", s1.pInt[i]);
    }

    // 정렬
    //Sort(&s1);
    Sort(&s1, &BubbleSort);  // 가변 배열이 관리하고 있는 데이터 s1을 BubbleSort() 함수를 이용해서 정렬해라.
    // 함수명 앞에 '&'를 붙여서 함수의 주소를 전달할 수도 있다.
    // Sort(&s1, &BubbleSort);
    // 함수는 이름 자체가 주소로 인정되기 때문에 이름만 적어도 상관은 없다.
    printf("\n");

    // 정렬 후 다시 출력
    printf("정렬 후\n");
    for (int i = 0; i < s1.iCount; ++i)
    {
        printf("%d\n", s1.pInt[i]);
    }

    // 배열 메모리 해제
    ReleaseArr(&s1);

    return 0;
}