TS's memorandom

クイックソートループ版

2/14の続き。ループ版のクイックソートも考えてみたのでメモ。

def qsort_loop(array)
  result = array.dup
  start = 0
  last = array.size - 1
  rest = []
  while (start < array.size - 1)
    while (start < last)
      pivot = start
      current = start + 1
      pivot_val = result[pivot]
      while (current <= last)
        current_val = result[current]
        if current_val < pivot_val
          if (current - pivot > 1)
            result[current] = result[pivot + 1]
          end
          result[pivot] = current_val
          pivot=pivot + 1
        end
        current = current + 1
      end
      result[pivot] = pivot_val
      rest.push [pivot+1, last] 
      last = pivot - 1
    end
    start, last = rest.pop
  end
  result
end

data = (1..100).to_a.map { 1 + (rand 200) }
p data
p qsort_loop(data)

1回分の処理の基本形は比較的簡単に作れる。あとはその処理を繰り返しで適用するための形を考えるのにちょっとてまどった。