Bubble sort

Term Project

Choose a problem from the topics below or other topics and design two different algorithms for this problem. For each algorithm, write a parallel program. Students will be asked to present their problem description, algorithm(s) employed, program description, and performance plots to the class using 5-10 minutes.

Submit the following: A 3-5 page single-spaced project report (hard copy) containing the following sections:

1.      Problem:

Bubble Sort

2.      chosen algorithms

BUBBLE SORT

·         procedure bubbleSort( A : list of sortable items )

n = length(A)

for i = 1 to  n-1 inclusive do

for j=1to n-2 inclusive do

if A[j] > A[j+1] then

swap( A[i-1], A[i] )

end if

end for

end for

end procedure

#include<stdio.h>
#include<conio.h>
void main()
{
long int i,j,tmp,a[10];
for(i=0;i<n;i++)
printf("enter nos.\n");

for(i=0;i<10;i++)
scanf("%ld",&a[i]);

for(i=0;i<10;i++)
{
for(j=0;j<9;j++)
if(a[j]>a[j+1])
{
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
printf("sorted array is -->\n");
for( i=0;i<10;i++)
printf("%ld\n",a[i]);
getch();
}

·         procedure bubbleSort( A : list of sortable items )

n = length(A)

repeat

swapped = false

for i = 1 to n-1 inclusive do

if A[i-1] > A[i] then

swap(A[i-1], A[i])

swapped = true

end if

end for

n = n - 1

until not swapped

end procedure

#include<stdio.h>
#include<conio.h>
void main()
{
long int i,j,tmp,a[10],f=0;
for(i=0;i<n;i++)
printf("enter nos.\n");

for(i=0;i<10;i++)
scanf("%ld",&a[i]);

do
{

f=0;
for(j=0;j<9;j++)
if(a[j]>a[j+1])
{

f=1;
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}while(f==0);

printf("sorted array is -->\n");
for( i=0;i<10;i++)
printf("%ld\n",a[i]);
getch();
}

3.      associated data structures,

array is used of size n

long int variables are used

4.      underlying communication pattern

5.      parallel time complexity for each implementation

6. performance of each program with reference to the plots for (a) execution time and for (b) speedup as number of processes varies, and

7. your conclusions containing your interpretation of the performance of these programs, their limitations, and possible future improvements.