2022_07_12_Algorithm

개선된 정렬 알고리즘

• 퀵 정렬 : 분할 알고리즘을 기본으로 하며 nlogn의 시간 복잡도를 갖음
• 병합 정렬 : 분할 정복 방식을 사용해 데이터를 분할하고 집합을 정렬하며 합치는 알고리즘
• 기수 정렬 : 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교 한다.

병합 정렬 과정

1. 집합을 2개씩의 그룹으로 지속적으로 분할합니다. 예를 들면 8개 요소가 있는 배열이면 2개씩 4그룹으로 나누어 오름차순정렬합니다.
2. 투 포인터 알고리즘을 이용하여 왼쪽, 오른쪽 그룹을 병합합니다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하며 추가한 쪽의 포인터를 이동합니다.