Problem with Java multithreaded bubble sort algorithm

[Bernard]

Hi

I decided to create a new thread solely for the purpose of getting an answer from someone experienced in Java multithreading and/or multithreaded sorting algorithm optimization.

Some time ago I wrote simple multithreaded version of bubble sort algorithm in order to  measure speed of execution as a function of data set size and number of  spawned worker threads.

The results obtained from averaging hundreds of program runs were  partially expected.The best result was achieved with the 4 spawned threads thus matching number of cores available.

Two test were performed so far.First of them sorted an array of 1000 values filled by my own implementation of Airy function second test sorted an array filled with Airy function 1e4 values.

Speed of execution measurement was performed by java.System.nanoTime() method which is binary translated to machine code RDTSC instruction.I have to mention that Airy function values were multiplied by java random.float() method to insert peudo-random noise into monotonic increasing data.Access to the main sorting loop was controlled by synchronized statement , multiple threads were waiting for each other completion.Timing method.

When  I looked at sorting results the numbers were not sorted at monotonically increased order over the whole domain(array length).For this I can blame the lack of global synchronization lock in the form of synchronized{} statement.With the synchronized{} statement only one thread was accessing an array and other threads were waiting on global lock.I can post source code if it is needed.

Here are the results:

1a.Bubble sort 1000 elements three threads(main and 2 spawned threads) with synchronized{} statement : ~13.235 miliseconds.
1b.Bubble sort 1000 elements three threads(main and 2 spawned threads)without synchronized{} statement:~12.678 miliseconds.
2a.Bubble sort 1000 elements five threads(main and 4 spawned threads)without synchronized{} statement:~7.603 miliseconds.
2b.Bubble sort 1000 elements five threads(main and 4 spawned threads)with synchronized{} statement: ~10.551 miliseconds.
3a.Bubble sort 1000 elements nine threads(main and 8 spawned threads)with synchronized{}statement: ~10.233 miliseconds.
3b.Bubble sort 1000 elements nine threads(main and 8 spawned threads)without synchronized{}statement:~9.664 miliseconds.
4a.Bubble sort 1e4 elements five threads(main and 4 spawned threads)without synchronized{}statement: ~71.133 miliseconds.
4b.Bubble sort 1e4 elements five threads(main and 4 spawned threads)with synchronized{}statement:~173.134 miliseconds.

Thanks in advance!

[Bernard]

Can someone help me?

[SergeyKostrov]

>>...When I looked at sorting results the numbers were not sorted at monotonically increased order over >>the whole domain(array length)... Could you posts some results? For example, if your input array has 64 numbers ( integers ) in a descending order how the output looks like? Input: 64, 63, 62, 61, 60, ..., 4, 3, 2, 1 Output: ???

[Bernard]

Hi Sergey!

Thanks for reply.I will post the results later today.

[Bernard]

Hi Sergey!

Thanks for offering your help, but I decided to use Java only for GUI programming.

[SergeyKostrov]

>>>>>>Could you posts some results? >>>> >>>>Thanks for reply.I will post the results later today. >> >>...Thanks for offering your help, but I decided to use Java only for GUI programming. I consider that the problem with un-ordered array is solved.