[Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 4156
  • Last Modified:

Parallel Insertion Sort

Hello Experts,
I need an algorithm on Parallel Insertion Sort.
Please provide some link/help.
thanks.
0
soodsandeep
Asked:
soodsandeep
  • 3
  • 2
  • 2
  • +1
1 Solution
 
tim_vCommented:
this is the algoritm for insertion sort:
http://en.wikipedia.org/wiki/Insertion_sort#Algorithm
0
 
tim_vCommented:
but perhaps you mean bubble sort?
here it is:
http://en.wikipedia.org/wiki/Bubble_sort#Step-by-step_example
0
 
Jose ParrotGraphics ExpertCommented:
Hi,
A parallel insertion sorting algorithm is at
http://www.cs.cmu.edu/~scandal/nesl/alg-sequence.html#insertsort
Jose
0
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
soodsandeepAuthor Commented:
Hello
tim_v, thanks for your reply, BUT, i am not requesting for sequential insertion sort, neither for Bubble sort.

JoseParrot, thanks for the link, BUT, it does not have sufficient information.
neither the algorithm is explained, nor model is specified for which algo is written there.

Please, i need Parallel Insertion sort or Parallem Shell sort for PRAM or HyperCube or Shuffle Exchange.

BTW, is Shell sort same as Insertion Sort ?
Please reply.
0
 
Jose ParrotGraphics ExpertCommented:
Hi,
The trivial solution is to use OpenMP and declare a parallel for in the first loop and let OpenMP do the things. A complete explanation is more complicated due the possible alternatives and contexts.
Let me suggest first to understand well the principles of PRAM. A short presentation (which includes an example on insertion sort)  can be downloaded at
www.nku.edu/~foxr/CSC464/ch14.ppt
For a deeper explanation on parallel programming, the book Introduction to Parallel Algorithms (Wiley Series on Parallel and Distributed Computing) is a very good choice.
About hypercubes, there are other considerations to take attention to, as data moving between processors, which can cancelate the gains of parallelizing if not well programmed.
As per your original question and second derived question seems you are looking for CREW PRAM, in which we should pay attention to the O(n log n) or O(log n) growth of memory space. If so, we should study a liitle bit on the subject before going to the final algorithm. A good start is the paper On Sorting an Intransitive Total Ordered Set Using Semi-Heap at http://www.cse.fau.edu/~jie/teaching/fall_2003_files/p.pdf
Shell and Insertion sorting algorithms are different, not same things.
Below there are both algorithms in c like language with suggestions on to how to parallelize them by using OpenMP which is ease to obtain. Other parallel libraries will have similar sintax.
Jose

    void InsertionSort(array a) // a is the array of numbers to sort
    {
        for(i = ARR_MAX-1; i > 0; i--) <- make this a OpenMP parallel for
        {
            if(a[i]<a[i-1])
            {
                temp = a[i];
                a[i] = a[i-1];
                a[i-1] = temp;
            }
        }
        // force syncronization before net statement
        for(i = 2; i<=ARR_MAX-1; i++) <- parallel for again
        {
            j = i;
            v = a[i];
            while(v < a[j-1])
            {
                a[j] = a[j-1];
                j--;
            }
            a[j] = v;
        }
    }
----------------------------------------------------------------
    ShellSort(array a) // a is the array of numbers to sort
    {
        l = 0;
        r = ARR_MAX-1;
        /* set up increment sequence reccomended by Donald Knuth */
        /* 1 4 13 40 121 364 ... */
        for(z = 1; z <= (r+1)/9; z = 3*z+1);
 
        for(; z>0; z/=3) <---- make this a OpenMP parallel for
        for(int i = l+z; i<=r; i++)
        {
            j = i;
            v = a[i];
            while(j>=l+z && v < a[j-z]) // search the element to insert
            {
                a[j] = a[j-z];
                j-=z;
            }
            a[j] = v; // insert it
        }
    }

Open in new window

0
 
Jose ParrotGraphics ExpertCommented:
Have you tried the code? I did, by using OpenMP with Intel C++ compiler. Parallel execution is more than 4 times faster then serial one.
Jose
0
 
SRINAAGCommented:
can you share your Open MP code here please..?
0
 
SRINAAGCommented:
Here is my program but i am unable to see any speed up... help please...

double insertionsort(int datasize) 
{
	double startTime=0, endTime=0, timee;
  int v,i,j,temp;
  int array[datasize];
 //declaring the array for given datasize

 for(i=0;i<datasize;i++)  
{
	array[i]= rand()%1000;
  //printf(" %d",array[i]);	
}

omp_set_num_threads(24);

	startTime = timerval();

#pragma omp parallel for shared(array) private(i,temp)
for(i = (datasize-1); i > 0; i--) 
        {
           
		   
		    if(array[i]<array[i-1])
            {
                temp = array[i];
                array[i] = array[i-1];
                array[i-1] = temp;
            }
        }


  
#pragma omp critical (array)
		for(i = 2; i<=(datasize-1); i++) 
        {
            j = i;
            v = array[i];
            while(v < array[j-1])
            {
                array[j] = array[j-1];
                j--;
            }
            array[j] = v;
        }
  endTime = timerval();

            timee = (endTime - startTime);
			return timee;


  }

Open in new window

0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

  • 3
  • 2
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now