Ruby実装挿入ソートアルゴリズムおよびステップアップの2パス挿入ソートコード例
2792 ワード
ベースは、並べ替えられたテーブルにレコードを挿入し、レコードが1つ増えた順序付きテーブルを得る.そして、最も重要なのは、現在の要素よりも大きなレコードを後ろに移動して、「自分」が挿入する位置を空けることです.n−1パス挿入が完了すると、記録は秩序シーケンスである.
コードを書き始めたばかりの頃、x
最初は戸惑ってx.class,tarray[j].を出力しました.classですが、両方の出力はFixnumです.その後、RubyのArrayクラスは他のものとは異なり、Rubyでは1つのArrayオブジェクトに異なるタイプの要素を格納することが許可されており、aの1つの要素がxに付与された後、xと比較したa[i]がFixnumタイプであるかどうかは判断できないため、エラーを報告するのは私自身の理解にすぎない.
ステップ2の挿入ソートは、折半挿入ソートに基づいています.
def insertSort(tarray)
i=1
while(i < tarray.size) do
if tarray[i] < tarray[i-1]
j=i-1
x=tarray[i]
#puts x.class
#puts tarray[i].class
tarray[i]=tarray[i-1]#
while(x< tarray[j].to_i) do# ，
tarray[j+1]=tarray[j]
#puts tarray[j].class
j=j-1
end
tarray[j+1]=x
end
i=i+1
end
end
a=[5,2,6,4,7,9,8]
insertSort(a)
print a
[2, 4, 5, 6, 7, 8, 9]>Exit code: 0
コードを書き始めたばかりの頃、x
final.rb:10:in `
最初は戸惑ってx.class,tarray[j].を出力しました.classですが、両方の出力はFixnumです.その後、RubyのArrayクラスは他のものとは異なり、Rubyでは1つのArrayオブジェクトに異なるタイプの要素を格納することが許可されており、aの1つの要素がxに付与された後、xと比較したa[i]がFixnumタイプであるかどうかは判断できないため、エラーを報告するのは私自身の理解にすぎない.
ステップ2の挿入ソートは、折半挿入ソートに基づいています.
def two_way_sort data
first,final = 0,0
temp = []
temp[0] = data[0]
result = []
len = data.length
for i in 1..(len-1)
if data[i]>=temp[final]
final +=1
temp[final] = data[i]
elsif data[i]<= temp[first]
first = (first -1 + len)%len
temp[first] = data[i]
else
if data[i]>1
if data[i]>temp[m]
low = m + 1
else
high = m -1
end
end
j = first - 1
first -=1
while j < high do
temp[j] = temp[j+1]
j +=1
end
temp[high] = data[i]
else
low =0
high = final
while low <=high do
m =(low + high)>>1
if data[i]>=temp[m]
low = m + 1
else
high = m - 1
end
end
j = final + 1
final +=1
while j > low do
temp[j] = temp[j-1]
j -=1
end
temp[low] = data[i]
end
end
p temp
end
i = 0
for j in first..(len - 1)
result[i] = temp[j]
i +=1
end
for j in 0..final
result[i] = temp[j]
i +=1
end
return result
end
data = [4,1,5,6,7,2,9,3,8].shuffle
p data
result = two_way_sort data
p result