quick.nim

import sequtils, system, random
discard """クイックソート
先頭をピボットに任命->ピボットより小さいのを左に、大きいのを右に->左右それぞれにもう一度
ソート対象の動的配列は?->seqで
"""
proc qsort(arr:var seq[int],l:int,r:int):void

var testdata:seq[int]
testdata= @[0,1,2,3,4,5,6,7,8,9,10]
randomize()
for i in 0..10:
  swap(testdata[i],testdata[i + rand(max= 10 - i )])
  echo testdata[i]

qsort(testdata,0,10)
echo testdata

proc qsort(arr:var seq[int],l:int,r:int):void=
  let p=arr[l]
  var
    i=l
    j=r
#  echo "p=",p,",l=",l,",r=",r
  if r-l<1:return
  while i<=j:
    while arr[i]<p:
      i+=1
    while arr[j]>p:
      j-=1
    if i==j:break
    if i<j:
#      echo "swaped ",arr[i],"<=>",arr[j]
      swap(arr[i],arr[j])
      #var tmp=arr[i]
      #arr[i]=arr[j]
      #arr[j]=tmp
      i+=1
      j-=1
  echo arr
#  echo "i=",i,",j=",j
  qsort(arr,l,i-1)
  qsort(arr,j+1,r)