Testing if an Array Is Sorted

Suppose we would like to check whether a given array of real numbers is sorted (say, in nondecreasing order). Performing this task exactly requires reading the entire array. Here we consider the approximate version of the problem: testing whether an array is sorted or “far ” from sorted. We consider two natural definitions of the distance of a given array from a sorted array. Intuitively, we would like to measure how much the input array must change to become sorted. We could measure the change by 1. the number of entries changed; 2. the sum of the absolute values of changes in all entries. It is not hard to see that looking at the number of entries that must be deleted in an array to make it sorted is equivalent to the measure in item 1. To define the two distance measures formally, let a = (a1,..., an) be the input array and S be the set of all sorted arrays of length n. We denote by [n] the set {1, 2,..., n}. The Hamming distance from a to S, denoted dist(a,S), is minb∈S |{i ∈ [n] : ai 6 = bi}|. The L1 distance from a to S, denoted dist1(a,S), is minb∈S i∈[n] |ai−bi|