Find two elements in array having sum equal to given element

We can use insertion sort method to find the two element from the array having sum same as given element. Method FindSum displays two elements from array having sum same as given element.

void FindSum( int * a, int size, int Sum) {     int firstNum = 0, secondNum = -1;     for(; firstNum < size; firstNum++)     {         int sercahKey = Sum - a[firstNum];         for( int i = firstNum + 1; i < size; i++)         {             if( sercahKey == a[i] )             {                 secondNum = i;                 break;             }         }         if( secondNum != -1 )             break;     }     if( secondNum == -1 )         cout << "Could not found two number having sum " << Sum << endl;     else         cout << "found two number having sum [" << Sum  << "] as [ " << a[firstNum] << "] and [" << a[secondNum] << "]."  << endl; }

The above method requires o(n2) time complexity. Using map the time complexity can be reduced to o(n) as shown in below method.

void FindPairMatchingSum(int * arr,  int size, int sum) {     map<int, int> mapOfArray;     for (int i = 0; i < size; i++)     {         mapOfArray.insert(make_pair(arr[i], i));     }     for (int  i = 0; i <size; i++)     {         int key = sum - arr[i];         map<int, int>::const_iterator kit = mapOfArray.find(key);         if (kit != mapOfArray.end())         {             cout << "Found Pair at index : " << i  << "  & " << kit->second;             break;         }     } }

Implementing Selection Sort Algorithm in C++/C

SelectionSort method implements Selection Sort algorithm in the simplest way. This method you can use in C/C++ program. Method takes integer array and size the array to be sorted and sorts the array in place.

 

void SelectionSort(int * array, int nSize) {     if( NULL == array )         return;        if( nSize < 1 )         return;     for( int nIterator = 0; nIterator < nSize - 1; nIterator++)     {         int nCurrentLow = array[nIterator];         int nPos = nIterator;         for( int nTemp = nIterator +1; nTemp < nSize; nTemp++ )         {             if( nCurrentLow > array[ nTemp ] )             {                 nCurrentLow = array[ nTemp ];                 nPos = nTemp;             }         }         array[nPos] = array[ nIterator ];         array[nIterator] = nCurrentLow;     } }