Login | Register

Fast parallel algorithms for sorting and median finding


Fast parallel algorithms for sorting and median finding

Dachraoui, Taoufik (1996) Fast parallel algorithms for sorting and median finding. Masters thesis, Concordia University.

[thumbnail of MQ26012.pdf]
Text (application/pdf)


Many sorting algorithms that perform well on uniformly distributed data suffer significant performance degradation on non-random data. Unfortunately many real-world applications require sorting on data that is not uniformly distributed. In this thesis, we propose a new strategy, A-ranksort, for sorting on parallel machines which has a stable behavior on input distributions of different entropies. Our sorting algorithm essentially consists of deterministically computing approximate ranks for the input keys, and using these to route to destinations that are guaranteed to be close to the final destination, and finally using a few steps of odd-even transposition sort to complete the sorting. We implemented A-ranksort, B-flashsort (40), Radix sort (20), and Bitonic sort (6) on a 2048 processor Maspar MP-1. Thearling (73) proposes a test suite of inputs with which to evaluate the performance of sorting algorithms. We tested all the algorithms on a very similar test suite. Using similar ideas, we also designed a new deterministic selection algorithm for integers that is simple and fast. (Abstract shortened by UMI.)

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Dachraoui, Taoufik
Pagination:x, 65 leaves ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Thesis Supervisor(s):Narayanan, Lata
Identification Number:QA 76.6 D325 1996
ID Code:169
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:10
Last Modified:13 Jul 2020 19:45
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top