MIT - Introduction to Algorithms
- Lecture 3. Insertion sort, merge sort
삽입 정렬과 합병 정렬 Review
Copyright to MIT & Srini Devadas & Erik Demaine
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
code, data, note pdf : https://courses.csail.mit.edu/6.006/fall11/notes.shtml
한글 번역과 슬라이드를 보고싶은 분은 Edwith - 파이썬을 이용한 알고리즘의 이해 항목 강의를 참조하세요.
URL : https://www.edwith.org/introalgorithm/
아래 그림들은 위 URL에서 다운받은 note를 기반 pdf입니다.
왜 Sorting을 배워야하는지 삽입 정렬부터 발전시켜나가는 정렬을 보게될 것
합병 정렬 Merge Sort의 경우 재귀 해결법 Recurrence Solving을 통해 진행
Overview : phone book
많은 이름들과 전화번호들을 정렬을 이용해 정리해야함
Problem that become easy once items are sorted
정렬이 되고 나면 문제는 쉬워짐
Finding a median
array A[0:n] unsorted -> B[0:n] sorted
sorted list의 경우 median을 찾는 것이 상수 시간의 복잡도를 가지기 때문에 훨신 쉬움
median : B[n/2]
A[0:n] looking for specific item k
찾는데 선형시간
sorted B[0:n], compare k to B[n/2]
Computer Graphics using sorting
컴퓨터 그래픽은 앞에서 뒤로 랜더링이 진행되는데 랜더링할 때 앞에 커다란 불투명한 객체가 있다면 먼저 랜더링하고 싶을 것. 그러면 커다란 객체로 가려진 다른 객체들을 랜더링 할 필요가 없기때문에 앞에서부터 뒤로 정렬
그러나 투명도가 걱정된다면 뒤에서 앞으로 랜더링
정리해서 말하면 중요도가 높은 것을 먼저 처리하기 위해 앞에서부터 랜더링을 했다.
데이터 압축 또한 중복되는 것에 대해 정렬하는 것이 효율적으로 정렬할 수 있다.
정렬은 굉장히 중요한 서브루틴subroutine
cf) 일부 프로그래밍 언어에서 함수와 서브루틴subroutine을 구분.
파스칼, 포트란에서 반환값이 없는 경우 서브루틴, 반환값이 있으면 함수
그러나 C에서는 함수와 서브루틴이 동의어
서브루틴 : Divide & Conquer을 위한 Method로 이해
위키피디아, 구글 검색은 칵테일 정렬, 바이토닉 정렬과 같은 모든 정렬이 있고 각각의 정렬 알고리즘마다의 목적이 있다.
1. Insertion sort 삽입 정렬
pseudocode 의사코드로 설명할 것
$\theta(n^2)$
숫자를 셀 때 연산의 관점에서 무엇은 셌는가
말하지 않은 가정 : 비교와 스왑을 동일한 하나의 연산으로 취급 : 대부분의 컴퓨터에서는 True
하나의 기계어 명령으로 수행가능
그러나 레코드들이 존재하고 레코드들을 위한 비교 함수가 그 자체로 메소드나 호출 서브루틴이라면 포인터와 참조하는 것만으로도 스왑이 가능하지만 비교는 더 복잡하고 비용이 듬
비용 : 비교 > 스왑
expensive : compare > swap
그러나 우리는 비교와 스왑의 비용이 같다고 가정 : compare : $\theta(n^2)$, swap : $\theta(n^2)$
그러나 다른 가정
Compare >> swaps $\theta(n^2)$ comparsion cost
pairwise swaps -> Binary Search
Do a binary search on A[0:i-1] already sorted in $\theta(log i)$ time
$\theta(nlogn)$ compare
그러나 sorted된 list나 array에 insert넣는다는 것은 넣은 자리 이후의 값들에 대해서는 오른쪽으로 움직여야하기 때문에
swap : $\theta(n^2)$
그럼 $\theta(nlogn)$ Insertion Sort가 있나? 없음
Search만 하는데 log n 시간임
Binary Tree의 경우 높이에 해당하는 log n과 그 해당 level의 node 조사는 상수텀
삽입 정렬이 합병 정렬보다 나은 점은?
삽입 정렬은 제자리 정렬이기에 추가 공간이 필요가 없다.
이에 반해 합병 정렬은 L과 R을 재정렬하기 위한 다른 배열이 필요하다.
Merge Sort $\theta(n)$ auxiliary space
In-place Sort => $\theta(1)$ constant auxiliary space
auxiliary space : temporary space to swap element
수십억개와 같이 많은 수가 있다면 메모리를 더 잡아먹는 방법이 합병 정렬이 될 것
시간복잡도에서 큰 고려 대상
In-place Mearge Sort 비실용적인 측면도 있고 상수 인자 수준 정도로 속도가 별루이며 \theta(nlog n). 실행 시간은 \theta(n)의 보조 공간을 쓰는 일반 합병 정렬보다 훨씬 좋지 않기에 잘 쓰지 않는다.
Mergesort in Python = $2.2 nlog n \mu s$
Insertion sort Python = $0.2 n^2 \mu s$
Insertion sort C = $0.01n^2 \mu s$
n>4000 speed Compete : merage sort in Python > Insertion in C
