Learn how to use and navigate the new features included in Bootstrap 4, the most popular HTML, CSS, and JavaScript framework for developing responsive, mobile-first websites.

Hello Experts,

I need an algorithm on Parallel Insertion Sort.

Please provide some link/help.

thanks.

I need an algorithm on Parallel Insertion Sort.

Please provide some link/help.

thanks.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

here it is:

http://en.wikipedia.org/wiki/Bubble_sort#Step-by-step_example

A parallel insertion sorting algorithm is at

http://www.cs.cmu.edu/~sca

Jose

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.

The trivial solution is to use OpenMP and declare a

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/c

For a deeper explanation on parallel programming, the book

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

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
}
}
```

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialJose

```
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;
}
```

Algorithms

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

http://en.wikipedia.org/wiki/Insertion_sort#Algorithm