User:Ncrosty

From Wikipedia, the free encyclopedia


[edit] Nathan Crosty

crostyna@msu.edu

Computer Science Student at Michigan State University

[edit] Projects

/*
  N. Crosty
  "RoughCut"

  This algorithm roughly sorts lists of numerical values with reasonably
  even distrobution in order N processes.  If the list is required to be 
  sorted exactly, this Roughcut will improve performance on a successive
  sorting algorithm by reducing the number of inversions thus reducing the 
  number of required processes.


  TO DO:
  - Shorten run time to O(N)
  - Elimate the temporary vector
  - Better function for rounding "newPlace"
  - Better formula for finding the percentage
      > Efficient and accurate handling of any distrobution
      > Will require some statistics figures
      > Speed is more important than accuracy!

  BUGs:
  - Currently requires the list to begin with lowest value 0
*/


#include<iostream>
#include<vector>
#include<math.h>

using namespace std;

template <typename T> void roughCut( std::vector <T> & In );

template <typename T>
  void roughCut( vector<T> & In )
  {

    double largestVal = In[0];
    double smallestVal = In[0];
    double Percentage;
    int newPlace;

    typename vector<T>::iterator theIterator;
    vector<T> tempStorage;
    typename vector<T>::iterator newPlaceIterator; //holds the position of new data.


    //set the largest and smallest values.
    //note, smallest value is not currently in use
    for(theIterator=In.begin(); theIterator != In.end(); theIterator++)
    {
      // dereference theIterator which is equivalent to In[i]
      if( *theIterator < smallestVal ) { smallestVal = double(*theIterator); }
      if( *theIterator > largestVal ) {largestVal = double(*theIterator); }
    }

    for( theIterator=In.begin(); theIterator != In.end() ; theIterator++ )
    {
      // Only works when the list starts at zero.
      // Need a better formula, this is a huge disadvantage.
      //what happens with a 0 value?
      Percentage = ( double(*theIterator) / largestVal );
        
      if( tempStorage.empty() )
      {
        tempStorage.push_back(*theIterator);

      } else{
        //use a better function than floor to round up or down
        //set the approximate new place for our value
        newPlace = int( floor( Percentage  *  tempStorage.size() ) );  

        //the insert method needs to have an iterator pointing to where we want to insert
        //lets relate In[newPlace] to an iterator.
        newPlaceIterator = tempStorage.begin() + newPlace ;

             //insert the object in its new place according
             //to its relation to what is already there
             if( *theIterator >= *newPlaceIterator )
             {
               tempStorage.insert(newPlaceIterator, *theIterator);
             } else if( *theIterator < *newPlaceIterator ) {
                 if(newPlaceIterator > tempStorage.begin())
                 {
                   tempStorage.insert( (newPlaceIterator - 1) , *theIterator); 
                 }else { 
                   tempStorage.insert(newPlaceIterator, *theIterator);
                 }
             }
           }

    } //end of for loop

  In = tempStorage;
  }