note description: "Indexable data structure sorters using quick sort algorithm" legal: "See notice at end of class." status: "See notice at end of class." date: "$Date$" revision: "$Revision$" class QUICK_SORTER [G] inherit SORTER [G] create make feature -- Sort subsort_with_comparator (a_container: INDEXABLE [G, INTEGER]; a_comparator: PART_COMPARATOR [G]; lower, upper: INTEGER) -- Sort `a_container' according to `a_comparator''s -- comparison criterion within bounds `lower'..`upper'? local l, u, m, i, n: INTEGER pivot, lv, uv: G a_lower, a_upper: INTEGER lowers, uppers: ARRAY [INTEGER] do from n := upper - lower + 1 until n = 0 loop n := n // 2 i := i + 1 end i := i + 10 from create lowers.make_filled (0, 1, i) create uppers.make_filled (0, 1, i) lowers.put (lower, 1) uppers.put (upper, 1) i := 1 until i = 0 loop a_lower := lowers.item (i) a_upper := uppers.item (i) i := i - 1 l := a_lower u := a_upper if l < u then if u = l + 1 then lv := a_container.item (l) uv := a_container.item (u) if a_comparator.less_than (uv, lv) then a_container.put (lv, u) a_container.put (uv, l) end else m := (l + u) // 2 pivot := a_container.item (m) a_container.put (a_container.item (a_upper), m) from until l >= u loop from until l >= u or else not a_comparator.less_than (a_container.item (l), pivot) loop l := l + 1 end from u := u - 1 until u <= l or else not a_comparator.less_than (pivot, a_container.item (u)) loop u := u - 1 end if l < u then lv := a_container.item (l) a_container.put (a_container.item (u), l) a_container.put (lv, u) l := l + 1 end end a_container.put (a_container.item (l), a_upper) a_container.put (pivot, l) if l - 1 > a_lower then i := i + 1 lowers.force (a_lower, i) uppers.force (l - 1, i) end if l + 1 < a_upper then i := i + 1 lowers.force (l + 1, i) uppers.force (a_upper, i) end end end end end note copyright: "[ Copyright (c) 1984-2009, Eiffel Software and others Copyright (c) 2000, Eric Bezault and others ]" license: "[ Eiffel Forum License v2 (see http://www.eiffel.com/licensing/forum.txt) MIT License (see http://www.eiffel.com/licensing/mit.txt) ]" source: "[ Eiffel Software 5949 Hollister Ave., Goleta, CA 93117 USA Telephone 805-685-1006, Fax 805-685-6869 Website http://www.eiffel.com Customer support http://support.eiffel.com ]" end