알고리즘 코딩테스트 핵심이론 강의 - 병합 정렬

https://www.youtube.com/watch?v=KNKj8QSbRXE&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=18

📌 정렬 알고리즘

 

정렬 알고리즘정의

버블 (bubble)	데이터의 인접 요소끼리 비교하고 swap 연산을 수행하여 정렬
선택 (selection)	대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하며 정렬
삽입 (insertion)	대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬
퀵 (quick)	pivot 값을 선정해 해당 값을 기준으로 정렬
병합 (merge)	이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는
기수 (radix)	데이터의 자릿수를 바탕으로 비교해 데이터를 정렬

 

📌 병합 정렬

• 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합침
• 시간 복잡도는 O(nlogn)
• 나눌 수 없을 때 까지 나눈 후 다시 합치며 정렬

 

◾ 병합 정렬 핵심 이론

 

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

◾ 병합 정렬 수행방식

• N개의 그룹으로 나눈 후 2개씩 그룹을 합치며 오름차순으로 정렬
• 모두 합친 후 다시 또 2개씩 그룹을 합치며 오름차순 정렬

◾ 2개의 그룹을 병행하는 과정

• 투 포인터 개념을 사용하여 왼쪽 오른쪽 그룹을 병합.
• 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸씩 이동시킴

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html