[MIT] 파이썬을 이용한 알고리즘의 이해 - 삽입 정렬과 합병 정렬

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

 

✔  정렬

⁉️ 정렬이란?

 배열의 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 것입니다.

 

⁉️ 왜 정렬을 해야 할까?

• 대표적인 응용 사례 : 전화번호부 정리, 검색, mp3 파일 관리, 스프레드시트 등
• 정렬되면 쉬워지는 문제들 : 중간값 또는 가장 가까운 쌍 찾기, 이진탐색/통계적 이상치 확인
• 생소한 응용 사례 : 데이터 압축(정렬로 중복된 부분 검출), 컴퓨터 그래픽(앞에서 뒤로 화면 렌더링)

 

 

⁉️ 삽입 정렬

👀 삽입 정렬이란?

 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 방법입니다.

⏱ 시간 복잡도 : Θ(n^2)

삽입 정렬 예시

 

👀 이진 삽입 정렬이란?

 삽입 정렬을 개선한 알고리즘으로 삽입 정렬에 이진 탐색을 합친 정렬 알고리즘입니다.

⏱ 시간 복잡도 : Θ(n^2)

                           → Θ(n log(n))의 시간으로 비교를 하지만 스왑 때문에 Θ(n^2)입니다.

 

 

⁉️ 합병 정렬

👀 합병 정렬이란?

 분할 정복 알고리즘의 하나로 하나의 배열을 두 개의 균등한 크기로 분할하고 분할된 부분 배열을 정렬한 다음, 두 개의 정렬된 부분 배열을 합하여 정렬하는 방법입니다.

합병 정렬 예시

⏱ 시간 복잡도 : Θ(n log(n))

                           → c1을 무시한채로 cn 부분을 재귀 형태로 쪼개어서 트리 형태로 나타내어보면 다음과 같습니다.

⭐ 합병 정렬과 비교해서 삽입 정렬의 장점

 → 요소들을 정렬하기 위해서 추가적인 공간이 필요하지 않습니다.

 

 

 

👀 재귀 풀이에 대한 설명은 따로 필기하지 않았습니다.