serial and parallel bubble sort help me ? :)
friends, I need to find the differences between the serial and parallel version of the bubble sort search algorithm. Is there code in C ++ that works? Could you help ?
a parallel bubble sort is the most polished poo I have heard of to date lol. Lets take the slowest possible algorithm and speed it up with parallel processing...
there may be something else that you mean, but your standard double loop over all the data bubble sort is the serial version. Its what everyone posts here.
to make that parallel, I am not aware of a special algorithm so much as a technique. It works like this:
1) divide the array to be sorted into equally sized chunks. The easy way to do this is with pointers to the starting location, and how many items. so say you had 18 items and 4 cpus to split across. 4*4 is 16 so you need to split it 4,4,5,5.
2) call the serial version of bubble sort on your 4 arrays. beginthread(array, 4, bubblesort) and beginthread(&array[4], 4, bubblesort) and beginthread(&array[8],5,bubblesort) and so on.
3) call simple** merge sort on the results when the 4 threads are all done. you do this in parallel as well: you merge the first 2 result arrays and the second 2 result arrays each in a thread.
4) when those 2 threads finish, mergesort a final time to produce the final result.
total real time taken is going to be significantly faster for large input because your N*N is using a smaller n, and the bigger n was to start, the more it helps. if you had 1000 items, 1000*1000 for N*N is very different from 250*250 (done in parallel, they all take the same wall clock time, but in terms of work performed, its 4*(250*250) which is not the same as 1000*1000) and the subsequent merges are so fast (O(N)) that the net result is a significant improvement. Its roughly 3 times faster for 4 cpu.
**simple merge sort takes the smallest value off the front of each sorted array each time until all elements in both arrays are done. so if you had 1357 and 2468 it would pick 1, then 2, then 3, then 4... and generate 12345678 from the 2 sorted arrays. It does not need anything fancy. There is a more complex merge sort that subdivides the data, but you don't need it because the data is sorted already. You need to be careful with it, though, because at least as I am describing it, everything is in-place. Write the logic accordingly if you don't want to make copies anywhere (recommended to not copy anything).
my apologies if this is not what you needed. Its possible to code the sort itself to be parallel, of course. You can call each inner loop in a thread, if you are very careful about what you are doing, as one way, but its going to be very busy waiting on itself. I have not studied this for bubble sort, but there is probably a slick way to rewrite it to be threaded internally: its the kind of algorithm that is well suited for it.
there may be something else that you mean, but your standard double loop over all the data bubble sort is the serial version. Its what everyone posts here.
to make that parallel, I am not aware of a special algorithm so much as a technique. It works like this:
1) divide the array to be sorted into equally sized chunks. The easy way to do this is with pointers to the starting location, and how many items. so say you had 18 items and 4 cpus to split across. 4*4 is 16 so you need to split it 4,4,5,5.
2) call the serial version of bubble sort on your 4 arrays. beginthread(array, 4, bubblesort) and beginthread(&array[4], 4, bubblesort) and beginthread(&array[8],5,bubblesort) and so on.
3) call simple** merge sort on the results when the 4 threads are all done. you do this in parallel as well: you merge the first 2 result arrays and the second 2 result arrays each in a thread.
4) when those 2 threads finish, mergesort a final time to produce the final result.
total real time taken is going to be significantly faster for large input because your N*N is using a smaller n, and the bigger n was to start, the more it helps. if you had 1000 items, 1000*1000 for N*N is very different from 250*250 (done in parallel, they all take the same wall clock time, but in terms of work performed, its 4*(250*250) which is not the same as 1000*1000) and the subsequent merges are so fast (O(N)) that the net result is a significant improvement. Its roughly 3 times faster for 4 cpu.
**simple merge sort takes the smallest value off the front of each sorted array each time until all elements in both arrays are done. so if you had 1357 and 2468 it would pick 1, then 2, then 3, then 4... and generate 12345678 from the 2 sorted arrays. It does not need anything fancy. There is a more complex merge sort that subdivides the data, but you don't need it because the data is sorted already. You need to be careful with it, though, because at least as I am describing it, everything is in-place. Write the logic accordingly if you don't want to make copies anywhere (recommended to not copy anything).
my apologies if this is not what you needed. Its possible to code the sort itself to be parallel, of course. You can call each inner loop in a thread, if you are very careful about what you are doing, as one way, but its going to be very busy waiting on itself. I have not studied this for bubble sort, but there is probably a slick way to rewrite it to be threaded internally: its the kind of algorithm that is well suited for it.
Last edited on
Topic archived. No new replies allowed.