생각하는 프로그래밍

칼럼 11

11.1 삽입정력(Insertion sort)
 - 카드를 섞는것과 같다.  이미 정렬되어있을경우 Good

for i = [1, n)
    for (j = i; j >0 && x[j-1] > x[j]; j--)
         swap(j-1, j)

swap을 변수temp를 사용하는 것으로 대체할수 있고
t=x[i]를 For 밖으로 빼낼수있다

11.2 간단한 퀵 정렬(Quick sort)
랜덤하게 정렬되어있을때 좋음

void qsort(l, u)
  if l >= u then
     return;
 /* goal: partition array around a particular value,
      which is eventually placed in its correct position p
  */
   qsort(l, p-1)
   qsort(p+1, u)

m이 중앙값 i가 진행하는 값

void qsort1(l, u)
  if (l > u)
    return
  m = l
  for i = [l+1, u]
    if x[i] < x[l]
      swap(++m, i)
  swap(l, m)

랜덤하지않을경우를 고려해서 수정가능
cut off의 크기를 늘려서 sub set의 정렬은 insertion sort를 사용한다.