并行排序

并行排序算法是计算机并行计算能力大大发展之后,为了提高排序效率而提出的算法。

划分的设计方法

串行算法直接并行化

  • 模拟快速排序
    • 二叉树上模拟快速排序
      • 串行算法简介:快速排序是一种较为高效的排序算法,它通过不断的划分待排序列为两段,使得前一段总小于或等于某个数,而后一段总大于某个数,这样每次划分就能确定一个数的最终位置。一般情况下,如果每次划分的两个子列大致等长,那么它的时间复杂度是
      • PRAM-CRCW计算模型上利用二叉树网络模拟快速排序
        • 由快速排序的过程,我们可以看到,快速排序实际上就是在构造一棵二叉树,让划分主元位于根节点,使得左子节点小于或等于根而右子节点大于根,最后对整棵二叉树进行一次中序遍历,便可以得到最后排好序的数列。
        • 我们可以选n个处理器分别保存待排序数组A的n个元素,处理器对应一个变量用于存放主元元素的处理器号,以及两个变量L,R分别存放其左右儿子。开始时,每一个处理器都试图往变量root中写入它的处理器号,若果我们使用PRAM-CRCW计算模型,那么就只有一个能够写入root,接着root被复制给每一个处理器的。然后对于每个处理器(除去被原为主元的那个外)判断其值与的大小,从而确定放入还是,同样的,由于并发操作的互斥性,只有一个只能被最终写入,他们就作为下次划分的主元。算法继续进行直到n个主元被选完为止。
      • 时间复杂度分析:由于一层节点的构造时间是,所以算法的时间复杂度是
    • 超立方体上模拟快速排序
      • 超立方体网络是基于超立方体连接构建的网络。网络中以格雷码对各顶点编号。在下面的描述中,设顶点数,待排序元素共有n个。
      • 超立方体上的快速排序是这样进行的:首先我们将n个元素分配到p个处理器上,为了使问题讨论简单化,假设n是p的整数倍,那么每个顶点将会分到个元素。然后随机选一个主元,各个处理器将每个顶点中的元素按与主元的比较结果分为两部份。这个算法的关键点在这里,对每一个处理器(顶点)在进行第i次划分时,将大于主元的部分都送到超立方体的一个d-i维自立方体中,而将小于主元的部分送到另一个d-i位的子立方体中,这样就模拟了快速排序中的划分算法。子立方体可以这样选择:在第i次划分中判断第i位是0还是1。划分算法到处理完所有1维子立方体后结束。接下来对每个顶点中的元素调用串行算法进行局部排序,最后对整个立方体进行一次遍历便可得到排好序的元素。

比较器络上的并行排序网

比较器网络英语sorting network一般是指由Batcher比较器构成的网络。这些比较器均可以执行两个数之间的比较与条件交换(CCI)操作。Batcher归并网络可以由较小的Batcher归并网络递归地组成。Batcher排序网络可以分为奇偶排序网络(Odd-Even Sorting Network)双调排序网络英语Bitonic Sorting Net两大类。

参阅

Read other articles:

Roman statesman's five marriages Julia, in a 16th century artist's fanciful illustration. Julia, Pompey's fourth wife, was Julius Caesar's only legitimate child The first-century-BCE Roman statesman and commander Pompey the Great was married five times. These marriages were not only romantic matches, but political arrangements, often dictated by Pompey's political career and need to form alliances with other powerful Roman men. Pompey's first marriage, in 86 BCE, was to Antistia, the dau...

 

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Mei 2016. Di televisi, format program menggambarkan isi keseluruhan dan merk dari hak cipta program televisi. Stasiun lisensi memproduksi dan menyiarkan versi nasional dari program asing. Format menjadi bagian utama dari pasar televisi internasional. Format pembelia...

 

Zona fasciculataLayers of adrenaline gland.DetailsIdentifiersLatinZona fasciculataMeSHD015383FMA69234Anatomical terminology[edit on Wikidata] The zona fasciculata (sometimes, fascicular or fasciculate zone) constitutes the middle and also the widest zone of the adrenal cortex, sitting directly beneath the zona glomerulosa. Constituent cells are organized into bundles or fascicles. The zona fasciculata chiefly produces glucocorticoids (mainly cortisol in humans), which regulate the metabol...

JapanFIBA ranking10FIBA zoneFIBA AsiaCoachTorsten LoiblOlympic GamesAppearances1World CupAppearances5Asia CupAppearances3Medals (2019) Home Away The Japan women's national 3x3 team is a national 3x3 basketball team of Japan,[1] administered by the Japan Basketball Association.[2] It represents the country in international 3x3 (3 against 3) women's basketball competitions. As of late 2019, the head coach was Torsten Loibl.[3] Tournament record Olympic Games Year Positio...

 

1951 Japanese drama film The IdiotTheatrical release poster showing Toshiro Mifune (left), Masayuki Mori (centre) and Setsuko Hara (right)Japanese nameKanji白痴TranscriptionsRevised HepburnHakuchi Directed byAkira KurosawaScreenplay byAkira KurosawaEijirō HisaitaBased onThe Idiotby Fyodor DostoevskyProduced byTakashi KoideStarringSetsuko HaraYoshiko KugaToshiro MifuneMasayuki MoriTakashi ShimuraNoriko SengokuCinematographyToshio UbukataEdited byAkira KurosawaMusic byFumio HayasakaProductio...

 

Battaglia di Tapso (Thapsus)parte della Guerra civile tra Cesare e Pompeo(Bellum Africum)Disposizione iniziale delle truppe sul campo di battaglia.Data6 aprile 46 a.C. LuogoTapso, oggi Ras Dimas (Tunisia) EsitoVittoria di Giulio Cesare SchieramentiCesarianiPompeiani ComandantiGiulio Cesare,Giuba I, Quinto Cecilio Metello Pio Scipione Nasica, Marco Petreio, Marco Porcio Catone Uticense EffettiviUn numero imprecisato (almeno 10 legioni)Un numero imprecisato di fanti, 2.500 cavalieri Numidi e ci...

Ювеналии (лат. Juvenalia) — сценические игры, учреждённые римским императором Нероном в 60 году по случаю достижения им зрелого возраста. Это были своего рода любительские спектакли, устраивавшиеся не в общественном цирке, а в частных домах или садах и происходившие пере...

 

Kejuaraan Dunia Futsal FIFA 1989(Belanda) FIFA Wereldkampioenschap Futsal 1989Informasi turnamenTuan rumah BelandaJadwalpenyelenggaraan5–15 Januari 1989Jumlahtim peserta16 (dari 6 konfederasi)Tempatpenyelenggaraan5 (di 5 kota)Hasil turnamenJuara Brasil (gelar ke-1)Tempat kedua BelandaTempat ketiga Amerika SerikatTempat keempat BelgiaStatistik turnamenJumlahpertandingan40Jumlah gol221 (5,53 per pertandingan)Jumlahpenonton86.500 (2.163 per pertandi...

 

Romanian Balkan brass band This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Fanfare Ciocărlia – news · newspapers · books · scholar · JSTOR (April 2018) (Learn how and when to remove this message) Fanfare CiocărliaFanfare Ciocărlia in 2017Background informationOriginZece Prăjini, Iași County, RomaniaGenr...

Boat builder company in America Huckins Yacht Corporation is one of the oldest boat builders in the United States. The company is located on the Ortega River in Jacksonville, Florida, and is run by its third-generation owners, Cindy and Buddy Purcell. Huckins manufactures custom yachts ranging from 40 to 90 feet that combine classic design and traditional workmanship with modern technology and amenities. It has built a total of 457 yachts during its 80 years of operation, crafting vessels one...

 

Orde JasaRepublik Federal JermanKelas Salib Agung Istimewa(diberikan kepada para kepala negara)Dianugerahkan oleh Presiden JermanTipeBintang jasa dengan delapan kelas umum dan satu kelas istimewaDibentuk7 September 1951Negara JermanStatusSaat ini dianugerahkanStatistikJumlah penerima260.429 (per 10 Januari 2021)[1]Salib Agung Kelas IstimewaSalib Agung Kelas I, Anugerah KhususSalib Agung Kelas ISalib AgungKesatria KomandanKomandanPrajuritAnggotaMedaliPita tanda kehormatan Orde Jas...

 

尊敬的拿督斯里莫哈末·沙布Mohamad bin Sabu国会议员2018年9月24日末沙布在五角大楼与美国国防部长詹姆斯·马蒂斯会面农业及食品工业部部长现任就任日期2022年12月3日君主最高元首苏丹阿都拉最高元首苏丹依布拉欣·依斯迈首相安华·依布拉欣副职陈泓缣(2022年至2023年)亚瑟古律(2023年至今)前任羅納建迪国防部长任期2018年5月21日—2020年2月24日君主最高元首端姑莫哈末五世...

هنودمعلومات عامةنسبة التسمية الهند التعداد الكليالتعداد قرابة 1.21 مليار[1][2]تعداد الهند عام 2011ق. 1.32 مليار[3]تقديرات عام 2017ق. 30.8 مليون[4]مناطق الوجود المميزةبلد الأصل الهند البلد الهند  الهند نيبال 4,000,000[5] الولايات المتحدة 3,982,398[6] الإمار...

 

1979 single by the MisfitsNight of the Living DeadSingle by the MisfitsB-sideWhere Eagles DareRat FinkReleasedOctober 31, 1979RecordedJune 1979GenreHorror punkLength5:43LabelPlan 9 (PL 1011)Songwriter(s)Glenn DanzigProducer(s)Danny Zelonky, The MisfitsMisfits singles chronology Horror Business (1979) Night of the Living Dead (1979) Halloween (1981) Night of the Living Dead is the fourth single by the horror punk band the Misfits. It was released on October 31, 1979, on singer Glenn Danzig...

 

2002 United Kingdom local elections ← 2001 2 May 2002 2003 → All 32 London boroughs, all 36 metropolitan boroughs,18 unitary authorities, 88 English districtsand 7 directly elected mayors   Majority party Minority party Third party   Leader Tony Blair Iain Duncan Smith Charles Kennedy Party Labour Conservative Liberal Democrats Leader since 21 July 1994 13 September 2001 9 August 1999 Percentage 33%[a] 34% 27% Swing 2% 6% 2% Councils 64 ...

Politics of the Faroe Islands Constitution Constitution Act of Succession Freedom of Speech and the Press Taxation The Crown Monarch King Frederik X Privy Council Purveyors to the Royal Court The unity of the Realm  Kingdom of Denmark  Faroe Islands  Denmark  Greenland ExecutiveRegeringen The Government of Denmark High Commissioner (list) Lene Moyell Johansen Landsstýri The Government of the Faroe Islands Premier Aksel V. Johannesen Deputy Premier Høgni Hoydal Johannesen...

 

这是满族传统命名,只称名而不与姓氏连用,其姓氏为爱新觉罗。 本页面有满文字母,操作系统及浏览器須支持特殊字母与符号才能正確显示为滿文字母,否则可能變成未成連寫體的字母或其他符號。 注意:本页有Unihan新版汉字:「㫛」,這些字符可能會错误显示,詳见Unicode扩展汉字。 胤祥怡親王前任:-繼任:弘曉國家大清封爵和硕怡亲王族裔滿洲旗籍正藍旗出生�...

 

阿拉斯加州Alax̂sxax̂ (阿留申语)Alaasikaq (伊努皮克语)Anáaski (特林吉特语)Alas'kaaq (阿魯提克語(英语:Alutiiq language)) 美国联邦州State of Alaska 州旗州徽綽號:最后的边疆(The Last Frontier)格言:北境走向未來(North to the Future)颂歌:阿拉斯加的旗帜(英语:Alaska's Flag)地图中高亮部分为阿拉斯加州坐标:64°N 150°W / 64°N 150°W / 64; -150国家 美国建州前...

German tennis player Heinrich KleinschrothCountry (sports)GermanyBorn(1890-03-15)15 March 1890Kitzingen, German EmpireDied10 January 1979(1979-01-10) (aged 88)Munich, West GermanyTurned pro1906 (amateur tour)Retired1938SinglesHighest rankingNo. 9 (1914, A. Wallis Myers)[1]Grand Slam singles resultsFrench Open4R (1930)Wimbledon3R (1927, 1932)US OpenQ1 (1912)US Open SeniorF (1937)[2]Other tournamentsWHCCQF (1912, 1913)WCCCQF (1913)DoublesGrand Slam ...

 

Mountain rising from the ocean seafloor that does not reach to the water's surface For active seamounts, see Submarine volcano. Marine habitatsBear Seamount Coastal habitats Littoral zone Intertidal zone Estuaries Mangrove forests Seagrass meadows Kelp forests Coral reefs Continental shelf Neritic zone Ocean surface Surface microlayer Epipelagic zone Open ocean Pelagic zone Oceanic zone Sea floor Seamounts Hydrothermal vents Cold seeps Demersal zone Benthic zone Marine sediment vte A seamount...