Data, sorting, picking 10 largest

[HandleOfMe]

Ok, here is a rather basic problem.

I have 2 sets of data, each containing 1000 floating points. I need to find 10 that changed the most, i.e.

data1[1] - data2[1] = s[1]
data1[2] - data2[2] = s[2]
etc... (repeat 1000 times)

and I need to find s[] with the 10 largest numbers.

How would you go about in doing this?

Thanks

 

[Salem]

Sort the array, say using qsort(), then pick the first 10 entries.

--

 

[xwb]

Before sorting you need to find the values of s first

for (i = 0; i < 1000; i++)
   s[i] = data1[i] - data2[i];

 

[HandleOfMe]

Sorry, one more additional info:

I need to know the original position of the value in the array. if the value was moved from s[900] to s[9], I need to know that it used to be at 900.

 

[cpjust]

If you only need the 10 largest numbers, sorting the whole list is overkill. Use partial_sort()

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;


void PrintInt( int i )
{
	cout << i << ", ";
}


int main()
{
	vector<int> vInt;

	for ( int i = 0; i < 20; ++i )
	{
		vInt.push_back( i );
	}

	random_shuffle( vInt.begin(), vInt.end() );

	// Print random order.
	for_each( vInt.begin(), vInt.end(), PrintInt );
	cout << endl;

	// Move the 5 highest numbers to the front.
	partial_sort( vInt.begin(), vInt.begin() + 5, vInt.end(), greater<int>() );

	// Print partially sorted order.
	for_each( vInt.begin(), vInt.end(), PrintInt );
	cout << endl;

	return 0;
}

 

[HyperEngineer]

You could set up an array of structures:

  numStruct
  {
    int iValue;
    int origIndex;
  };

Then sort on the iValue element

  numStruct s1[1000];
  
  ...

  void elementsort(numStruct[] S1, int beginIndex, int endIndex)
  {
    int i = beginIndex;
    int j = endIndex;
    int temp;
    int compareValue = S1[(beginIndex + endIndex)/2];

    do
      {
        while (S1[i].iValue < compareValue) i++;
        while (S1[j].iValue > compareValue) j--;

        if (i <= j)
        {
          temp = S1[i].iValue;
          S1[i].iValue = S1[j].iValue;
          S1[j].iValue = temp;
          i++;
          j--;
         }
       }while (i<=j);
       
       if (beginIndex <j )
         elementsort(S1, beginIndex, j);
       if (i < endIndex)
         elementsort(S1, i, endIndex);
  }

You sort on the iValue, which are your inputted values that you want to sort on. The origIndex is the original position. This is the spot it was at prior to sorting.

I haven't had a chance to check this code, so I hope it works.


HyperEngineer
If it ain't broke, it probably needs improvement.

 

[uolj]

HyperEngineer is right that you can use a struct to remember the original index and the difference (you could also just use an std:air). I think it is completely unnecessary to write your own sort code (or use somebody else's handwritten attempt).

Just make a comparison operator for your struct and use partial_sort:

struct DiffStruct
{
  double difference;
  int origIndex;
};

bool DiffGreater(const DiffStruct& lhs, const DiffStruct& rhs)
{
  return lhs.difference > rhs.difference;
}

// Assuming DiffStruct s[1000] is filled already.
partial_sort(s, s+10, s+1000, DiffGreater);