Roughly Sorting: Sequential and Parallel Approach

Abstract

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.

Journal

Journal of information processing   [List of Volumes]

Journal of information processing 12(2), 154-158, 1989-08-30  [Table of Contents]

Information Processing Society of Japan (IPSJ)

Preview

Preview

Codes

  • NII Article ID (NAID) :
    110002673489
  • NII NACSIS-CAT ID (NCID) :
    AA00700121
  • Text Lang :
    ENG
  • ISSN :
    03876101
  • Databases :
    NII-ELS 

Share