Roughly sorting: Sequential and parallel approach

Roughly sorting: Sequential and parallel approach

0.00 Avg rating0 Votes
Article ID: iaor19891008
Country: Japan
Volume: 12
Issue: 2
Start Page Number: 154
End Page Number: 158
Publication Date: Sep 1989
Journal: Journal of Information Processing
Authors: ,
Keywords: sorting
Abstract:

The authors study sequential and parallel algorithms on roughly sorted sequences. A sequence α=(a1,a2,...,an) is k-sorted if for all 1•i, j•n, i<j-k implies ai•aj. They first show a real-time algorithm for determining if a given sequence is k-sorted and an O(n)-time algorithm for finding the smallest k for a given sequence to be k-sorted. Next, the authors give two sequential algorithms that merge two k-sorted sequences to form a k-sorted sequence and completely sort a k-sorted sequence. Their running times are O(n) and O(nlogk), respectively. Finally, parallel versions of the complete-sorting algorithm are presented. Their parallel running times are O(f(2k)logk), where f(t) is the computing time of an algorithm used for finding the median among t elements.

Reviews

Required fields are marked *. Your email address will not be published.