united1.cpp

openmp sort, parallel bubble sort for example

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib> 
#include <ctime>
#include <omp.h>
#include <time.h>
#include <math.h> 
#ifndef WIN32
#include <sys/time.h>
#endif


using namespace std;

const int n=10000, j = 50;

void create_random_vector(vector<double>& vec, int n) 
{
	vec.clear();
	for(int i=0; i<n; i++) {
		vec.push_back(((rand()%10000)+1));                             
	} 
}


void read(string fileName, vector<double>& vec) {
	double n;
	ifstream file(fileName.c_str());
	while(file >> n)
	{
		vec.push_back(n);
	}                  
}
void write(string fileName, vector<double>& vec) {
	ofstream out(fileName.c_str());
	for(size_t j=0; j<vec.size(); j++)
	{
		out << vec[j] << " ";
	}           
}


void bubble(vector<double>& vec) {
	for(size_t i=0 ; i<vec.size() -1 ; i++) { 
		for(size_t j=0 ; j<vec.size() -i-1 ; j++) {  
			if(vec[j] > vec[j+1]) {           
				swap(vec[j], vec[j+1]);
			}
		}
	}
}

void Parallel_bubble_sort(vector<double>& vec) {
	int size = (int)vec.size();
	int neven = (size + 1)/ 2;
	int nodd = size / 2;
	int k,j;
	for(k = 0 ; k < neven + nodd; k++)
	{ 
		{
			// even
			if( k % 2 == 0)
			{
#pragma omp parallel for private(j)
				for(j = 0 ; j < size - 1 ; j++)
				{   			
					int i =  j * 2;
					if ((i +1 < size ) && ( vec[i] > vec[i+1]) )
					{
						swap(vec[i], vec[i+1]);
					}
				}
			}
			else
			{
#pragma omp parallel for private(j)
				// odd
				for(j = 1 ; j < size - 1; j++)
				{
					int i=j*2-1;
					if((i +1 < size ) &&(vec[i] > vec[i+1]))
					{
						swap(vec[i], vec[i+1]);
					}
				}
			}
		}
	}
}
void InsertionSort(vector<double>& vec) {
	double value;
	int j=0;
	for (size_t i = 1; i < vec.size(); i++) {
		value = vec[i];
		for (j = i-1; (j >= 0) && (vec[j] > value); j--) {
			vec[j+1] = vec[j];
		}
		vec[j+1] = value;
	}
}

void isort(int m,int k, vector<double>& vec) {
    int i,j;
	int N = (int)vec.size();
    for (j=m+k;j<N;j+=k) {
    	for (i=j;i>=k && vec[i]<vec[i-k];i-=k) {
        	swap(vec[i],vec[i-k]);
    	}
    }
}

void new_ShellSort(vector<double>& vec) {
	int N = (int)vec.size();


	int k=N/5;
    for(int m=0;m<k;m++) {
        isort(m,k, vec);
    }
    k=N/7;
    for(int m=0;m<k;m++) {
        isort(m,k, vec);
    }
    for (k=7;k>0;k-=2) {
    	for(int m=0;m<k;m++) {
        	isort(m,k, vec);
    	}
    }
}

void ShellSort_new2(vector<double>& vec) {
 int passes = abs(log((double)vec.size())/log(2.0));
 
	do  {
			int increment = abs(exp(passes*log(2.0)));
			for(int start=0;start<increment;start++) {
				isort(start,increment,vec);
			}
			passes=passes-1;
		}
	while( passes >=0 );
}

void ShellSort_new2_parallel(vector<double>& vec) {
 int passes = abs(log((double)vec.size())/log(2.0));
 int start;
 
	do  {
			int increment = abs(exp(passes*log(2.0)));
			#pragma omp parallel for private(start)

			for(start=0;start<increment;start++) {
				isort(start,increment,vec);
			}
			passes=passes-1;
		}
	while( passes >=0 );
}


void parallel_new_ShellSort(vector<double>& vec) {
	int N = (int)vec.size();
	int k=N/5;
	int m;
#pragma omp parallel for private(m)
    for(m=0;m<k;m++) {
        isort(m,k, vec);
    }
    k=N/7;
#pragma omp parallel for private(m)
    for(int m=0;m<k;m++) {
        isort(m,k, vec);
    }
    k=N/3;
#pragma omp parallel for private(m)
    for(int m=0;m<k;m++) {
        isort(m,k, vec);
    }
	k=N/9;
#pragma omp parallel for private(m)
    for(int m=0;m<k;m++) {
        isort(m,k, vec);
    }
    for (int k=7;k>0;k-=2) {
    	for(m=0;m<k;m++) {
        	isort(m,k, vec);
    	}
    }
}


void ShellSort(vector<double>& vec) {
  int size = (int)vec.size();
  int incr = (int)vec.size();
  while (incr > 0) {
    for (int i = incr ; i < size; i++) {
      int j = i - incr ; 
      while (j >= 0)
        if (vec[j] > vec[j + incr]) { 
          swap(vec[j], vec[j + incr]);
          j = j - incr; 
        }
        else j = -1;
	}
    incr = incr / 2; 
  }
}

void parallel_ShakerSort(vector<double>& vec) {  
	bool swapped;
	int i;
	int size = (int)vec.size();
	if (vec.size() == 0) return;
	do {
		swapped = false;
		for(i=0; i < size-1; i++) {
			{
				if (vec[i] > vec[i+1])   {
					swap(vec[i], vec[i+1]); // let the two elements change places
					swapped= true;
				} 
			}
		}
		if (!swapped) {
			return;
		}
		for(i=size-2; i >= 0; i--) {
			{
				if (vec[i] > vec[i+1])   {
					swap(vec[i], vec[i+1]); // let the two elements change places
					swapped= true;
				}
			}
		}
	}while(swapped); // if no elements have been swapped, then the list is sorted

}


void ShakerSort(vector<double>& vec) {  
	bool swapped;
	if (vec.size() == 0) return;
	do {
		swapped = false;

		for(size_t i=0; i < vec.size()-1; i++) {
			if (vec[i] > vec[i+1])   {
				swap(vec[i], vec[i+1]); // let the two elements change places
				swapped= true;
			} 
		}
		if (!swapped) {
			return;
		}
		for(int i=vec.size()-2; i >= 0; i--) {
			if (vec[i] > vec[i+1])   {
				swap(vec[i], vec[i+1]); // let the two elements change places
				swapped= true;
			} 
		}
	}while(swapped); // if no elements have been swapped, then the list is sorted

}

void Merge(vector<double>& vec, vector<double>& temp, int left, int middle, int right) {  
	for(int i = left ; i <= middle ; i++)
	{
		temp[i - left] = vec[i];             
	}

	int middle2 = middle - left;

	int i = 0;
	int j = middle + 1;
	int k = left;

	while(i <= middle2 || j <= right)
	{
		if(j > right || (i <= middle2 && temp[i] < vec[j]))
		{
			vec[k++] = temp[i++];                  
		}
		else
		{
			vec[k++] = vec[j++];                  
		}
	}

}

void MergeSort(vector<double>& vec, vector<double>& temp, int left, int right) {  
	if(left >= right)
	{
		return;
	}
	int middle = (left + right) / 2;
	MergeSort(vec, temp, left, middle);     
	MergeSort(vec, temp, middle + 1, right);
	Merge(vec, temp, left, middle, right);
}

void MergeSort(vector<double>& vec) {  
	vector<double> temp((vec.size() + 1)/ 2);
	MergeSort(vec, temp, 0, (int)vec.size() - 1);
}
/*
extern "C" int CompareDoubles(double *a, double *b)
{
	if(*a < *b) return -1;
	if(*a > *b) return +1;
	return 0;
}
*/
void BuiltInQSort(vector<double>& vec) {  
	sort(vec.begin(), vec.end());
//qsort((double*)&vec[0], vec.size(), sizeof(vec[0]), (int (*)(const void*, const void*))CompareDoubles);

}

int partition (vector<double>&  m, int a, int b) 
    {
      int i = a;
      for (int j = a; j <= b; j++)    // 镳铖爨蝠桠噱