User:Ncrosty
From Wikipedia, the free encyclopedia
[edit] Nathan Crosty
crostyna@msu.edu
Computer Science Student at Michigan State University
[edit] Projects
- Common Components - A Wiki cross reference for efficiently finding common components
- Formula SAE Racing - Telemetry
- RoughCut in C++
/* 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; }