Sorting algorithms/Strand sort: Difference between revisions
Content added Content deleted
(Nimrod -> Nim) |
(→{{header|Ruby}}: used partition) |
||
| Line 1,426: | Line 1,426: | ||
<lang ruby>class Array |
<lang ruby>class Array |
||
def strandsort |
def strandsort |
||
a = |
a = dup |
||
result = [] |
result = [] |
||
until a.empty? |
until a.empty? |
||
v = a.first |
|||
sublist, a = a.partition{|val| v=val if v<=val} # In case of v>val, it becomes nil. |
|||
a.each_with_index.each_with_object([]) { |(val, idx), remove| |
|||
next if val <= sublist.last |
|||
sublist << val |
|||
remove << idx |
|||
}.reverse_each {|idx| a.delete_at(idx)} |
|||
result.each_index do |idx| |
result.each_index do |idx| |
||
break if sublist.empty? |
break if sublist.empty? |
||
result.insert(idx, sublist.shift) if sublist |
result.insert(idx, sublist.shift) if sublist.first < result[idx] |
||
end |
end |
||
result += sublist |
result += sublist |
||
| Line 1,452: | Line 1,448: | ||
p [1, 6, 3, 2, 1, 7, 5, 3].strandsort</lang> |
p [1, 6, 3, 2, 1, 7, 5, 3].strandsort</lang> |
||
{{out}} |
|||
result |
|||
<pre>[1, 1, 2, 3, 3, 5, 6, 7]</pre> |
<pre>[1, 1, 2, 3, 3, 5, 6, 7]</pre> |
||