import java.text.ParseException;
import java.time.Duration;
import java.time.LocalTime;
import java.util.Random;
import java.util.function.BiConsumer;
class Ideone {
private static final int NB_TEST = 10_000;
int[] indexes
= new Random().
ints( NB_TEST,
0,
Integer.
MAX_VALUE ).
toArray();
targets
= new String[indexes.
length];
for ( int i = 0; i < indexes.length; ++i ) {
sources[i] = "sources #" + i;
targets[i] = "targets #" + i;
}
LocalTime start = LocalTime.now();
{
Sorter.sortArrays( indexes, ( i, j ) -> swapCell( sources, i, j ), ( i, j ) -> swapCell( targets, i, j ) );
}
LocalTime end = LocalTime.now();
System.
out.
println( Duration.
between( start, end
) ); }
public static <T> void swapCell( T[] array, int from, int to ) {
T tmp = array[from];
array[from] = array[to];
array[to] = tmp;
}
}
interface Sorter {
void sort
( int[] array, BiConsumer
<Integer, Integer
>...
actions );
static void sortArrays
( int[] array, BiConsumer
<Integer, Integer
>...
actions ) { if ( array.length < 1000 )
new BubbleSorter().sort(array, actions);
else
new SelectionSorter().sort(array, actions);
}
}
class SelectionSorter implements Sorter {
@Override
public void sort
( int[] array, BiConsumer
<Integer, Integer
>...
actions ) { int index;
int value;
int tmp;
for ( int i = 0, length = array.length; i < length; ++i ) {
index = i;
value = array[i];
for ( int j = i + 1; j < length; ++j )
if ( value > array[j] ) {
index = j;
value = array[j];
}
if ( index != i ) {
tmp = array[i];
array[i] = array[index];
array[index] = tmp;
// Swap the other arrays
for ( BiConsumer
<Integer, Integer
> cons
: actions
) cons.accept( i, index );
}
}
}
}
class BubbleSorter implements Sorter {
@Override
public void sort
( int[] array, BiConsumer
<Integer, Integer
>...
actions ) { int tmp;
boolean swapped;
do {
swapped = false;
for ( int i = 1, length = array.length; i < length; ++i )
if ( array[i - 1] > array[i] ) {
tmp = array[i];
array[i] = array[i - 1];
array[i - 1] = tmp;
// Swap the other arrays
for ( BiConsumer
<Integer, Integer
> cons
: actions
) cons.accept( i, i - 1 );
swapped = true;
}
} while ( swapped );
}
}
aW1wb3J0IGphdmEudGV4dC5QYXJzZUV4Y2VwdGlvbjsKaW1wb3J0IGphdmEudGltZS5EdXJhdGlvbjsKaW1wb3J0IGphdmEudGltZS5Mb2NhbFRpbWU7CmltcG9ydCBqYXZhLnV0aWwuUmFuZG9tOwppbXBvcnQgamF2YS51dGlsLmZ1bmN0aW9uLkJpQ29uc3VtZXI7CgpjbGFzcyBJZGVvbmUgewoKICAgIHByaXZhdGUgc3RhdGljIGZpbmFsIGludCBOQl9URVNUID0gMTBfMDAwOwoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKCBTdHJpbmdbXSBhcmdzICkgdGhyb3dzIFBhcnNlRXhjZXB0aW9uIHsKICAgICAgICBpbnRbXSBpbmRleGVzID0gbmV3IFJhbmRvbSgpLmludHMoIE5CX1RFU1QsIDAsIEludGVnZXIuTUFYX1ZBTFVFICkudG9BcnJheSgpOwoKICAgICAgICBTdHJpbmdbXSBzb3VyY2VzID0gbmV3IFN0cmluZ1tpbmRleGVzLmxlbmd0aF0sCiAgICAgICAgICAgICAgICB0YXJnZXRzID0gbmV3IFN0cmluZ1tpbmRleGVzLmxlbmd0aF07CgogICAgICAgIGZvciAoIGludCBpID0gMDsgaSA8IGluZGV4ZXMubGVuZ3RoOyArK2kgKSB7CiAgICAgICAgICAgIHNvdXJjZXNbaV0gPSAic291cmNlcyAjIiArIGk7CiAgICAgICAgICAgIHRhcmdldHNbaV0gPSAidGFyZ2V0cyAjIiArIGk7CiAgICAgICAgfQoKICAgICAgICBMb2NhbFRpbWUgc3RhcnQgPSBMb2NhbFRpbWUubm93KCk7CiAgICAgICAgewogICAgICAgICAgICBTb3J0ZXIuc29ydEFycmF5cyggaW5kZXhlcywgKCBpLCBqICkgLT4gc3dhcENlbGwoIHNvdXJjZXMsIGksIGogKSwgKCBpLCBqICkgLT4gc3dhcENlbGwoIHRhcmdldHMsIGksIGogKSApOwogICAgICAgIH0KICAgICAgICBMb2NhbFRpbWUgZW5kID0gTG9jYWxUaW1lLm5vdygpOwoKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIER1cmF0aW9uLmJldHdlZW4oIHN0YXJ0LCBlbmQgKSApOwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgPFQ+IHZvaWQgc3dhcENlbGwoIFRbXSBhcnJheSwgaW50IGZyb20sIGludCB0byApIHsKICAgICAgICBUIHRtcCA9IGFycmF5W2Zyb21dOwogICAgICAgIGFycmF5W2Zyb21dID0gYXJyYXlbdG9dOwogICAgICAgIGFycmF5W3RvXSA9IHRtcDsKICAgIH0KfQoKaW50ZXJmYWNlIFNvcnRlciB7CiAgICB2b2lkIHNvcnQoIGludFtdIGFycmF5LCBCaUNvbnN1bWVyPEludGVnZXIsIEludGVnZXI+Li4uIGFjdGlvbnMgKTsKCiAgICBzdGF0aWMgdm9pZCBzb3J0QXJyYXlzKCBpbnRbXSBhcnJheSwgQmlDb25zdW1lcjxJbnRlZ2VyLCBJbnRlZ2VyPi4uLiBhY3Rpb25zICkgewogICAgICAgIGlmICggYXJyYXkubGVuZ3RoIDwgMTAwMCApCiAgICAgICAgICAgIG5ldyBCdWJibGVTb3J0ZXIoKS5zb3J0KGFycmF5LCBhY3Rpb25zKTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIG5ldyBTZWxlY3Rpb25Tb3J0ZXIoKS5zb3J0KGFycmF5LCBhY3Rpb25zKTsKICAgIH0KfQoKY2xhc3MgU2VsZWN0aW9uU29ydGVyIGltcGxlbWVudHMgU29ydGVyIHsKICAgIEBPdmVycmlkZQogICAgcHVibGljIHZvaWQgc29ydCggaW50W10gYXJyYXksIEJpQ29uc3VtZXI8SW50ZWdlciwgSW50ZWdlcj4uLi4gYWN0aW9ucyApIHsKICAgICAgICBpbnQgaW5kZXg7CiAgICAgICAgaW50IHZhbHVlOwogICAgICAgIGludCB0bXA7CiAgICAgICAgZm9yICggaW50IGkgPSAwLCBsZW5ndGggPSBhcnJheS5sZW5ndGg7IGkgPCBsZW5ndGg7ICsraSApIHsKICAgICAgICAgICAgaW5kZXggPSBpOwogICAgICAgICAgICB2YWx1ZSA9IGFycmF5W2ldOwogICAgICAgICAgICBmb3IgKCBpbnQgaiA9IGkgKyAxOyBqIDwgbGVuZ3RoOyArK2ogKQogICAgICAgICAgICAgICAgaWYgKCB2YWx1ZSA+IGFycmF5W2pdICkgewogICAgICAgICAgICAgICAgICAgIGluZGV4ID0gajsKICAgICAgICAgICAgICAgICAgICB2YWx1ZSA9IGFycmF5W2pdOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgaWYgKCBpbmRleCAhPSBpICkgewogICAgICAgICAgICAgICAgdG1wID0gYXJyYXlbaV07CiAgICAgICAgICAgICAgICBhcnJheVtpXSA9IGFycmF5W2luZGV4XTsKICAgICAgICAgICAgICAgIGFycmF5W2luZGV4XSA9IHRtcDsKCiAgICAgICAgICAgICAgICAvLyBTd2FwIHRoZSBvdGhlciBhcnJheXMKICAgICAgICAgICAgICAgIGZvciAoIEJpQ29uc3VtZXI8SW50ZWdlciwgSW50ZWdlcj4gY29ucyA6IGFjdGlvbnMgKQogICAgICAgICAgICAgICAgICAgIGNvbnMuYWNjZXB0KCBpLCBpbmRleCApOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CgpjbGFzcyBCdWJibGVTb3J0ZXIgaW1wbGVtZW50cyBTb3J0ZXIgewogICAgQE92ZXJyaWRlCiAgICBwdWJsaWMgdm9pZCBzb3J0KCBpbnRbXSBhcnJheSwgQmlDb25zdW1lcjxJbnRlZ2VyLCBJbnRlZ2VyPi4uLiBhY3Rpb25zICkgewogICAgICAgIGludCB0bXA7CgogICAgICAgIGJvb2xlYW4gc3dhcHBlZDsKICAgICAgICBkbyB7CiAgICAgICAgICAgIHN3YXBwZWQgPSBmYWxzZTsKICAgICAgICAgICAgZm9yICggaW50IGkgPSAxLCBsZW5ndGggPSBhcnJheS5sZW5ndGg7IGkgPCBsZW5ndGg7ICsraSApCiAgICAgICAgICAgICAgICBpZiAoIGFycmF5W2kgLSAxXSA+IGFycmF5W2ldICkgewogICAgICAgICAgICAgICAgICAgIHRtcCA9IGFycmF5W2ldOwogICAgICAgICAgICAgICAgICAgIGFycmF5W2ldID0gYXJyYXlbaSAtIDFdOwogICAgICAgICAgICAgICAgICAgIGFycmF5W2kgLSAxXSA9IHRtcDsKCiAgICAgICAgICAgICAgICAgICAgLy8gU3dhcCB0aGUgb3RoZXIgYXJyYXlzCiAgICAgICAgICAgICAgICAgICAgZm9yICggQmlDb25zdW1lcjxJbnRlZ2VyLCBJbnRlZ2VyPiBjb25zIDogYWN0aW9ucyApCiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnMuYWNjZXB0KCBpLCBpIC0gMSApOwoKICAgICAgICAgICAgICAgICAgICBzd2FwcGVkID0gdHJ1ZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICB9IHdoaWxlICggc3dhcHBlZCApOwogICAgfQp9