Win a copy of Practical SVG this week in the HTML/CSS/JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

concurrent bubble sort

 
John Alkinson
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello fellow programmers,
i recently started working on threads and concurrent-parallel programming - which has not been going that well. I ve been trying to create a parallel bubble sort (meaning that in an array [10,5,3,1] the 10 should go after 1 and the 5 go between 1 and 10. Below is the basic bubble sort lagorithm, what confuses is me is the fact that i have monitors and semaphores to use and i cant decide which to use and how to start with em.
Thank you for your time,
John

void bubbleSort(int numbers[], int array_size)
{
int i, j, temp;

for (i = (array_size - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (numbers[j-1] > numbers[j])
{
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
}
}
 
Henry Wong
author
Sheriff
Posts: 22542
109
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am not sure if the bubble sort is a very good algorithm to thread. Generally, algorithm that have some sort of "segmentation" are more easier convert.

However, I guess you can start the next pass of the bubble sort before the previous pass finishes. But it can get really hairy as you have to make sure that no pass passes the previous pass (okay bad grammar ... )

You need to maintain some sort of shared progress variables for the threads -- which need to be protected from each other using monitors. If you do that right, you many not have to protect the array, as they should not be stepping on each other.

In any case, the overhead of this may far outweigh any speed increase for small samples.

Henry
[ November 16, 2005: Message edited by: Henry Wong ]
 
John Alkinson
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm...
what i still havent understood is where to focus my attention... use semaphores/monitors etc?

This is in the main class:

public static void pbsort(int [] sa, int [] ua, int [] hp) {}

where sa=array of unsorted integers, ua=array of sorted integers, hp=number of hops it does to sort it.

Thank you for your time,
John
 
Henry Wong
author
Sheriff
Posts: 22542
109
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by John Alkinson:
Hmm...
what i still havent understood is where to focus my attention... use semaphores/monitors etc?

This is in the main class:

public static void pbsort(int [] sa, int [] ua, int [] hp) {}

where sa=array of unsorted integers, ua=array of sorted integers, hp=number of hops it does to sort it.

Thank you for your time,
John


For something like this, you have to focus on the design first. This is not just a port. IMHO, it is almost a complete rewrite.

Workout a way to have each thread do one iteration of the loop. Make sure that the thread have a way to check that it's index is not stepping on the previous iterations index. This means you need a way to expose your index for the next iteration too.

You don't need worry about semaphores / monitors until you figure out what common data you need to protect first. And you don't need to figure out the common data until you figure out the algorithm first.

Henry
 
John Alkinson
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ive been trying to figure out the algorithm so that i can continue on with the common data etc... but im not sure if its going that well
ive the unsorted array, the sorted array, the hops, the array lengths, i need to have a part where the 1st swap would take place in the sequential bubble sort and a part where the parallel swap would take place according to the 1st (cant explain this well so ill give an example: the array contains [4,3,2,1] so 4 is checked (1st in array) to be the highest so it goes in the end, so since 4 is the highest, at the same time 3 is checked in relation to the highest and since it is directly after, 3 is moved before 4... im not sure how the parallel function is triggered for the bubble sort. Could u correct me if im wrong which im 100% sure of, and add any ideas if any?

John
 
John Alkinson
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i figured out how and when the swaps are:
1,4,6,10,3 compare 1,4 no swap
1,4,6,10,3 compare 4,6 no swap
1,4,6,10,3 compare 6,10 no swap ----- AND compare 1,3 AND no swap
1,4,6,10,3 compare 10,3 swap 10,3>3,10 ----- AND compare 4,6 AND no swap
1,4,6,3,10 compare 6,3 swap 6,3>3,6 ----- AND compare 1,4 AND no swap
1,4,3,6,10 compare 4,3 swap 4,3>3,4
1,3,4,6,10 compare 1,3 no swap

but i cant figure out how the array location is given to the first swap and then the second-parallel swap as they are given at the third line at the swaps....:/
 
Henry Wong
author
Sheriff
Posts: 22542
109
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by John Alkinson:
i figured out how and when the swaps are:
1,4,6,10,3 compare 1,4 no swap
1,4,6,10,3 compare 4,6 no swap
1,4,6,10,3 compare 6,10 no swap ----- AND compare 1,3 AND no swap
1,4,6,10,3 compare 10,3 swap 10,3>3,10 ----- AND compare 4,6 AND no swap
1,4,6,3,10 compare 6,3 swap 6,3>3,6 ----- AND compare 1,4 AND no swap
1,4,3,6,10 compare 4,3 swap 4,3>3,4
1,3,4,6,10 compare 1,3 no swap

but i cant figure out how the array location is given to the first swap and then the second-parallel swap as they are given at the third line at the swaps....:/


Yea, it is going to be a pain... a few caveats first... Sorting is a CPU intensive operation. You will *NOT* gain any speed by going multithread on a single processor machine -- in fact, the overhead will slow it down. Furthermore, this seems very complex, so it might only be useful for large data sets.

Anyway... Obvious you need some way to expose your current working index to the other threads. And of course, you need to get the current working index of the thread processing the previous iteration. Can you think of a place to store it? A "common" place to store it?

Henry
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!