Chap04. Sorting

Insertion Sort :: O($n^2$)

• Analysis
  Worst-Case Complexity
  
  Average Behavior
  shiftVacRec가 핵심
  
  첫번째 인덱스만 따로 빼 준 이유는 앞의 원소와 크기를 비교할 필요가 없기 때문에 1회 비교
  
• Optimality
  인접한 원소끼리 비교하고 위치를 바꾸어 줌
  데이터 탐색 시 순차 접근만 가능
  따라서 연산에 제한 조건이 존재할 때에는 optimal하지만 일반적으로는 그렇지 않음

Quick-Sort :: O($nlgn$)

* W(n)는 느리지만(Insertion Sort와 동일), A(n)이 빠름

• Divide and Conquer
  1 . divide : 문제를 여러 개의 작은 문제로 나누어 줌
  2 . conquer : sub problem들을 해결하는 단계. 재귀적으로 해결
  3 . combine : sub problem들의 solution을 합쳐 원래 문제의 solution으로 만듦

solve(I)
n = size(I)
if (n ≤ smallsize)
	solution = directlySolve(I);	// conquer
else
	divide I into I1, …, Ik.
	for each i in {1, …, k}
		Si = solve(Ii);
	solution = combine(S1, …, Sk);
return solution;

• Strategy
  1 . divide-and-conquer : 적어도 하나의 원소는 정렬시킬 수 있음
  2 . randomization : pivot x를 랜덤으로 선택함
  
• Partition(group G) :: O(n)

Algorithm partition(S, p)
	/* Input: sequence S, position p of pivot
	Output: subsequences L, E, G of the
		elements of S less than, equal to,
		or greater than the pivot, resp. */
	L, E, G <- empty sequences
	x <- S.remove(p)			// O(1) time
	while ~S.isEmpty()			// O(n) iterations
		y <- S.remove(S.first())	// O(1) time
		if y < x
			L.insertLast(y)		// O(1) time
		else if y = x
			E.insertLast(y)		// O(1) time
		else { y > x }
			G.insertLast(y)		// O(1) time
	return L, E, G

• Worst-case Running Time : O(n)