Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted
(Added Eiffel version)
(→‎{{header|Eiffel}}: Added contracts, general cleanup)
Line 1,038:
 
quicksort (list: ARRAY [COMPARABLE]): ARRAY [COMPARABLE]
require
not_void: list /= Void
local
less_a: ARRAY [COMPARABLE]
Line 1,043 ⟶ 1,045:
more_a: ARRAY [COMPARABLE]
temp: ARRAY [COMPARABLE]
return: ARRAY [COMPARABLE]
pivot: COMPARABLE
i: INTEGER
Line 1,050 ⟶ 1,051:
create more_a.make_empty
create equal_a.make_empty
create returnResult.make_empty
if list.count <= 1 then
Result := list
else
pivot := list [list.lower]
fromacross
ilist :=as list.lowerli
untilinvariant
less_a.count + equal_a.count + more_a.count <= list.count
i > list.upper
loop
if list [i]li.item < pivot then
less_a.force (list [i]li.item, less_a.count)
elseif list [i]li.item = pivot then
equal_a.force (list [i]li.item, equal_a.count)
elseif list [i]li.item > pivot then
more_a.force (list [i]li.item, more_a.count)
end
i := i + 1
end
 
temp := quicksort (less_a)
across
temp as t
loop
returnResult.force (t.item, returnResult.count)
end
across
equal_a as eq
loop
returnResult.force (eq.item, returnResult.count)
end
temp := quicksort (more_a)
across
temp as t
loop
returnResult.force (t.item, returnResult.count)
end
Result := returnResult
end
ensure
same_size: list.count = Result.count
end
 
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Quicksort"