[알고리즘] Merge Sort and Selection Sort

 

• Insertion sort의 입력 : a list of keys + a new k

   

• Merge Sort

Running time :

 

• A divide-and-conquer approach :

1. Divide
2. Conquer
3. Combine

   

    

   

    

   Pseudo Code

   

    

   1. p=r 인 경우를 제외하고는 모두 성립. 즉, key가 하나일 때를 제외하기 위해 만든것

   2. 큐를 반으로 나눈다

   3~4. Merge-sort를 재귀함
   5. Merge

    

   Time

   

    

   결론적으로

   

    

   

   

    

   Recursive 문제에서

   

    

   첫째항 : subproblem의 개수*subproblem의 사이즈(기존대비)

    

   따라서

    

    

    

• Binary Search

  Binary Search 의 시간복잡도

  

   

   

• Selection Sort

  구버전의 시간복잡도 : n+n-1+n-2+ … 1 = Θ(n^2)

   

   

  [ 정리 ]

  	시간복잡도 Best	시간복잡도 Worst
  Insertion	Θ(n)	Θ(n^2)
  Merge	Θ(nlgn)	Θ(nlgn)
  Selection	Θ(n^2)	Θ(n^2)

   

  • Insertion Sort는 Stable (몇 개의 key만 움직이면 된다)
  • Selection Sort 는 Stable
  • Merge Sort 는 Unstable. Output을 담는 Array가 따로 필요하다

    즉, Merge sort는 Selection sort보다 빠르지만 Memory Requirement가 더 크다.