Advertisement
Guest User

Calculating the Mode of a sorted array in 1 pass.

a guest
Sep 10th, 2012
253
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. //Pre: The array passed in should already be sorted.
  2. //Post: Returns the number that occurs the most.
  3. //Purpose: Determine which number occurs most often in a sorted array.    
  4. int CalcMode(/*IN*/ const IntArr& numArr,       //Sorted array to calculate the mode for.
  5.              /*IN*/ int numFilled)                  //Number of filled indices.
  6. {
  7.     int modeInd = 0;    //Index of the Mode
  8.     int modeRun = 0;    //Run Length of the current Mode
  9.  
  10.     int currInd = 0;    //Index of Current Test
  11.     int currRun = 0;    //Current Run Length
  12.  
  13.     int ind = 0;        //Working Index
  14.  
  15.     //Count the run for the first number in the array and initialize the currInd
  16.     //I had this as an if inside the next while but it only executes for the first
  17.     //number so I just separated it so it wasn't a Kobayashi Maru, hence wasting processing.
  18.     while(numArr[ currInd ] == numArr[ modeInd ])
  19.     {
  20.         modeRun++;
  21.         currInd++;
  22.     }
  23.  
  24.     //Iterate through every element.
  25.     while(ind < numFilled - 1)
  26.     {
  27.         //Test if the working num is part of the current run:
  28.         if(numArr[ ind ] == numArr[ currInd ])
  29.         {
  30.             currRun++;
  31.         }//end consecutivity test.
  32.         else
  33.         {
  34.             currInd = ind;
  35.             currRun = 0;
  36.         }//end non-consecutive branch.
  37.  
  38.         //Test if the current run is longer than the recorded mode:
  39.         if(currRun > modeRun)
  40.         {
  41.             modeInd = currInd;
  42.             modeRun = currRun;
  43.  
  44.             //Move the currInd to the NEXT working index.
  45.             currInd = ind + 1;
  46.             currRun = 0;
  47.         }//End if
  48.  
  49.         ind++;
  50.     }//End while
  51.  
  52.     return modeInd;
  53. }//End CalcMode();
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement