# I don't know how to explain this in debug

Thanks guys for the input. I know I should not spend so much time in reinventing the wheel designing the sort algorithm.......BUT, I just feel like having some stimulation on the old brain. It is NOT easy, I spent like a week on this. But I really feel I learn a lot. Call it stupid sort or whatever, I did it.

I know it's pointless to optimize the speed, I just did it for the hell of it. The program ask to input information into each structure, then it immediately sort and store in the vector. So the elements of the vector are sorted already. Any new element added will be sorted and added in. Sounds easy enough, but I can assure you it's a whole lot harder than bubble or selection sort and a whole lot less steps. I don't know any other sorting method, so I just made this up. Call it stupid sort or whatever, I did this on my own.

My program not only sort the last name, I sort the first name also. I can input as many names as I want as I am using vector of structure to give me the flexibility. I made so much mistakes it's not funny. Things that work most of the time and fail occasionally. I don't know how many time I stepped through the program in debug. Finally I stopped and actually work out a table that really help me in seeing all the potential error. This is my program that ask you to input last name and first name, it will first sort the last name and then sort the first name within the same last name. Also tracking the element number of the vector array.
C++:
#include <iostream>
#include <cstring>
#include <vector>
#include <iomanip>
using namespace std;
const static int nameLen = 25, phoneLen = 12;
struct Directory { char lastName[nameLen]; char firstName[nameLen];    char phone[phoneLen]; int element; };
std::vector<Directory>DirV;
Directory Dir;
void sort_firstName(int&);
int main()
{
int newName;
char more, displayAll;
do
{   cout << " Enter last name:  "; cin.getline(Dir.lastName, nameLen);
cout << " Enter first name:  "; cin.getline(Dir.firstName, nameLen);
sort_firstName(newName);
cout << " The new element added is DirV[" << newName << "] \n\n";
cout << " Do you want to enter another name?  "; cin.get(more);
cin.ignore();
} while (tolower(more) == 'y');
int index = 0;

do
{ cout << "   Name stored in DirV[" << DirV[index].element << "]  is:   Last name: "
<< left << setw(10) << DirV[index].lastName << "    First name: " << left <<
setw(10) << DirV[index].firstName << "    phone:  " << DirV[index].phone << "\n\n";
index++;
}while (index < DirV.size());
return 0;
}

{ int size, selCase;
DirV.push_back(Dir);//Push to next available element of DirV.
size = DirV.size();// DirV[midPt].element = midPt; newName = midPt;
int startPt = 0, endPt = size - 2, midPt = (endPt - startPt) / 2;
if((size == 1) || ((strcmp(DirV[endPt].lastName, Dir.lastName) <= 0) & (size >= 2)))
selCase = 0;//Don't have to sort or anything, Dir is in last element already
//Case 0 for first entry when size = 1 OR when Dir.lastName is
// >= to last element of DirV(Dir.lastName >= DirV[endPt].lastName.
else
{if((strcmp(Dir.lastName, DirV[startPt].lastName) <= 0) && (size > 1))
selCase = 1;//If Dir smaller than DirV AND (size >1)
else
{ startPt = 0, endPt = size - 2; midPt = (endPt - startPt) / 2;
do {  if (strcmp(Dir.lastName, DirV[midPt].lastName) <= 0)
{ endPt = midPt; midPt = (startPt + endPt) / 2; }
else {startPt = midPt; midPt = (startPt + endPt) / 2; }
}while (startPt != midPt);
selCase = 2;
}//else selCase = 2
}
switch(selCase)
//(size = 1)  AND  Dir.lastName => DirV[endPt].lastName
{case 0: { DirV[size - 1].element = size - 1; newName = size - 1; break;}
case 1://Dir.lastName <= DirV.lastName
{ int i;
for(i = 1; i <= (size - 1); i++)
{ DirV[size - i] = DirV[size - i - 1];
DirV[size - i].element = size - i;
DirV[size - i - 1].element = size - i - 1;
}
DirV[size - i] = Dir; newName = size - i;
DirV[size - i].element = size - i;
break;
}
case 2:
{ int j;
for(j = 1; j <= (size - endPt - 1); j++)
{ DirV[size - j] = DirV[size - j - 1];
DirV[size - j].element = size - j;
DirV[size - j - 1].element = size - j - 1;
}
DirV[size - j] = Dir; newName = size - j;
DirV[size - j].element = size - j;
break;
}
}

}

void sort_firstName(int& newName)//DirV[newName] is the element of the newly added name.
{   int beginLname = newName, endLname = newName;//start out all equal
int bubbleDown, bubbleUp;
Directory Temp;//Temporary structure variable to store structure Directory
Temp = DirV[newName];
bool doneUp = false, doneDown = false, moveUp = false;
bubbleUp = newName; bubbleDown = newName;
while ((bubbleUp > 0) & !doneUp)//Prevent bubbleUp going negative
{if((strcmp(DirV[newName].lastName, DirV[newName - 1].lastName) == 0)
& (strcmp(DirV[newName].firstName, DirV[newName - 1].firstName) < 0))
{DirV[newName] = DirV[newName - 1]; DirV[newName].element = newName;
DirV[newName - 1] = Temp; DirV[newName - 1].element = newName - 1;
newName--;bubbleUp--; moveUp = true;}
else (doneUp = true);
}//END while((bubbleUp > 0)& !doneUp)
if (moveUp == false)
{while ((bubbleDown < (DirV.size()-1)) & !doneDown)
{ if((strcmp(DirV[newName].lastName, DirV[newName + 1].lastName) == 0)
&(strcmp(DirV[newName].firstName, DirV[newName + 1].firstName) > 0))
{ DirV[newName] = DirV[newName + 1]; DirV[newName].element = newName;
DirV[newName + 1] = Temp; DirV[newName + 1].element = newName + 1;
newName++; bubbleDown++; }
else doneDown = true;
}//END while (decrement < bubbleUp)
}
}
This is a big step in completing my Directory program that store name, phone, address and email address. Also it uses Classes. This program really make me practice all the things I learned.

Attached is my table I used to write this program. I spent a few hours typing this in, that really helped me to see my bugs.

Thanks for all the help.

#### Attachments

• 21.4 KB Views: 28
Last edited:
• sysprog
yungman said:
Thanks guys for the input. I know I should not spend so much time in reinventing the wheel designing the sort algorithm.......BUT, I just feel like having some stimulation on the old brain. It is NOT easy, I spent like a week on this. But I really feel I learn a lot. Call it stupid sort or whatever, I did it.
I think that you are right to be pleased at having succeeded at working through some difficulties.

Just to clarify something that seems as if it may have been misunderstood: no-one here was trying to say anything derisive about your alorithm or your implementation of it ##-## the reference to "stupid sort" was in the context of discussion of sort algorithms in general, and of a classroom example that was decades ago presented as cautionary illustration of a possible inefficiency that could be brought into a sorting algorithm, due to failing to fully think it through.

Good on you for doing the work to keep your mental faculties in good shape.

• yungman
I think that you are right to be pleased at having succeeded at working through some difficulties.

Just to clarify something that seems as if it may have been misunderstood: no-one here was trying to say anything derisive about your alorithm or your implementation of it ##-## the reference to "stupid sort" was in the context of discussion of sort algorithms in general, and of a classroom example that was decades ago presented as cautionary illustration of a possible inefficiency that could be brought into a sorting algorithm, due to failing to fully think it through.

Good on you for doing the work to keep your mental faculties in good shape.
Thanks

I like the challenge too. It's one thing to learn all the names and their meanings, it's another thing to let the rubber hit the road. It really started out thinking that was easy, you have a vector that is already sorted, how hard can it be to add a new one in the right place? NOT!!! It sounded so easy to set the starting point, the end point and middle = ( start + end)/2 and if new one is smaller than middle, end = middle, middle = ( start + end)/2 and do it over................... WRONG!!! That's how I spent 5 days going no where. Finally I created the chart, keeping tract of the start (S), middle (M) and end(E) as you see in subscripts in the word file. Then you can see how they being set. They don't behave the same depending on the position and the length of the original vector( ' --- ' in the chart shows where the new name fits in the existing vector). Took me 4 hours to generate the file, then one day to implement and debug to make it work. this is live and learn.

This reminds me in kick boxing, people keep admiring the round house kick and side kick that look so hard. They think front kick is easy, just pick up your foot and kick..................WRONG!!! Round and side kick has a steep learning curve, but once you get good, you are good. That stupid front kick looks so easy, believe me, it takes YEARS to master it to generate the power. You wonder why in MMA and other kick boxing tournaments seldom use front kicks? It's NOT easy to generate power. Last thing you want is you land a kick and the opponent just look at you!!!

Anyway, I am happy, I almost going to give up and put in the selection sort........But I guess it's not in my nature. Now that my study schedule is out the window delayed by this!!! The next step is displaying a range of selected names, choose one I want to delete and resort the file, that complete the sorting. Last step is to implement this back to my main program of Directory of names with address, phone, email and store in file using Classes.

Last edited:
• sysprog
pbuk
Gold Member
I like the challenge too. It's one thing to learn all the names and their meanings, it's another thing to let the rubber hit the road. It really started out thinking that was easy, you have a vector that is already sorted, how hard can it be to add a new one in the right place? NOT!!! It sounded so easy to set the starting point, the end point and middle = ( start + end)/2 and if new one is smaller than middle, end = middle, middle = ( start + end)/2 and do it over................... WRONG!!! That's how I spent 5 days going no where. Finally I created the chart, keeping tract of the start (S), middle (M) and end(E) as you see in subscripts in the word file. Then you can see how they being set. They don't behave the same depending on the position and the length of the original vector( ' --- ' in the chart shows where the new name fits in the existing vector). Took me 4 hours to generate the file, then one day to implement and debug to make it work. this is live and learn.
Ah, I see what you have done. Rather than sorting, you have maintained the vector in a sorted state by inserting each new element into the right place. The algorithm you have used is called binary search if you want to look into this further.

Anyway, I am happy, I almost going to give up and put in the selection sort........But I guess it's not in my nature. Now that my study schedule is out the window delayed by this!!! Not much point in sorting a vector that is already sorted. There are better ways of organising this kind of data in a tree as I think I mentioned above, but this is a whole new subject that will take some time to master.

The next step is displaying a range of selected names, choose one I want to delete and resort the file, that complete the sorting.
Again you won't need to resort it, will you?

• yungman
Ah, I see what you have done. Rather than sorting, you have maintained the vector in a sorted state by inserting each new element into the right place. The algorithm you have used is called binary search if you want to look into this further.

Not much point in sorting a vector that is already sorted. There are better ways of organising this kind of data in a tree as I think I mentioned above, but this is a whole new subject that will take some time to master.

Again you won't need to resort it, will you?
Thanks

I cannot find a better word than "sort"!! Yes, the vector is sorted, just want to insert the new element into it. I read the name binary search and tree in later chapters. I just decided to be adventurous and do it. I don't want to wait and wait until I learn all the tools before attempt doing something. That's part of the adventure!!!

thanks

• sysprog
Thanks

I cannot find a better word than "sort"!! Yes, the vector is sorted, just want to insert the new element into it. I read the name binary search and tree in later chapters. I just decided to be adventurous and do it. I don't want to wait and wait until I learn all the tools before attempt doing something. That's part of the adventure!!!

thanks
What you're doing is an insertion sort with a binary search instead of iterative comparisons to determine the insertion point ##-## there's a C++ example here: https://www.geeksforgeeks.org/binary-insertion-sort/

• yungman
What you're doing is an insertion sort with a binary search instead of iterative comparisons to determine the insertion point ##-## there's a C++ example here: https://www.geeksforgeeks.org/binary-insertion-sort/
Actually this is a lot easier than what I am doing. The tricky part is to start the vector with no element. If you look at the subscripts S, M and E in my word file, you'll see they are different when you first push_back into an empty file. As it turn out, I don't even have to create the second page for 6 and 7 elements, you can see the trend in the first page already. That's the reason I separate into 3 different cases, case0, case1 and case2 and have to be treated differently. pbuk
Gold Member
The tricky part is to start the vector with no element.
That's not usually tricky, the implementation should go something like this:
pseudocode:
function insertElement(element, array)
// Set the lowest and highest points possible for insertion.
low = 0;
high = array.length;
// Note if the array is empty high == low == 0 so the loop
// is not executed and the element is inserted at array
while high > low
midpoint = floor((high + low) / 2)
...

That's not usually tricky, the implementation should go something like this:
pseudocode:
function insertElement(element, array)
// Set the lowest and highest points possible for insertion.
low = 0;
high = array.length;
// Note if the array is empty high == low == 0 so the loop
// is not executed and the element is inserted at array
while high > low
midpoint = floor((high + low) / 2)
...
high = array.length - 1. It will be negative if there is no element in the array. It is this kind of small little things that are tricky. You can have the program running correctly until you hit these kind of potholes. It was to the point that I decided to stop and wrote out the chart in the word file. Then it became clear. I literally deleted all the former work and start over new and finished in one day with the chart.

I finally finish to adding name, show certain range of names, delete name. I am sure the add_sort the last name is correct, I played with the first name , display and delete, so far, it works. But I want to play with it more to confirm. FINALLY, I can go back to my original Directory project and store all the names in a file so I can call them up the next time I run the program to do adding, delete. This is my final program:
C++:
#include <iostream>
#include <cstring>
#include <vector>
#include <iomanip>
using namespace std;
const static int nameLen = 25, phoneLen = 12;
struct Directory { char lastName[nameLen]; char firstName[nameLen];    char phone[phoneLen]; int element; };
std::vector<Directory>DirV;
Directory Dir;
void sort_firstName(int&);
void showRange(char[]);
void deleteName(int);
int main()
{
int newName, index = 0, compSize, numDelete;
char more, displayAll, choice;
char selName;
cout << " Welcome to the directory program. You can add name, contact informations and\n";
cout << " it will store in a file. You can display selected names and choose to delete\n";
cout << " anyone you want.\n\n";
do {
cout << " Please enter 'a' to add names, 's' to dispay complete list. 'r' to show \n";
cout << " range of names around a name. 'd' for delete a specific name. 'q' to quit.\n\n";
cout << " Please enter what you want to do:  "; cin >> choice; cout << "\n\n";
switch (choice)
{
case 'a': //Add new names and sort
{ do { cout << " Enter last name:  "; cin >> Dir.lastName;
//cout << " Enter first name:  "; cin >> Dir.firstName;
sort_firstName(newName);
cout << " \n\nDo you want to enter another name?  "; cin >> more;
}while (tolower(more) == 'y');
break;
};//End case 'a'
case 's': //Display entire list of names and info
{ index = 0;
if(DirV.size() > 0)
{ do { cout << "   Element #" << DirV[index].element <<
"]  is:   Last name: " << left << setw(10) << DirV[index].lastName <<
" first name: " << left << setw(10) << DirV[index].firstName << "\n\n";
index++;
} while (index < DirV.size()); break;
} else cout << " There is no name in the file.\n\n";
};//End case 's'
case 'r':
{ if (DirV.size() > 0)
{ cout << " Enter the first 2 character of the last name to search.";
cin >> selName; cout << "\n\n";
showRange(selName);//Display range before and after the name initials.
}else cout << " There is no name in the file.\n\n";
break;
};
case 'd'://Delete a name.
{ showRange(selName);
cout << " Enter the Element# of the left to be deleted: ";
cin >> numDelete;
deleteName(numDelete);
break;
};//End case 'd'
case 'q':{ cout << " Are you sure you want to quit? ";
cin >> choice; cout << "\n\n";};
default: cout << " Not a valid choice.\n";
}//End switch
} while(choice != tolower('q'));//End choice what to do

return 0;
}//End main()

{ int size, selCase;
DirV.push_back(Dir);//Push to next available element of DirV.
size = DirV.size();// DirV[midPt].element = midPt; newName = midPt;
int startPt = 0, endPt = size - 2, midPt = (endPt - startPt) / 2;
if((size == 1)||((strcmp(DirV[endPt].lastName, Dir.lastName) <= 0) & (size >= 2)))
selCase = 0;//Don't have to sort or anything, Dir is in last element already
//Case 0 for first entry when size = 1 OR when Dir.lastName is
// >= to last element of DirV(Dir.lastName >= DirV[endPt].lastName.
else
{if((strcmp(Dir.lastName, DirV[startPt].lastName) <= 0) && (size > 1))
selCase = 1;//If Dir smaller than DirV AND (size >1)
else
{ startPt = 0, endPt = size - 2; midPt = (endPt - startPt) / 2;
do {  if (strcmp(Dir.lastName, DirV[midPt].lastName) <= 0)
{ endPt = midPt; midPt = (startPt + endPt) / 2; }
else {startPt = midPt; midPt = (startPt + endPt) / 2; }
}while (startPt != midPt);
selCase = 2;
}//else selCase = 2
}//End if((strcmp(Dir.lastName, DirV[startPt].lastName) <= 0) && (size > 1))
switch(selCase)
//(size = 1)  AND  Dir.lastName => DirV[endPt].lastName
{case 0: { DirV[size - 1].element = size - 1; newName = size - 1; break;}
case 1://Dir.lastName <= DirV.lastName
{ int i;
for(i = 1; i <= (size - 1); i++)
{ DirV[size - i] = DirV[size - i - 1];
DirV[size - i].element = size - i;
DirV[size - i - 1].element = size - i - 1;
}//End for
DirV[size - i] = Dir; newName = size - i;
DirV[size - i].element = size - i;
break;
}//End case 1
case 2:
{ int j;
for(j = 1; j <= (size - endPt - 1); j++)
{ DirV[size - j] = DirV[size - j - 1];
DirV[size - j].element = size - j;
DirV[size - j - 1].element = size - j - 1;
}
DirV[size - j] = Dir; newName = size - j;
DirV[size - j].element = size - j;
break;
}//end case 2
}//End switch
}

void sort_firstName(int& newName)//DirV[newName] is the newly added name.
{   int beginLname = newName, endLname = newName;//start out all equal
int bubbleDown, bubbleUp;
Directory Temp;//Temporary structure variable to store structure Directory
Temp = DirV[newName];
bool doneUp = false, doneDown = false, moveUp = false;
bubbleUp = newName; bubbleDown = newName;
while ((bubbleUp > 0) & !doneUp)//Prevent bubbleUp going negative
{if((strcmp(DirV[newName].lastName, DirV[newName - 1].lastName) == 0)
& (strcmp(DirV[newName].firstName, DirV[newName - 1].firstName) < 0))
{DirV[newName] = DirV[newName - 1]; DirV[newName].element = newName;
DirV[newName - 1] = Temp; DirV[newName - 1].element = newName - 1;
newName--;bubbleUp--; moveUp = true;}
else (doneUp = true);
}//END while((bubbleUp > 0)& !doneUp)
if (moveUp == false)
{while ((bubbleDown < (DirV.size()-1)) & !doneDown)
{ if((strcmp(DirV[newName].lastName, DirV[newName + 1].lastName) == 0)
&(strcmp(DirV[newName].firstName, DirV[newName + 1].firstName) > 0))
{ DirV[newName] = DirV[newName + 1]; DirV[newName].element = newName;
DirV[newName + 1] = Temp; DirV[newName + 1].element = newName + 1;
newName++; bubbleDown++; }
else doneDown = true;
}//END while (decrement < bubbleUp)
}
}
void showRange(char selName)
{
int size = DirV.size(), stpt = 0, edpt = size - 1;
int mdpt = (stpt + edpt) / 2, index, comp;
do //search to within range using 2 characters in selName
{  comp = strncmp(selName, DirV[mdpt].lastName, 2);
if (comp != 0) {if(comp > 0){stpt = mdpt; mdpt = (stpt + edpt)/2;}
else {edpt = mdpt; mdpt = (stpt + edpt) / 2;}}
} while ((comp != 0) && (stpt + 2 <= edpt));//Matching DirV[mdpt]
for(index = -2; index <=3; index++)
{if(((mdpt + index) >= 0) && ((mdpt + index) <= (size - 1)))
{ cout << "   Element #" << DirV[mdpt + index].element <<
"]  is:   Last name: " << left << setw(10) << DirV[mdpt + index].lastName <<
" first name: " << left << setw(10) << DirV[mdpt + index].firstName << "\n\n";}
}//End for loop to display range of names if it is valid.
}//End showRange
void deleteName(int numDelete)
{   char sure;
int edpt = DirV.size() - 1;
cout << " Is this what you chose?\n";
cout << "   Element #" << DirV[numDelete].element <<
"]  is:   Last name: " << left << setw(10) << DirV[numDelete].lastName <<
" first name: " << left << setw(10) << DirV[numDelete].firstName << "\n\n";
cout << " Are you sure you want to delete this:\n\n"; cin >> sure;
if (tolower(sure) == 'y')
{
for(int i = 0; i < (edpt - numDelete); i++)
{ DirV[numDelete + i] = DirV[numDelete + i + 1];
DirV[numDelete + i].element = numDelete + i;}
DirV.pop_back();
}

}
It is getting very long. the next step on top of saving in file, I am going to break the program up using Class declaration and put a lot of these in the Specification and implementation file. I am even thinking about using two Specification files, one doing file management, the second one just add sort delete.

Thanks for all the help. It's educational. Working through the programs in the book is NOTHING like writing one of this program, one really find out what they actually learned. I had to kept going back to my notes, the book and online to find the correct ways to write the program.

Thanks

Last edited: