読者です 読者をやめる 読者になる 読者になる

ボクココ

サービス開発を成功させるまでの歩み

明日が休みでないと知って、急いで作りました。

今日は筆記試験の後はゆっくりしてようと思ったら、明日は祖父の33?回忌らしく一日空きそうもないので、プログラミングを早いうちにやっておきます。
今日はみなさんお待ちかね?のクイックソートです。マージソート作った後だから、それなりに作りやすかった。 ただ、ソースコードのコメントの所だけ苦戦してしまった。このコードの


while(j-=1)do
break if a[j]<=x
end
を、最初はこうしてた。

while(a[j]<=x)do j-=1 end
似ている部分が多いが、後者だと無限ループに陥る。
先に1引いてるか引いてないかの違いでかなり変わるのでご注意を。

def partition(a,p,r)
x=a[p] #ピボットを最初の要素に設定
i=p-1 #iを最初の要素の一個前として設定。
j=r+1 #同様。理由は以下

while(1)
#ここで大枠のwhileを一回繰り返したらjを1引かないといけない。
#そうしないと移動ができない(説明しにくい)
while(j-=1)do
break if a[j]<=x
end
while(i+=1)do
break if a[i]>=x
end

if i<j
a[i],a[j]=a[j],a[i]
else
return j
end
end
end
#クイックソート。元はマージソートに似てる
def quick_sort(a,p,r)
if p<r
q=partition(a,p,r)
quick_sort(a,p,q)
quick_sort(a,p+1,r)
end
end

それでは! 次回は特殊なソートを扱っていきたいと思います。
そしてハッシュ、2分探索などに進んでいきます!