0

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!

Improve this question
6
  • 1
    you don't need to sort anything. You can't do that in linear time. You can solve the above issue in linear time. Commented Mar 3, 2014 at 22:06
  • So no sorting is needed? Then how would I traverse that array and find the answer? Would that mean I would just have to find the min and max values in the array? Commented Mar 3, 2014 at 22:08
  • 1
    Find the smallest number in the array and find the largest number. As you iterate over the array. You check if each number is the smallest you have found so far or the biggest you have seen so far, or neither. Commented Mar 3, 2014 at 22:11
  • If you think about it...the pair of numbers that are "farthest apart in value" must be the min and max. Commented Mar 3, 2014 at 22:11
  • Suddenly realized it mentions that all number are real, and then asks for the integers that are furthest apart in value... What? Commented Mar 3, 2014 at 22:17

5 Answers 5

Reset to default
4

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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.

Improve this answer

4 Comments

Not true. Radix sort can sort a list of numbers in linear time.
True, but it was specifically mentioned that it is an array of real numbers, radix sort only works for int (or fixed-point).
Oh my apologies. I didn't take that into consideration.
@Solace: Technically in the RAM model (the one most commonly used in algorithm analysis), radix sort is O(n * w) where w is the word size
1

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.

Improve this answer

2 Comments

Your step 2 is unclear (and I suspect it is wrong). Please write out those statements in full.
@StephenC see my new answer.
0

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+" )");
    }
}
Improve this answer

Comments

0

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;

Improve this answer

5 Comments

That is correct. However, you need to cope with the case where a.length is odd. Also, while you save 0.5N comparisons, (and an extra 0.5N for the loop variable ...) there is more arithmetic. So I think you would need to benchmark this to see what the actual performance benefit is.
you are right that I need to handle the case n is odd also. But I dont get your second point about the need to benchmark this approach to see actual benefit?
The point is that quantifying the actual performance is more complicated than just counting the comparisons. (Especially since you were not actually counting all of the comparisons ... I suspect)
I see your point and I agree on that, for example we have to analyze how we retrieve and read data also. But for that simple piece of code, the analysis should be very simple, don't you agree on that?
No actually, I don't. The real performance will be determined by the native code emitted by the JIT compiler, and even by such things as cache memory behaviour. An analysis that gave answers that correlate strongly with actual measured performance would need to be very complicated indeed ... even for a simple piece of code. By contrast "big O" analysis works by ignoring the issue of actual performance, and focussing on theoretical scalability; i.e. the predicted behaviour of the cost functions as the scaling variables tend towards infinity.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.