algorithms which not change order of equal elements ? about algorithm-networksort HOT 12 CLOSED

Hmm. It's honestly something that's never occurred to me. I did a search on "stable sort sorting networks", and didn't find much overlap (that is, stability might be found in an article, but not related to a sorting network).

Wikipedia, in its Sorting Algorithm article (https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms), lists both Bubble and Odd-Even sorts as stable, and they are present in a sorting network form in this module. But it's possible to destabilize a stable sort in its implementation, and I haven't tested either one for stability.

I'll keep this open, but frankly the usual way of guaranteeing an order is to extend your comparison function to handle the extra conditions.

from algorithm-networksort.

Whoops, my mistake: Odd-Even is not in the module (Batcher's other two algorithms are however, Merge-Exchange and Bitonic).

from algorithm-networksort.

The only things I have read about stable sorting networks is that they use more comparators, or less optimal networks of the same size. For example, take a sorting network of size 3: [[0, 2], [0, 1], [1, 2]] is unstable; on the other hand [[0, 1], [1, 2], [0, 1]] is stable but trying to sort every bitstring of size 3 shows that it performs more swaps on average.

WikiSort is a stable sorting algorithm that uses sorting networks to sort subsequences whose size is lesser than or equal to 8. However, to maintain the stability, it keeps the indices of the elements and compares them when comparing equal elements. The sorting networks used aren't stable per se.

Anyway, there doesn't seem to be much research about stable sorting networks. Any such network will likely be the result of a suboptimal generic algorithm.

from algorithm-networksort.

I believe that all so-called "transposition networks" such as bubble sort (as John said) are stable. Unfortunately they are far from ideal as the number of elements gets larger.

I suppose this is yet another parameter that finding the "best" network should be able to consider (see #8).

from algorithm-networksort.

thanks a lot to all for tips and answers about stable networks.

indeed it will be nice to get "best" from stable networks list, if this is possible.

from algorithm-networksort.

This may be obvious, but you can always use a non-stable sorting algorithm to do a stable sort by modifying the values to embed the original order as a part of the value (and changing the comparison function to take this into account).

I made a simple gist to demonstrate this:

https://gist.github.com/hoytech/02a86f2e946fca4b0f0e

This is known as the Schwartzian transform and has been used to work around lack-of-stability in certain situations like in PHP scripts that only offer an unstable sort.

A related approach that might be more efficient is to create a parallel array the same size as your input with sequentially increasing numbers as values, and modify the comparison function to check this array if the values in the input are equal, and modify the swap function to also swap the elements of this parallel array.

from algorithm-networksort.

@jgamble - I believe the "odd-even sort" referenced on the wikipedia page you linked is for "odd-even transposition sort", depicted here for n=8:

http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/oetsen.htm

Batcher's "odd-even merge sort" is different, as depicted here for n=8:

https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort

Batcher's O-E mergesort is an advanced algorithm but is not stable.

The O-E transposition sort is a primitive, almost trivial algorithm like bubble sort, but it is stable owing to the fact it's a transposition sort (elements are only compare-exchanged against their immediate neighbours).

Time permitting, I'm going to see if I can whip up some implementations for A::NS so we can play around with them.

from algorithm-networksort.

Odd-even transposition here:

#10

Not a great sort, but probably our best stable one.

I'm going to try to do Batcher's odd-even merge sort soon too...

from algorithm-networksort.

OK I'm going to stop spamming this thread after this I promise. :)

I implemented odd-even merge in this PR: #11

And I just wanted to show that this sort is not stable.

Here's how n=4 looks:

$ algorithm-networksort-chooser --algorithm oddevenmerge --show 4
...
o--^--^--------o
   |  |         
o--v--|--^--^--o
      |  |  |   
o--^--v--|--v--o
   |     |      
o--v-----v-----o

And here's a simple test with two numerically equal inputs:

$ cat snstable.pl 
use strict;
use Algorithm::Networksort qw{:all};
use Data::Dumper;
my @arr = ("2 A","2 B",1,3);
my @network = nw_comparators(scalar @arr, algorithm => "oddevenmerge");
nw_sort(\@network, \@arr);
print Dumper(\@arr);

And the output (note that 2 A and 2 B have been swapped):

$ perl snstable.pl 
$VAR1 = [
          1,
          '2 B',
          '2 A',
          3
        ];

from algorithm-networksort.

Thank you, and sorry for not responding sooner, I've been managing house guests and had little time for myself.

from algorithm-networksort.

No worries :)

from algorithm-networksort.

Closing this now. Version 2.00 is released, and if there is any chance of a stable sorting network, I suspect it will be in an addition to the Best module, not in the algorithms.

from algorithm-networksort.