Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › C++ dual sort/binary search help needed
New Posts  All Forums:Forum Nav:

C++ dual sort/binary search help needed

post #1 of 5
Thread Starter 
Code:
#include <iostream>
#include <fstream>
#include <iomanip>

using namespace std;

const int NUM_EMP = 7;
void getHourWage(long[], int[], double[]);
void calcWage(double[], int[], double[], const int);
void displayStuff(long[], double[], int[], double[], const int);
void dualSort(long[], int[], double[], double [], const int);
int binarySearch(long[], const int, long);
long getEmpNum();
void displayEmp(long[], int[], double[], double[], int);

void main()
{
long empID[NUM_EMP] = {5658845, 4520125, 7895122, 8777541, 8451277, 1302850, 7580489};
int empHours[NUM_EMP];
double payRate[NUM_EMP];
double wages[NUM_EMP];

long empNum;
int index;
    char again; 

cout << fixed << showpoint << setprecision(2);

getHourWage(empID, empHours, payRate);

calcWage(wages, empHours, payRate, NUM_EMP);

dualSort(empID, empHours, payRate, wages, NUM_EMP);

displayStuff(empID, wages, empHours, payRate, NUM_EMP);

   do
   {
      // Get the desired employee number.
      empNum = getEmpNum();

      // Search for the employee number.
      index = binarySearch(empID, NUM_EMP, empNum);

      // Display the results of the search.
      if (index == -1)
         cout << "That employee ID was not found.\n";
      else
         displayEmp(empID, empHours, payRate, wages, index);

      // Does the user want to do this again?
      cout << "Would you like to look up another employee? (y/n) ";
      cin >> again;
   } while (again == 'y' || again == 'Y');

}

void getHourWage(long empID[], int empHours[], double payRate[])
{
for (int index = 0; index < NUM_EMP; index++)
{

cout << "For the employee : " << empID[index] << "\n";

cout << "Please enter the number of hours worked: ";
cin >> empHours[index];
while (empHours[index] < 0)
{
cout << "Please enter the number of hours worked: ";
cin >> empHours[index];
}


cout << "Please enter their pay rate: ";
cin >> payRate[index];
while (payRate[index] < 6.00)
{
cout << "Please enter their pay rate: ";
cin >> payRate[index];
}
cout << endl;
}
}

void calcWage(double wages[], int empHours[], double payRate[], const int NUM_EMP)
{
for (int index = 0; index < NUM_EMP; index++)
wages[index] = empHours[index] * payRate[index];
}

void dualSort(long empID[], int empHours[], double payRate[], double wages[], const int NUM_EMP)
{
   long maxValue;
   int startScan, maxIndex, temphours;
   double tempwages, temppay;

   for (startScan = 0; startScan < (NUM_EMP - 1); startScan++)
   {
      maxIndex = startScan;
      maxValue = empID[startScan];
      temphours = empHours[startScan];
  temppay = payRate[startScan];
  tempwages = wages[startScan];
      for(int index = startScan + 1; index < NUM_EMP; index++)
      {
         if (empID[index] > maxValue)
         {
            maxValue = empID[index];
            temphours = empHours[index];
temppay = payRate[index];
tempwages = wages[index];
            maxIndex = index;
         }
      }
     empHours[maxIndex] = empHours[startScan];
     empID[maxIndex] = empID[startScan];
 payRate[maxIndex] = payRate[startScan];
 wages[maxIndex] = wages[startScan];

     empID[startScan] = maxValue;
     empHours[startScan] = temphours;
 wages[startScan] = tempwages;
 payRate[startScan] = temppay;

   }
}

void displayStuff(long empID[], double wages[], int empHours[], double payRate[], const int NUM_EMP)
{
ofstream OutputFile;

//OutputFile.open("F:\\CIS251\\StudentData\\KBbill.dat");
OutputFile.open("J:\\Documents\\School\\CIS251\\DATA\\PayRoll.txt"/*, ios::_Nocreate*/);

cout << "Employee ID\tWages\n";
cout << "--------------------------------------------------\n";

for (int index = 0; index < NUM_EMP; index++)
{
cout << empID[index] << "\t\t$";
cout << wages[index] << endl;
OutputFile << empID[index] << "#" << empHours[index] << "#" << payRate[index] << "#" << wages[index] << "\n";
}

cout << "\nData has been written to file.\n\n";
OutputFile.close();
}

long getEmpNum()
{
   long empNum;  // Employee Number

   cout << "Enter the employee's ID number: ";
   cin >> empNum;

   return empNum;
}

int binarySearch(long array[], const int NUM_EMP, long empNum)
{
   int first = 0,           // First array element
       last = NUM_EMP - 1, // Last array element
       middle,              // Mid point of search
       position = -1;       // Position of search value
   bool found = false;      // Flag

   while (!found && first <= last)
   {
      middle = (first + last) / 2;  // Calculate mid point
      if (array[middle] == empNum)   // If value is found at mid
      {
         found = true;
         position = middle;
      }
      else if (array[middle] > empNum) // If value is in lower half
         last = middle - 1;
      else
         first = middle + 1;          // If value is in upper half
   }
   return position;
}

void displayEmp(long empID[], int empHours[], double payRate[], double wages[], int index)
{
   cout << "\nEmployee ID: " << empID[index] << endl;
   cout << "Hours: " << empHours[index] << endl;
   cout << "Pay Rate: $" << payRate[index] << endl;
   cout << "Total Wages: $" << wages[index] << endl << endl;

}

Hey guys, having a bit of trouble with this binary search. The programs purpose is to get hours and payrate for 9 employees, and store the values in an array.

then sort the employee ID, display/write some info to a file, then ask the user to search for an employee, and then write all of that employee's information to the screen.

what i've written works, but only for the employeeID : 7580489, the last ID in the array.

any help would be great, as i'm stumped
Edited by shrapner - 7/17/11 at 6:47pm
i7-860
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 860 ASUS P7P55D-E LX Sapphire HD 6950 Unlocked 1536 Shaders 1.175v 8GB Samsung MV-3V4G3 
Hard DriveHard DriveOptical DriveOS
2x Spinpoint F3 7200RPM 500GB Samsung 830 SSD Samsung Black 2MB Cache SATA CD/DVD Burner Windows 7 Professional x64 
MonitorKeyboardPowerCase
Viewsonic VX2433wm Logitech EX110 Corsair 750TX Cooler Master HAF 922 
MouseAudioOther
Logitech LX7 Xonar Essence STX Denon AH-D2000 
  hide details  
Reply
i7-860
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 860 ASUS P7P55D-E LX Sapphire HD 6950 Unlocked 1536 Shaders 1.175v 8GB Samsung MV-3V4G3 
Hard DriveHard DriveOptical DriveOS
2x Spinpoint F3 7200RPM 500GB Samsung 830 SSD Samsung Black 2MB Cache SATA CD/DVD Burner Windows 7 Professional x64 
MonitorKeyboardPowerCase
Viewsonic VX2433wm Logitech EX110 Corsair 750TX Cooler Master HAF 922 
MouseAudioOther
Logitech LX7 Xonar Essence STX Denon AH-D2000 
  hide details  
Reply
post #2 of 5
does it only work for employeeID : 7580489; or any ID number in the last position in the array? also, what happens when the program doesnt work for the other IDs?

it looks like your binary search method is set up correctly. it will only work correctly if the array is properly sorted. have you verified that the dual sort method is functioning properly? it looks like you already thought of that though, since you have a display method.

thats all the advice i can give atm, since your code is somewhat difficult to read. so many emps, nums, and IDs sprinkled throughout your program tongue.gif
Fractal Design
(15 items)
 
775 4 life
(15 items)
 
 
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix 
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64 
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W 
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer 
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400 
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi 
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5 
Mouse
Razor Abyssus 
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3 
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ... 
Power
9-cell plus Slice battery 
  hide details  
Reply
Fractal Design
(15 items)
 
775 4 life
(15 items)
 
 
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix 
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64 
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W 
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer 
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400 
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi 
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5 
Mouse
Razor Abyssus 
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3 
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ... 
Power
9-cell plus Slice battery 
  hide details  
Reply
post #3 of 5
Thread Starter 
yea i know, i need to rename some things, i haven't checked to see if i switch the emp numbers to see if it is def the last, when they are sorted the number that works is in the middle position.

when it doesn't work, it just tells the user that the id wasn't found, and asks if they'd like to search again.

EDIT ok. the only value that works is the middle 7580489 order i had them programmed into the array with doesn't matter. it sorts properly but the only value the search works for is that one.
Edited by shrapner - 7/17/11 at 8:14pm
i7-860
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 860 ASUS P7P55D-E LX Sapphire HD 6950 Unlocked 1536 Shaders 1.175v 8GB Samsung MV-3V4G3 
Hard DriveHard DriveOptical DriveOS
2x Spinpoint F3 7200RPM 500GB Samsung 830 SSD Samsung Black 2MB Cache SATA CD/DVD Burner Windows 7 Professional x64 
MonitorKeyboardPowerCase
Viewsonic VX2433wm Logitech EX110 Corsair 750TX Cooler Master HAF 922 
MouseAudioOther
Logitech LX7 Xonar Essence STX Denon AH-D2000 
  hide details  
Reply
i7-860
(15 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 860 ASUS P7P55D-E LX Sapphire HD 6950 Unlocked 1536 Shaders 1.175v 8GB Samsung MV-3V4G3 
Hard DriveHard DriveOptical DriveOS
2x Spinpoint F3 7200RPM 500GB Samsung 830 SSD Samsung Black 2MB Cache SATA CD/DVD Burner Windows 7 Professional x64 
MonitorKeyboardPowerCase
Viewsonic VX2433wm Logitech EX110 Corsair 750TX Cooler Master HAF 922 
MouseAudioOther
Logitech LX7 Xonar Essence STX Denon AH-D2000 
  hide details  
Reply
post #4 of 5
Trying to work through it, I'll let you know if I figure anything out
Edited by Tomiger - 7/18/11 at 10:46am
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
post #5 of 5
Change
Code:
else if (array[middle] > empNum) // If value is in lower half

To
Code:
else if (array[middle] < empNum) // If value is in lower half

If you ever get stuck on these kinds of things, don't be hesitant to pull out a pad of paper and a pen and just walk through your algorithm. If you did that for this case, you'd notice that you were moving in the wrong direction in your binary search (the search for the highest value [index 0 in the array] causes the algorithm to make the middle larger, thus moving downwards instead up upwards). Likewise, if your array was sorted in ascending order, your first algorithm would work correctly.
Edited by Tomiger - 7/18/11 at 11:09am
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › C++ dual sort/binary search help needed