Sorting an Array in Linear (O(N)) Time

Question

I'm working on an exercise currently regarding Sorting Algorithms. The actual exercise is structured like this:

Given a sequence of N real numbers, find the pair of integers that are farthest apart in value. Give a O(N) algorithm. Describe your proposed algorithm in English.

I am not familiar currently with any linear sorting algorithms, so I wanted to ask here about it. Is there a specific type of sorting algorithm that would work best in this situation? If so, what is it and how does that particular algorithm work?

Thanks!

Answer 1

There's no need for you to sort. All you are doing is finding the min of the list of numbers, which takes O(N), then find the max of the list of numbers, which again takes O(N).

Answer 2

Sorting all elements in a list is impossible in O(n) time. It will take minimally O(n log(n)) time.

however, this problem does not require sorting all the elements, only two of them.

Simply iterate over the list once, and keep the largest and smallest values.

Answer 3

As being pointed out, you just need to find min and max. Obviously you can find them separately and it takes O(n), to be exact it takes 2*n comparisons. But as in CLRS you can do it better, reducing number of comparisons to 1.5*n by finding min, max concurrently. The idea is as follow:

1) initialize min = a[0], max = a[0]

2) for i=1 to n-1, compare a[i] and a[i+1]. And then compare and update accordingly: min(a[i],a[i+1]) with min; max(a[i],a[i+1]) with max.

Answer 4

This is what you need :

public class MinMax {
    public static void main(String[] args) {
        int numberarray[] = { 5, 6, 8, 1, 3, 5, 4, 6, 9, 4, 2, 3, 4, 7, 9, 6 };
        int min, max;
        min = max = numberarray[0];

        for (int i = 0; i < numberarray.length; i++) {
            if (numberarray[i] < min)
                min = numberarray[i];
            if (numberarray[i] > max)
                max = numberarray[i];
        }       
        System.out.println("The pair farthest apart is ( "+max+" , "+min+" )");
    }
}

Answer 5

I'm writing in Java.

int min=Integer.MAX_VALUE; int max=Integer.MIN_VALUE;

for(int i=0;i

   if(a[i]<a[i+1]){ 
      if(a[i]<min) min=a[i];
      if(a[i+1]>max)max=a[i+1];
   }

   else{//a[i]>=a[i+1]
      if(a[i+1]<min) min=a[i+1];
      if(a[i]>max)max=a[i];

    }

}

So total number of comparisons is 1.5*n;