■

おれもとっぷこーだーになりたいけどぷろぐらみんぐこんてすとの問題とかむずかしすぎてぜんぜんとけない！ → とりあえず解説つきの各種過去問をかき集めて100問くらい解いて慣れるところから始めよう(手の施しようのない受験数学脳) → 10問くらい解いた → あー、はいはい、ダイクストラ法ね、あー、知ってるよ、うん、知ってる、マジでマジで、説明できないけど → 調べた → あー、プライオリティキュー使うのか、はいはい、知って(以下略) → 調べた → なるほど、ヒープで実装できるのか、はいはい、ヒープね(以下略) → 調べた → あー、そういやヒープソートとかあったなあ、いや、(以下略) → 調べた → そういやソートアルゴリズムって色々あってなんとなく理解しているけど何も見ないで書ける自信がぜんぜんない…… → http://www.geocities.jp/m_hiroi/light/index.html を読んだ → とりあえずバブルソート、選択ソート、挿入ソート、シェルソート、マージソート、ヒープソート、クイックソート、ラディックスソートは完全に理解して何も見ないで書けるようになったけど…… なんかこれ、すげえ早く書けたらおもしろくね？(明らかに迷走)

という経緯で先週の三連休の半分以上を費やして何も見ないで下のものを13分くらいで書けるようにしたものの、あまり早く書けるようにはならなかったし、そもそもあまり意味がないような気がしてきた。気付くのおせえ。

def bubble_sort(L):
  size = len(L)-1
  for i in range(size):
    for j in range(size, i, -1):
      if L[j] < L[j-1]:
        L[j-1], L[j] = L[j], L[j-1]
  return L

def selection_sort(L):
  size = len(L)
  for i in range(size-1):
    min = L[i]
    k = i
    for j in range(i+1, size):
      if L[j] < min:
        min = L[j]
        k = j
    L[k] = L[i]
    L[i] = min
  return L

def insertion_sort(L):
  for i in range(1, len(L)):
    a = L[i]
    j = i-1
    while 0 <= j and a < L[j]:
      L[j+1] = L[j]
      j -= 1
    L[j+1] = a
  return L

def shell_sort(L):
  size = len(L)
  gap = 1
  while gap < size/9: gap = gap*3+1
  while 0 < gap:
    for i in range(gap, size):
      a = L[i]
      j = i-gap
      while 0 <= j and a < L[j]:
        L[j+gap] = L[j]
        j -= gap
      L[j+gap] = a
    gap /= 3
  return L

def merge_sort(L, head, tail):
  if tail-head:
    mid = (head+tail)/2
    merge_sort(L, head, mid)
    merge_sort(L, mid+1, tail)

    i = mid+1
    j = 0
    k = head
    work = L[head:mid+1]
    while i <= tail and j < len(work):
      if work[j] < L[i]:
        L[k] = work[j]
        k += 1
        j += 1
      else:
        L[k] = L[i]
        k += 1
        i += 1
    while j < len(work):
      L[k] = work[j]
      k += 1
      j += 1
  return L

def heap_sort(L):
  size = len(L)
  for i in range(size/2-1, -1, -1):
    a = L[i]
    j = i
    while True:
      k = 2*j+1
      if size <= k: break
      if k+1 < size and L[k] < L[k+1]: k += 1
      if L[k] <= a: break
      L[j] = L[k]
      j = k
    L[j] = a

  for i in range(size-1, -1, -1):
    a = L[i]
    L[i] = L[0]
    j = 0
    while True:
      k = 2*j+1
      if i <= k: break
      if k+1 < i and L[k] < L[k+1]: k += 1
      if L[k] <= a: break
      L[j] = L[k]
      j = k
    L[j] = a
  return L

def quick_sort(L, head, tail):
  i = head
  j = tail
  pivot = L[(head+tail)/2]
  while True:
    while L[i] < pivot: i += 1
    while pivot < L[j]: j -= 1
    if j <= i: break
    L[i], L[j] = L[j], L[i]
    i += 1
    j -= 1
  if head < i-1: quick_sort(L, head, i-1)
  if j+1 < tail: quick_sort(L, j+1, tail)
  return L

def radix_sort(L):
  size = len(L)
  work = [0]*size
  n = 256
  count = [0]*n
  for i in range(4):
    shift = i*8
    for j in range(n):
      count[j] = 0
    for j in range(size):
      count[(L[j]>>shift)&0xff] += 1
    for j in range(1, n):
      count[j] += count[j-1]
    for j in range(size-1, -1, -1):
      k = (L[j]>>shift)&0xff
      count[k] -= 1
      work[count[k]] = L[j]
    L, work = work, L
  return L

if __name__ == '__main__':
  import sys
  import random
  N = int(sys.argv[1])
  L = [random.randint(1, N*10) for i in range(N)]
  print 'original :', L
  print '----'
  print 'bubble   :', bubble_sort(L[:])
  print 'selection:', selection_sort(L[:])
  print 'insertion:', insertion_sort(L[:])
  print 'shell    :', shell_sort(L[:])
  print 'merge    :', merge_sort(L[:], 0, N-1)
  print 'heap     :', heap_sort(L[:])
  print 'quick    :', quick_sort(L[:], 0, N-1)
  print 'radix    :', radix_sort(L[:])