Science and Technology news... :: View topic - The Partition-Exchange Sort algorithm

Richard Harter · Guest

The Partition-Exchange Sort algorithm

Partition-Exchange is a neologism; the algorithm discussed here
may be novel. In any event I haven>t seen it before.

The basic idea is quite simple. Suppose that we have an array X
that is divided into two parts, A and B, and that A is sorted,
i.e. X = {A,B}. Select the midpoint of A and use it as a pivot
to partition A and B. Partition A requires no work; partitioning

B is O(N) time.

After partitioning the array looks like this: X = {A1,A2,B1,B2}
where A1 and B1 are the "small" components of the partitions and
A2 and B2 the "big"components. We swap segments A2 and B1 to get

X = {A1,B1,A2,B2}. This again is an O(N) time operation.

Now we apply the same procedure recursively to {A1,B1} and
{A2,B2} until the unsorted components are sorted. Since each
pass halves the component lengths there will be O(log N) passes.
As a result the over-all cost is O(N*log N) time. The space
requirement will be O(log N) because of the recursion.

There remains the question: How does A get sorted? That is
simple enough. We sort an a small initial segment and
successively double the initial segment size by applying the
partition-exchange algorithm.

An actual implementation requires handling some end cases. The
partition should take into account elements of B that are smaller

or larger than any element of A. The algorithm must account for
either B1 or B2 or both being empty. With this in mind the
partition is {B0,B1,B2,B3} where

B0 contains all elements less than all elements of A.
B1 contains all elements not in B0 that are less than the
pivot.
B2 contains all elements >= the pivot that are not greater
then all elements of A.
B3 contais all elements greater than all elements of A.

The algorithm then is:

if B0 has content then
swap A and B0
sort B0
if B1 has content then
swap A2 and B1
process {A1,B1}
if B2 has content then
process (A2,B2)
if B3 has content then
sort B3

Some interesting points about this algorithm are:

(a) It is a "good" sort algorithm, where "good" means that it has
an average O(N*log N) time cost and an average O(log N) space

cost.
(b) It has "good" worst behaviour; the key is that partitions
reduce segment sizes geometrically. It can be shown that the
worst case time and space costs are still O(N*log N) and
O(log N) respectively, assuming no error in my analysis.

(c) The size of the array does not need to be known in advance.
The implication is that it can be used for sorting input from
streams.

None of this means that this algorithm is more efficient than the

more well-known algorithms; it is quite likely that it isn>t.
When I get the chance I will program a version and run some
tests.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It>s the only planet with chocolate.

Chris F Clark · Guest

[quote]Partition-Exchange is a neologism; the algorithm discussed here
may be novel. In any event I haven>t seen it before.
[/quote]
The idea has some merits. However, there is only a minimal guarantee
that the sizes of the B>s relative to the A>s are anywhere close in
size. You talk to that problem in your issues to resolve, but the
worst case looks easily to be some kind of situation when the pivot
you pick sorts all of the B>s the the one side and that happens
repetitively, for example how does your algorithm perform on a
completely reversed list.

Richard Harter · Guest

On Mon, 28 Jul 2008 11:08:22 -0400, Chris F Clark
<cfc@shell01.TheWorld.com> wrote:

[quote]Partition-Exchange is a neologism; the algorithm discussed here
may be novel. In any event I haven>t seen it before.

The idea has some merits. However, there is only a minimal guarantee
that the sizes of the B>s relative to the A>s are anywhere close in
size. You talk to that problem in your issues to resolve, but the
worst case looks easily to be some kind of situation when the pivot
you pick sorts all of the B>s the the one side and that happens
repetitively, for example how does your algorithm perform on a
completely reversed list.

[/quote]
How does it perform on a completely reversed list? Quite well
indeed, thank you. :-)

You are right, of course, that the sizes of the B>s can differ
significantly from the sizes of the A>s, but this is a
self-correcting problem. The essence of the matter is that
partitioning of B removes all values within B that are outside of
the box defined by A and treats them as sub-problems. For
example, a reversed list is handled by sorting the first half,
swapping the first and second halves, and then sorting the new
first half.

The problem occurs when all of the B>s stay within range. The
worst case is when all of the B>s lie between a successive pair
of A>s. In such case we must perform log n partitions to find a
new subproblem. The worst case happens when this feature is
present recursively in the data. In such case the time cost is
O(n * (log n)^2).

Thank you for the comments.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It>s the only planet with chocolate.

Gene · Guest

On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:
[quote]The Partition-Exchange Sort algorithm

Partition-Exchange is a neologism; the algorithm discussed here
may be novel. In any event I haven>t seen it before.

The basic idea is quite simple. Suppose that we have an array X
that is divided into two parts, A and B, and that A is sorted,
i.e. X = {A,B}. Select the midpoint of A and use it as a pivot
to partition A and B. Partition A requires no work; partitioning

B is O(N) time.

After partitioning the array looks like this: X = {A1,A2,B1,B2}
where A1 and B1 are the "small" components of the partitions and
A2 and B2 the "big"components. We swap segments A2 and B1 to get

X = {A1,B1,A2,B2}. This again is an O(N) time operation.

Now we apply the same procedure recursively to {A1,B1} and
{A2,B2} until the unsorted components are sorted. Since each
pass halves the component lengths there will be O(log N) passes.
As a result the over-all cost is O(N*log N) time. The space
requirement will be O(log N) because of the recursion.

There remains the question: How does A get sorted? That is
simple enough. We sort an a small initial segment and
successively double the initial segment size by applying the
partition-exchange algorithm.

An actual implementation requires handling some end cases. The
partition should take into account elements of B that are smaller

or larger than any element of A. The algorithm must account for
either B1 or B2 or both being empty. With this in mind the
partition is {B0,B1,B2,B3} where

B0 contains all elements less than all elements of A.
B1 contains all elements not in B0 that are less than the
pivot.
B2 contains all elements >= the pivot that are not greater
then all elements of A.
B3 contais all elements greater than all elements of A.

The algorithm then is:

if B0 has content then
swap A and B0
sort B0
if B1 has content then
swap A2 and B1
process {A1,B1}
if B2 has content then
process (A2,B2)
if B3 has content then
sort B3

Some interesting points about this algorithm are:

(a) It is a "good" sort algorithm, where "good" means that it has
an average O(N*log N) time cost and an average O(log N) space

cost.
(b) It has "good" worst behaviour; the key is that partitions
reduce segment sizes geometrically. It can be shown that the
worst case time and space costs are still O(N*log N) and
O(log N) respectively, assuming no error in my analysis.

(c) The size of the array does not need to be known in advance.
The implication is that it can be used for sorting input from
streams.

None of this means that this algorithm is more efficient than the

more well-known algorithms; it is quite likely that it isn>t.
When I get the chance I will program a version and run some
tests.

Richard Harter, c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
Save the Earth now!!
It>s the only planet with chocolate.
[/quote]
Richard,

This is very cool. Something like a cross-breeding of quicksort and
mergesort. I>m pretty sure it will not be fast, though. You>d like
to do the partition and exchange as elementwise "rotations", but you
can>t because you don>t know the sizes of b1 and b2 in advance.
Double handling for separate partition and exchange is expensive.

Oddly, a clean implementation may be possible for linked lists.

Gene

pete · Guest

Gene wrote:
[quote]On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:
The Partition-Exchange Sort algorithm

Partition-Exchange is a neologism; the algorithm discussed here
may be novel. In any event I haven>t seen it before.

The basic idea is quite simple. Suppose that we have an array X
that is divided into two parts, A and B, and that A is sorted,
i.e. X = {A,B}. Select the midpoint of A and use it as a pivot
to partition A and B. Partition A requires no work; partitioning

B is O(N) time.

After partitioning the array looks like this: X = {A1,A2,B1,B2}
where A1 and B1 are the "small" components of the partitions and
A2 and B2 the "big"components. We swap segments A2 and B1 to get

X = {A1,B1,A2,B2}. This again is an O(N) time operation.

Now we apply the same procedure recursively to {A1,B1} and
{A2,B2} until the unsorted components are sorted. Since each
pass halves the component lengths there will be O(log N) passes.
As a result the over-all cost is O(N*log N) time. The space
requirement will be O(log N) because of the recursion.

There remains the question: How does A get sorted? That is
simple enough. We sort an a small initial segment and
successively double the initial segment size by applying the
partition-exchange algorithm.

An actual implementation requires handling some end cases. The
partition should take into account elements of B that are smaller

or larger than any element of A. The algorithm must account for
either B1 or B2 or both being empty. With this in mind the
partition is {B0,B1,B2,B3} where

B0 contains all elements less than all elements of A.
B1 contains all elements not in B0 that are less than the
pivot.
B2 contains all elements >= the pivot that are not greater
then all elements of A.
B3 contais all elements greater than all elements of A.

The algorithm then is:

if B0 has content then
swap A and B0
sort B0
if B1 has content then
swap A2 and B1
process {A1,B1}
if B2 has content then
process (A2,B2)
if B3 has content then
sort B3

Some interesting points about this algorithm are:

(a) It is a "good" sort algorithm, where "good" means that it has
an average O(N*log N) time cost and an average O(log N) space

cost.
(b) It has "good" worst behaviour; the key is that partitions
reduce segment sizes geometrically. It can be shown that the
worst case time and space costs are still O(N*log N) and
O(log N) respectively, assuming no error in my analysis.

(c) The size of the array does not need to be known in advance.
The implication is that it can be used for sorting input from
streams.

None of this means that this algorithm is more efficient than the

more well-known algorithms; it is quite likely that it isn>t.
When I get the chance I will program a version and run some
tests.

Richard Harter, c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinoma.com
Save the Earth now!!
It>s the only planet with chocolate.

Richard,

This is very cool. Something like a cross-breeding of quicksort and
mergesort. I>m pretty sure it will not be fast, though. You>d like
to do the partition and exchange as elementwise "rotations", but you
can>t because you don>t know the sizes of b1 and b2 in advance.
Double handling for separate partition and exchange is expensive.

Oddly, a clean implementation may be possible for linked lists.
[/quote]
I think it would be difficult to come up with an algorithm
that was more naturally suited to linked lists,
than mergesort already is.

--
pete

Gene · Guest

On Jul 29, 11:13 am, c...@tiac.net (Richard Harter) wrote:
[quote]On Tue, 29 Jul 2008 07:35:40 -0400, pete <pfil...@mindspring.com
wrote:

Gene wrote:
On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:

[snip algorithm]

Richard,

This is very cool. Something like a cross-breeding of quicksort and
mergesort. I>m pretty sure it will not be fast, though. You>d like
to do the partition and exchange as elementwise "rotations", but you
can>t because you don>t know the sizes of b1 and b2 in advance.
Double handling for separate partition and exchange is expensive.

Thanks, I thought it was cool too. I came up with it when I was
thinking about ways to do in place merges.

You>re probably right about the speed, though the exchange cost
should be relatively low compared to the partition cost. The
swaps can be done using buffered block copies; most systems can
do high speed block moves.

Still, it might be fast enough to be useful when you want a good
worst case comparison sort. The principle candidate here is
heapsort, and it has locality problems.

Oddly, a clean implementation may be possible for linked lists.

I think it would be difficult to come up with an algorithm
that was more naturally suited to linked lists,
than mergesort already is.

I>m not sure what you mean by that. Quicksort works rather
nicely with linked lists.
[/quote]
Yes it does! When I>ve benchmarked, though, the mergesort always
seems to do better by a significant factor, at least when the
comparison cost is comparable to link munging.

Richard Harter · Guest

On Tue, 29 Jul 2008 07:35:40 -0400, pete <pfiland@mindspring.com>
wrote:

[quote]Gene wrote:
On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:
[/quote]
[snip algorithm]

[quote]
Richard,

This is very cool. Something like a cross-breeding of quicksort and
mergesort. I>m pretty sure it will not be fast, though. You>d like
to do the partition and exchange as elementwise "rotations", but you
can>t because you don>t know the sizes of b1 and b2 in advance.
Double handling for separate partition and exchange is expensive.
[/quote]
Thanks, I thought it was cool too. I came up with it when I was
thinking about ways to do in place merges.

You>re probably right about the speed, though the exchange cost
should be relatively low compared to the partition cost. The
swaps can be done using buffered block copies; most systems can
do high speed block moves.

Still, it might be fast enough to be useful when you want a good
worst case comparison sort. The principle candidate here is
heapsort, and it has locality problems.

[quote]
Oddly, a clean implementation may be possible for linked lists.

I think it would be difficult to come up with an algorithm
that was more naturally suited to linked lists,
than mergesort already is.
[/quote]
I>m not sure what you mean by that. Quicksort works rather
nicely with linked lists.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It>s the only planet with chocolate.

Richard Harter · Guest

On Tue, 29 Jul 2008 10:32:20 -0700 (PDT), Gene
<gene.ressler@gmail.com> wrote:

[quote]On Jul 29, 11:13=A0am, c...@tiac.net (Richard Harter) wrote:
On Tue, 29 Jul 2008 07:35:40 -0400, pete <pfil...@mindspring.com
wrote:

Gene wrote:
On Jul 28, 4:12 am, c...@tiac.net (Richard Harter) wrote:

[snip algorithm]

Richard,

This is very cool. =A0Something like a cross-breeding of quicksort and
mergesort. =A0I>m pretty sure it will not be fast, though. =A0You>d li=
ke
to do the partition and exchange as elementwise "rotations", but you
can>t because you don>t know the sizes of b1 and b2 in advance.
Double handling for separate partition and exchange is expensive.

Thanks, I thought it was cool too. =A0I came up with it when I was
thinking about ways to do in place merges.

You>re probably right about the speed, though the exchange cost
should be relatively low compared to the partition cost. =A0The
swaps can be done using buffered block copies; most systems can
do high speed block moves.

Still, it might be fast enough to be useful when you want a good
worst case comparison sort. =A0The principle candidate here is
heapsort, and it has locality problems.

Oddly, a clean implementation may be possible for linked lists.

I think it would be difficult to come up with an algorithm
that was more naturally suited to linked lists,
than mergesort already is.

I>m not sure what you mean by that. =A0Quicksort works rather
nicely with linked lists.

Yes it does! When I>ve benchmarked, though, the mergesort always
seems to do better by a significant factor, at least when the
comparison cost is comparable to link munging.
[/quote]
By about 20% I would imagine. The best possible comparison sort
requires ~ log2(n)-log2(e) comparisons per element. If I recall
correctly mergesort requires ~log2(n)-1 comparisons per element
whereas quicksort requires ~ 1.22*log2(n) comparisons per
element.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It>s the only planet with chocolate.

Guest

What is the difference between your Partition-Exchange Sort algorithm
and Chen>s Proportion Extend Sort algorithm?

Dann Corbit · Guest

<zxcb33@yahoo.com> wrote in message
news:7eea94f1-b974-45ea-b2a8-f4a91c0138f8@r35g2000prm.googlegroups.com...
[quote]What is the difference between your Partition-Exchange Sort algorithm
and Chen>s Proportion Extend Sort algorithm?
[/quote]
Symmetry Partition Sort by Jing-Chao Chen (an update of PE sort) is very
impressive:
http://arxiv.org/ftp/arxiv/papers/0706/0706.0046.pdf

Here is a comparison against J. L. Bentley and M. D. McIlroy>s NetBSD
excellent qsort() version:

NetBSD qsort():
distribution SAWTOOTH: max cratio 1.36, min 0.06, average 0.42 over 364
tests
distribution RAND: max cratio 1.08, min 0.06, average 0.43 over 364 tests
distribution STAGGER: max cratio 1.36, min 0.06, average 0.78 over 364 tests
distribution PLATEAU: max cratio 1.27, min 0.06, average 0.20 over 364 tests
distribution SHUFFLE: max cratio 1.56, min 0.06, average 0.75 over 364 tests
method COPY: max cratio 1.560, min 0.060, average 0.628 over 260 tests
method REVERSE: max cratio 1.357, min 0.060, average 0.612 over 260 tests
method FREVERSE: max cratio 1.364, min 0.060, average 0.625 over 260 tests
method BREVERSE: max cratio 1.347, min 0.060, average 0.762 over 260 tests
method SORT: max cratio 0.152, min 0.060, average 0.087 over 260 tests
method NEARSORT: max cratio 0.581, min 0.060, average 0.207 over 260 tests
method DITHER: max cratio 1.207, min 0.145, average 0.687 over 260 tests
Overall: average cratio 0.515 I=13, M=28, over 1820 tests

Adp_SymPsort():
distribution SAWTOOTH: max cratio 1.14, min 0.06, average 0.36 over 364
tests
distribution RAND: max cratio 1.06, min 0.06, average 0.40 over 364 tests
distribution STAGGER: max cratio 1.14, min 0.06, average 0.66 over 364 tests
distribution PLATEAU: max cratio 0.80, min 0.06, average 0.17 over 364 tests
distribution SHUFFLE: max cratio 2.38, min 0.06, average 0.47 over 364 tests
method COPY: max cratio 1.430, min 0.060, average 0.443 over 260 tests
method REVERSE: max cratio 2.375, min 0.060, average 0.480 over 260 tests
method FREVERSE: max cratio 1.278, min 0.060, average 0.611 over 260 tests
method BREVERSE: max cratio 1.286, min 0.060, average 0.525 over 260 tests
method SORT: max cratio 0.149, min 0.060, average 0.087 over 260 tests
method NEARSORT: max cratio 1.156, min 0.060, average 0.123 over 260 tests
method DITHER: max cratio 1.390, min 0.153, average 0.604 over 260 tests
Overall: average cratio 0.410 I=13, M=28, over 1820 tests

Richard Harter · Guest

On Tue, 29 Jul 2008 16:49:23 -0700 (PDT), zxcb33@yahoo.com wrote:

[quote]What is the difference between your Partition-Exchange Sort algorithm
and Chen>s Proportion Extend Sort algorithm?
[/quote]
Good question; thanks for the alert. I hadn>t heard of Chen>s
work before, which is not surprising since it appears to be
relatively new. At first glance the key idea is the same. I>m
not sure that he used the same strategy for outliers.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It>s the only planet with chocolate.


www.GetXFactor.com Leading Technology, Science, Agriculture News and information	Part of the Identityscape.com network... getxfactor.com jmoodmusic.com smartbusinesschoices.com mintdepot.com lowfaresalways.com evangelicalview.com shoppingpodder.com soproudlywehail.com webnews.ws currenthumor.com

Science and Technology news... Forum Index -> Cryptography Forum
Page 1 of 1