You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
110 lines
2.6 KiB
110 lines
2.6 KiB
/*
|
|
bitonic.c
|
|
|
|
This file contains two different implementations of the bitonic sort
|
|
recursive version : recBitonicSort()
|
|
imperative version : impBitonicSort()
|
|
|
|
|
|
The bitonic sort is also known as Batcher Sort.
|
|
For a reference of the algorithm, see the article titled
|
|
Sorting networks and their applications by K. E. Batcher in 1968
|
|
|
|
|
|
The following codes take references to the codes avaiable at
|
|
|
|
http://www.cag.lcs.mit.edu/streamit/results/bitonic/code/c/bitonic.c
|
|
|
|
http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
|
|
|
|
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
|
|
*/
|
|
|
|
/*
|
|
------- ----------------------
|
|
Nikos Pitsianis, Duke CS
|
|
-----------------------------
|
|
*/
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <sys/time.h>
|
|
#include <time.h>
|
|
|
|
typedef enum { false, true } bool;
|
|
struct timeval startwtime, endwtime;
|
|
double seq_time;
|
|
|
|
int threads; //number of threads
|
|
int N; // data array size
|
|
int *a; // data array to be sorted
|
|
unsigned randSeed; //seed array initialisation
|
|
|
|
const int ASCENDING = 1;
|
|
const int DESCENDING = 0;
|
|
|
|
void getArgs(int argc, char** argv);
|
|
void init(void);
|
|
void print(void);
|
|
int qSortAscending (const void * a, const void * b);
|
|
int qSortDescending (const void * a, const void * b);
|
|
|
|
/** the main program **/
|
|
int main(int argc, char **argv) {
|
|
getArgs(argc, argv);
|
|
a = (int *) malloc(N * sizeof(int));
|
|
randSeed = (unsigned) time(NULL);
|
|
|
|
//Sorts using the qSort algorithm
|
|
init();
|
|
|
|
gettimeofday (&startwtime, NULL);
|
|
qsort(a, N, sizeof(int), qSortAscending);
|
|
gettimeofday (&endwtime, NULL);
|
|
|
|
seq_time = (double)((endwtime.tv_usec - startwtime.tv_usec)/1.0e6
|
|
+ endwtime.tv_sec - startwtime.tv_sec);
|
|
|
|
printf("%f\n", seq_time);
|
|
|
|
free(a);
|
|
}
|
|
|
|
/** -------------- SUB-PROCEDURES ----------------- **/
|
|
|
|
void getArgs(int argc, char** argv){
|
|
if (argc != 2) {
|
|
printf("Usage: %s p q\nwhere:\n\tP=2^p is the the number of threads(power of two)\n\tN=2^q is problem size (power of two)\n",
|
|
argv[0]);
|
|
exit(1);
|
|
}
|
|
N = 1<<atoi(argv[1]);
|
|
}
|
|
|
|
/** procedure init() : initialize array "a" with data **/
|
|
void init() {
|
|
srand(randSeed);
|
|
int i;
|
|
for (i = 0; i < N; i++) {
|
|
a[i] = rand() % N; // (N - i);
|
|
}
|
|
}
|
|
|
|
/** procedure print() : print array elements **/
|
|
void print() {
|
|
int i;
|
|
for (i = 0; i < N; i++) {
|
|
printf("%d\n", a[i]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
|
|
/** function used by qsort for comparing **/
|
|
int qSortAscending (const void * a, const void * b) {
|
|
return ( *(int*)a - *(int*)b );
|
|
}
|
|
|
|
/** function used by qsort for comparing **/
|
|
int qSortDescending (const void * a, const void * b) {
|
|
return ( *(int*)b - *(int*)a );
|
|
}
|