Quickselect algorithm: Difference between revisions
Add CLU
(Added solution for Action!) |
Not a robot (talk | contribs) (Add CLU) |
||
Line 807:
{{out}}
<pre>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</pre>
=={{header|CLU}}==
<lang clu>quick = cluster [T: type] is select
where T has lt: proctype (T,T) returns (bool)
aT = array[T]
sT = sequence[T]
rep = null
swap = proc (list: aT, a, b: int)
temp: T := list[a]
list[a] := list[b]
list[b] := temp
end swap
partition = proc (list: aT, left, right, pivotIndex: int) returns (int)
pivotValue: T := list[pivotIndex]
swap(list, pivotIndex, right)
storeIndex: int := left
for i: int in int$from_to(left, right-1) do
if list[i] < pivotValue then
swap(list, storeIndex, i)
storeIndex := storeIndex + 1
end
end
swap(list, right, storeIndex)
return(storeIndex)
end partition
_select = proc (list: aT, left, right, k: int) returns (T)
if left = right then
return(list[left])
end
pivotIndex: int := left + (right - left + 1) / 2
pivotIndex := partition(list, left, right, pivotIndex)
if k = pivotIndex then
return(list[k])
elseif k < pivotIndex then
return(_select(list, left, pivotIndex-1, k))
else
return(_select(list, pivotIndex + 1, right, k))
end
end _select
select = proc (list: sT, k: int) returns (T)
return(_select(sT$s2a(list), 1, sT$size(list), k))
end select
end quick
start_up = proc ()
po: stream := stream$primary_output()
vec: sequence[int] := sequence[int]$[9,8,7,6,5,0,1,2,3,4]
for k: int in int$from_to(1, 10) do
item: int := quick[int]$select(vec, k)
stream$putl(po, int$unparse(k) || ": " || int$unparse(item))
end
end start_up</lang>
{{out}}
<pre>1: 0
2: 1
3: 2
4: 3
5: 4
6: 5
7: 6
8: 7
9: 8
10: 9</pre>
=={{header|COBOL}}==
| |||