Batchers Bitonic sort

The example i am showing will only works for 2^n numbers.

First,we need to break up the given sequence into smaller parts,we call them individual sorting parts( initially two numbers in a part, for every step it will doubles). Now sort first part in increasing and the second in decreasing order and continue like this to the end.

Second, after sorting, if the sorted part having more than two number, then you need to sort numbers with-in, and ascending or descending order depends on which part it is.

example for 8 numbers:

example for 4 numbers:

Basic pthread programming

Here i demonstated a thread based programme. It counts number of 3's in an array of size 100000. we fill the array with random values. We need to give the number of thread, so that each thread shares part of the array and starts computation.

In this program i used some of the basic pthread commands.

int pthread_create( pthread_t *thread,const pthread_attr_t *attr, void* (*start_routine)(void*),void *arg);

This command creates a thread on a start_routine, arg is an argutment to the start_routine.Mostly we do not use attr, instead we put null.

int pthread_join(pthread_t thread, void **status);

This command is usefull when we are waiting for return value. Here return value is status.

int pthread_mutex_lock(pthread_mutex_t *mutex);

int pthread_mutex_unlock(pthread_mutex_t *mutex);

Above two commands are used for locking and unlocking

#include stdio.h,stdlib.h,pthread.h,sys/time.h

#define N 100000

int a[N],nt;

int part,tid;

pthread_mutex_t arg,args[N];

void * function(void *i)

{

int j,k,l,ltid,count,*ret;

pthread_t thread;

j=(int)i;

ltid=tid;

pthread_mutex_unlock(&arg);

k=j+part;

if(ltid==(nt-1))

k=N;

count=0;

for(l=j;l is less than k;l++)

{

if(a[l]==3)

{

count++;

}

}

printf("thread %d %d\n",ltid,count);

ret=count;

return((void *)ret);

}

main(int argc,char *argv[])

{

int i,rc,t;

int count=0,total=0;

pthread_t threads[N];

void *status;

srand (time(NULL));

struct timeval tim;

nt=atoi(argv[1]);

// filling array with random number between 0 to 9

for(i=0;i is less than N;i++)

{

a[i]=rand()%10;

}

part=N/nt;

t=0;

gettimeofday(&tim, NULL);

double t1=tim.tv_sec+(tim.tv_usec/1000000.0);

// creating threads

for(i=0;i is less than nt;i++)

{

pthread_mutex_lock(&arg);

rc=pthread_create(&threads[i],NULL,function,(void *)t);

if(rc)

{

printf("error while creating thread\n");

exit(1);

}

t+=part;

tid=i;

}

// Waiting for all threads

for(i=0;i is less than nt;i++)

{

status=0;

rc=pthread_join(threads[i],(void **)&status);

if(rc)

{

printf("error while joining thread\n");

exit(1);

}

total+=status;

}

gettimeofday(&tim, NULL);

double t2=tim.tv_sec+(tim.tv_usec/1000000.0);

printf("3 repeated %d times in %4.3lf using threads\n",total,t2-t1);

}

Sardine run