게임 개발 로그

병합 정렬  병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘으로, 시간 복잡도는 O(nlogn)이다. 투 포인터 개념을 사용하여 배열의 원소를 나누며, 왼쪽, 오른쪽 그룹을 병합해간다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값(혹은 큰 값)을 배열에 추가하고, 포인터를 한 칸씩 이동시키는 방식이다.  합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. (위키백과 발췌)  n-way 합병 정렬의 개념은 다음과 같다.정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로..

퀵 정렬  퀵 정렬은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해서 정렬하는 알고리즘이다. 평균 시간 복잡도는 O(nlogn)이며 최악의 경우 O(n^2)의 시간 복잡도를 가진다.     퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 ..