Roughly Sorting: Sequential and Parallel Approach

• Item type: JInfP(1)
• 公開日: 1989-08-25
• タイトル: Roughly Sorting: Sequential and Parallel Approach
• タイトル / 言語: en
• タイトル: Roughly Sorting: Sequential and Parallel Approach
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Department of Computer Science University of Kentucky
• 著者所属: Department of Computer Science Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, University of Kentucky
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Gunma University
• 著者名: Tom, Altman; Yoshihide, Igarashi
• 著者名(英): Tom, Altman; Yoshihide, Igarashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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&les;i j&les;n i<j- k implies a_i&les;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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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&les;i,j&les;n,i<j- k implies a_i&les;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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of Information Processing; 巻 12, 号 2, p. 154-158, 発行日 1989-08-25
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会