On Friday, 10 July 2015 at 00:39:16 UTC, Xinok wrote:
On Thursday, 9 July 2015 at 21:57:39 UTC, Xinok wrote:
I found this paper which describes an in-place algorithm with
O(n) time complexity but it's over my head at the moment.
[snip]
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.25.5554&rep=rep1&type=pdf
from the pdf, above, in case readers, like me, don't know the
context of a Stable Partition implementation:
Stable minimum space partitioning
in linear time
Jyrki Katajainen1 and Tomi Pasanen2
Abstract.
In the stable 0-1 sorting problem the task is to sort an array of
n elements with
two distinct values such that equal elements retain their
relative input order.
Recently, Munro, Raman and Salowe [BIT 1990] gave an algorithm
which solves
this problem in O(nlog*n)
3 time and constant extra space. We show that by a
modification of their method the stable 0-1 sorting is possible
in O(n) time and
O(1) extra space. Stable three-way partitioning can be reduced to
stable 0-1
sorting. This immediately yields a stable minimum space
quicksort, which sorts
multisets in asymptotically optimal time with high probability.
CR categories: E.5, F.2.2.
The stable 0-1 sorting problem is defined as follows: Given an
array of n elements
and a function f mapping each element to the set {0,1}, the task
is to rearrange the
elements such that all elements, whose f-value is zero, become
before elements, whose
f-value is one. Moreover, the relative order of elements with
equal f-values should be
maintained. For the sake of simplicity, we hereafter refer to
bits instead of the f-values
of elements.
Stable partitioning is a special case of stable 0-1 sorting,
where the f-values are
obtained by comparing every element xi
to some pivot element xj (which will not take part in
partitioning):
