Comparing 1 million integers in an array without sorting it first

user_598343 0
Viewed 1972

I have a task to find the difference between every integer in an array of random numbers and return the lowest difference. A requirement is that the integers can be between 0 and int.maxvalue and that the array will contain 1 million integers.

I put some code together which works fine for a small amount of integers but it takes a long time (so long most of the time I give up waiting) to do a million. My code is below, but I'm looking for some insight on how I can improve performance.

for(int i = 0; i < _RandomIntegerArray.Count(); i++) {
  for(int ii = i + 1; ii < _RandomIntegerArray.Count(); ii++) {
    if (_RandomIntegerArray[i] == _RandomIntegerArray[ii]) continue;

    int currentDiff = Math.Abs(_RandomIntegerArray[i] - _RandomIntegerArray[ii]);

    if (currentDiff < lowestDiff) {
      Pairs.Clear();
    }

    if (currentDiff <= lowestDiff) {
      Pairs.Add(new NumberPair(_RandomIntegerArray[i], _RandomIntegerArray[ii]));
      lowestDiff = currentDiff;
    }
  }
}

Apologies to everyone that has pointed out that I don't sort; unfortunately sorting is not allowed.

algorithm c#
6 Answers

It helps a little if you do not count on each iteration 

int countIntegers = _RandomIntegerArray.Count();
for(int i = 0; i < countIntegers; i++) {
    //...
    for(int ii = i + 1; ii < countIntegers; ii++) {
        //...

Given that Count() is only returning the number of Ints in an array on each successful count and not modifying the array or caching output until modifications.

user_29686210
Related