[게임 프로그래머 입문 올인원] STL Algorithms : 기본정렬 (78강)

A. STL Algorithms : 기본 정렬

1. 기본 정렬의 기초

a. 기본 정렬이란?

🌟 디폴트 정렬(default sorting), 기본 정렬 알고리즘(default sorting algorithm)을 의미

 

• std::sort 함수를 통해 수행
• 이 함수는 퀵 정렬(Quick Sort)을 기반으로 한 기본 정렬 알고리즘을 사용
• STL의 정렬 알고리즘 중에서 가장 일반적으로 사용되는 정렬 방법
• 효율적인 성능을 제공

 

💥 하지만 데이터의 특성에 따라 다른 정렬 알고리즘을 사용하는 것이 더 효율적일 수도 있으므로 상황에 맞게 선택하여 사용

 

💙 게임에서 정렬이 필요한 경우

인벤토리의 정렬기능
자동사냥의 몬스터 정렬

즉, 그 순간에 정렬이 필요한 경우에 사용됨 (n log n 이라 자주사용하면 안됨)

 

b. std::sort 함수

std::sort 함수는 일반적으로 퀵 정렬을 사용하여 정렬을 수행하지만

표준에 따라 다른 정렬 알고리즘을 사용할 수 있음

 

📘 문법

template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);

//두 개의 반복자(first: 정렬의 시작 지점, last: 정렬의 끝)를 인자로 받아 범위 내의 요소들을 정렬
//범위의 요소들을 오름차순으로 정렬

⏳ 예제

 

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};

    // 벡터 내 요소들을 기본 정렬
    std::sort(numbers.begin(), numbers.end());

    // 정렬된 요소들 출력
    std::cout << "Sorted numbers: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

 

2. 기본정렬의 종류

a. 버블 정렬

🌟 서로 인접한 두 요소를 비교하면서 필요에 따라 값을 교환하는 정렬

 

1. 데이터 개수 구하기
2. 이중 포문을 사용해 개수만큼 비교하기 (마지막은 필요없음)
3. 바꿔치기하기

 

시간복잡도 : 최선, 평균, 최악의 경우 모두 O(n^2)

 

b. 선택 정렬

🌟 배열을 순회하면서 최솟값을 찾아 그 값을 배열의 앞쪽으로 이동시키는 방식

 

버블정렬과 코드도 비슷함 즉, 비슷하게 비효율적

 

1. 데이터 개수 구하고
2. 개수만큼 스캔을 하면서 제일 작은 후보를 교체시켜주기
3. 배열 스왑해주기

 

시간 복잡도 : 최선, 평균, 최악의 경우 모두 O(n^2)

 

c. 힙정렬

🌟 특정한 종류의 이진 트리인 힙(heap)을 이용하여 정렬을 수행하는 알고리즘

 

힙은 일종의 완전 이진 트리 (부모 노드가 자식 노드보다 크거나 작은 값을 가지는 구조)

우선순위큐를 사용해서 구현하면 쉽다 

 

1. 힙 구축(Build Heap): 배열의 요소들을 힙 속성을 만족하도록 Bottom-Up 방식을 사용하여 주어진 배열을 힙으로 구축
   • 모든애들을 다 꺼내서 우선순위 큐에 넣어준다
2. 벡터를 밀어준다
3. 힙 정렬(Heapify): 힙의 루트 노드를 배열의 마지막 요소와 교환하고, 배열의 크기를 하나 줄임. 이후 교환된 루트 노드를 다시 힙 속성을 만족하도록 조정하여 정렬. 반복해서 완료

 

시간복잡도:  항상 O(n log n)

 

모든 단계에서 반복적으로 이진 트리의 높이에 비례하는 작업을 수행해 전체적인 시간 복잡도가 O(n log n)

 

➡ 대부분의 효율적인 정렬은 거의 다 n log n

 

d. 병합정렬 (중요)

이 자체보다 테크닉(분할 정복)이 더 중요함

 

분할 정복 알고리즘은 분할했다고 알고리즘이 달라지는게 아니니까

분할한 데이터를 다른 컴퓨터에서 연산하게 할 수 있다는 이점이 있음

 

1) 분할정복(Divide and Conquer)

 

• 분할(Divide) : 문제를 단순하게 분할
• 정복(Conquer) : 문제를 해결
• 결합(Combine) : 취합하여 마무리

 

점점 작은 단위로 분할

 

순서를 맞춰서 다시 붙여준다

 

2) 분할

 

영역을 가지고 작업하는 방식(인덱스)으로 함

더이상 분할을 못하게 되면 리턴

데이터를 재귀함수 형식으로 계속 분할한다

 

 

3) 정복

 

나뉜 데이터를 다시 합쳐주는데 임시 벡터를 사용함

 

데이터를 하나씩 뽑아서 넣어주는식으로 작업

먼저끝난것 확인해 나머지애들을 스캔해 넣어줌

 

4) 결합 

 

 

5) 시간복잡도 : 0(n log n)

 

퀵정렬은 다음글로...

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -