Roughly Sorting: Sequential and Parallel Approach
Access this Article
Search this Article
Author(s)
Abstract
We study sequential and parallel algorithms on roughly sorted sequences. A sequence a = (a_l a_2 . . . a_n) is ksorted if for all 1⩽i j⩽n i<j k implies a_i⩽a_j. We first show a realtime algorithm for determining if a given sequence is ksorted and an O(n)time algorithm for finding the smallest k for a given sequence to be ksorted. Next we give two sequential algorithms that merge two ksorted sequences to form a ksorted sequence and completely sort a ksorted sequence. Their running times are O(n) and O(n log k) respectively. Finally parallel versions of the completesorting algorithm are presented. Their parallel running times are O(f(2k) 1og k) where f(t) is the computing time of an algorithm used for finding the median among t elements.We study sequential and parallel algorithms on roughly sorted sequences. A sequence a = (a_l, a_2, . . . , a_n) is ksorted if for all 1⩽i,j⩽n,i<j k implies a_i⩽a_j. We first show a realtime algorithm for determining if a given sequence is ksorted and an O(n)time algorithm for finding the smallest k for a given sequence to be ksorted. Next, we give two sequential algorithms that merge two ksorted sequences to form a ksorted sequence and completely sort a ksorted sequence. Their running times are O(n) and O(n log k), respectively. Finally, parallel versions of the completesorting algorithm are presented. Their parallel running times are O(f(2k) 1og k), where f(t) is the computing time of an algorithm used for finding the median among t elements.
We study sequential and parallel algorithms on roughly sorted sequences. A sequence a = (a_l, a_2, . . . , a_n) is ksorted if for all 1<≤i,j<≤n,i<jk implies a_i<≤a_j. We first show a realtime algorithm for determining if a given sequence is ksorted and an O(n)time algorithm for finding the smallest k for a given sequence to be ksorted. Next, we give two sequential algorithms that merge two ksorted sequences to form a ksorted sequence and completely sort a ksorted sequence. Their running times are O(n) and O(n log k), respectively. Finally, parallel versions of the completesorting algorithm are presented. Their parallel running times are O(f(2k) 1og k), where f(t) is the computing time of an algorithm used for finding the median among t elements.
Journal

 Journal of Information Processing

Journal of Information Processing 12(2), 154158, 19890825
Information Processing Society of Japan (IPSJ)