- 著者
- Tom Altman Yoshihide Igarashi
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- Journal of Information Processing (ISSN:18826652)
- 巻号頁・発行日
- vol.12, no.2, pp.154-158, 1989-08-25
We study sequential and parallel algorithms on roughly sorted sequences. A sequence a = (a_l a_2 . . . a_n) is k-sorted if for all 1⩽i j⩽n i<j- k implies a_i⩽a_j. We 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 we 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(n log k) respectively. Finally parallel versions of the complete-sorting 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 k-sorted if for all 1⩽i,j⩽n,i<j- k implies a_i⩽a_j. We 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, we 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(n log k), respectively. Finally, parallel versions of the complete-sorting 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.
- 著者
- Tom Altman Yoshihide Igarashi
- 雑誌
- Journal of Information Processing (ISSN:18826652)
- 巻号頁・発行日
- vol.12, no.2, pp.154-158, 1989-08-25
We study sequential and parallel algorithms on roughly sorted sequences. A sequence a = (a_l a_2 . . . a_n) is k-sorted if for all 1⩽i j⩽n i<j- k implies a_i⩽a_j. We 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 we 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(n log k) respectively. Finally parallel versions of the complete-sorting 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.