文档章节

《多核程序设计》学习笔记:冒泡排序的并行实现

Ritajiao
 Ritajiao
发布于 2017/07/28 00:06
字数 733
阅读 55
收藏 0

我们都知道冒泡排序的串行算法的实现,非常简单,两个for循环即可实现,那么并行算法又如何实现呢?

先介绍一下算法思想。

(1)串行算法思想:从左至右依次比较相邻的两个数据,如果左边的数比右边的数大,则交换,这样经过一轮变换后,最大的数据就会移到最右边;然后第二轮只需比较剩余的n-1个数即可,找到次最大的数据;依次类推,直到将这n个数据排好序。

下面是串行冒泡排序算法的核心代码:

for(i=0;i<n-1;i++)	//n-1轮
	{
		for(j=0;j<n-i-1;j++)
		{
			if(array[j]>array[j+1])
			{
				tmp=array[j];
				array[j]=array[j+1];
				array[j+1]=tmp;
			}
		}
	}

(2)并行算法思想:并行算法可以使用奇偶排序是冒泡排序的并行化版本,其思想就是将冒泡排序的每轮操作分解成奇数位和偶数位上的比较、交换,且互不干扰,所以可以并行化。

//#include"stdafx.h"
#include<stdio.h>
#include<malloc.h>
#include<windows.h>
int* array;
bool flag=false;
void Exchange(int* j)		//比较并交换相邻元素
{
	int b;
	int k=*((int* )j);
	if(array[k]>array[k+1])
	{
		b=array[k];
		array[k]=array[k+1];
		array[k+1]=b;
		flag=true;
	}
}
void Parallel_BubbleSort(int length)       //并行冒泡排序主体
{
	int i,j;
	int *tag=(int* )malloc(sizeof(int)*length);
	for(i=0;i<length;i++)
		tag[i]=i;
	HANDLE* h=(HANDLE* )malloc(sizeof(HANDLE)*(length/2));
	for(i=0;i<length;i++)
	{
		if(i%2==0)		//比较偶数位
		{
			
			for(j=0;j<length-1;j+=2)	//每循环一次,就创建一个交换线程
			{
                //创建线程函数
				h[j/2]=CreateThread(NULL,		
								0,
								(LPTHREAD_START_ROUTINE)Exchange,
								&tag[j],		//不能直接传j,j值会改变
								0,
								NULL);			
				printf("创建偶数线程\n");
			}
			WaitForMultipleObjects((length-1)/2,h,TRUE,INFINITE);
		}
		else	//比较奇数位
		{
			for(j=1;j<length-1;j+=2)
			{
				h[(j-1)/2]=CreateThread(NULL,
									0,
									(LPTHREAD_START_ROUTINE)Exchange,
									&tag[j],
									0,
									NULL);
				printf("创建奇数线程\n");
			}
			WaitForMultipleObjects(length/2,h,TRUE,INFINITE);
			if(!flag)		//当一次偶一次奇之后,才能跳出
				break;
			flag=false;
		}
	}
}
void main()
{
	int i,length;
	printf("请输入数组长度:");
	scanf("%d",&length);
	if(length<0)
		printf("输入错误!");
	else
	{
		array=(int* )malloc(sizeof(int)*length);		//创建动态数组
		printf("请输入数组的值:");
		for(i=0;i<length;i++)
		{
			scanf("%d",&array[i]);
		}
		Parallel_BubbleSort(length);
		for(i=0;i<length;i++)
			printf("%d ",array[i]);
		printf("\n");
	}
}

上述代码,为了提高算法效率,增加了一个标志位flag,当最后数组数据已经排好序,就跳出循环,而非循环最大的次数。

 

在两个算法前后加上clock()计时函数,比较运行时间发现:并行的奇偶排序算法所花费的时间比串行算法还要多,因为它创建线程非常频繁,所消耗的时间相对来说比较大。

© 著作权归作者所有

Ritajiao
粉丝 0
博文 10
码字总数 6835
作品 0
保定
私信 提问
Golang学习笔记目录

Golang 介绍 Go语言是谷歌2009发布的第二款开源编程语言。 Go语言专门针对多处理器系统应用程序的编程进行了优化,使用Go编译的程序可以媲美C或C++代码的速度,而且更加安全、支持并行进程。...

ChainZhang
2017/12/26
0
0
Python算法札记1_冒泡排序

冒泡排序:,从序列的一端开始往另一端冒泡,。重复性的工作直到没有可以交换的两个元素,说明数列已经排序完成。冒泡算法的时间复杂度为O(n2)。 算法思想 比较相邻的元素。如果第一个比第二...

皮皮大
06/23
0
0
算法之排序(Java版)-持续更新补充

开始复习排序,主要是按照《轻松学算法》这本书的目录来学习,同时搜索网上的博客文章来辅助,参考的来源均在文章底部标明。同样,本文持续更新,代码书上只给了基础排序代码(我称之为原始排...

kissjz
2018/08/03
0
0
一起学Python:多任务的概念

多任务的概念 什么叫“多任务”呢?简单地说,就是操作系统可以同时运行多个任务。打个比方,你一边在用浏览器上网,一边在听MP3,一边在用Word赶作业,这就是多任务,至少同时有3个任务正在...

祈澈姑娘
2017/11/25
0
0
算法学习笔记(3)---冒泡排序

冒泡排序是针对少量待排数据的一种有效的排序算法,其思想是非常容易理解的:假设待排的数组长度为N 比较前后相邻的两个数,如果前面数据大于后面数据,则进行交换 将数据进行N-1次比较后,最...

亭芳
2014/03/11
45
0

没有更多内容

加载失败,请刷新页面

加载更多

Dubbo-自适应拓展机制

背景 在 Dubbo 中,很多拓展都是通过 SPI 机制进行加载的,比如 Protocol、Cluster、LoadBalance 等,这些都是Dubbo的基础组件。这些基础组件的拓展不是在系统框架启动阶段被加载,而是拓展方...

rock-man
35分钟前
6
0
Kali安装fcitx输入法(五笔)

安装fcitx > sudo apt-get install fcitx-rime fcitx-config-gtk3 重启 > sudo reboot fcitx配置 效果就是这样 配置输入法切换 系统设置...

yeahlife
37分钟前
4
0
IE之css3效果兼容

本文转载于:专业的前端网站▷IE之css3效果兼容 一、兼容css阴影效果(ie滤镜) 1.Shadow,阴影 .shadow { -moz-box-shadow: 3px 3px 4px #000; -webkit-box-shadow: 3px 3px 4px #000; box-sha...

前端老手
40分钟前
4
0
NiushopB2C开源商城功能列表说明:

B2C单商户免费版:PC商城+微商城 B2C单商户标准版:PC商城+微商城组合套餐+阶梯优惠核销功能 B2C单商户企业版:PC商城+微商城拼团+组合套餐阶梯优惠+核销功能 B2C单商户分销版:PC商城+微商城...

niushop-芳
42分钟前
4
0
图片如何转GIF图片呢

如何将生活中拍摄的好玩有趣的图片制作成GIF动图呢?相信很多小伙伴都不知道要如何制作,其实制作方法非常的简单,下面分享一个图片转GIF动图的方法,希望这个方法能够帮助大家在与好友斗图时...

白米稀饭2019
49分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部