Straight Insertion Sort function problem

Hello again, I decided to post this in C++ because I'm actually doing my code in C++ now. Anyways, in another program that I was assigned (I'm sorry for posting homework, but I am just out of time to finish these and I have been stuck for several days on them.)

We were given this to work with:

Straight Insertion:

This algorithm sorts records R1, ... , RN in place with their keys in ascending order.
Record

Code:

---

for J in 2..N loop
        I := J -1;  K := KJ;  R := RJ;

        MoveLoop:
        loop
                if K >= KI then
                        RI+1 := R;  -- This is the final position.
                        exit MoveLoop;
                else
                        RI+1 := RI;  --Search higher.
                        I := I -1;
                        if I = 0 then
                                R1 := R;
                                exit MoveLoop;
                        end if;
                end if;
        end loop MoveLoop;

end loop;

---

Now, I understood how to convert this to a regular sort, but to get the grade, we had to not only implement this and use it as a sort on the our struct on the department part of the struct, but we had to also implement this as a pointer sort method.

Here is the instructions to clarify:

Implement the sort routine as a function sorting on the department field. The following data must be read from a file into an array. The array elements must be of type “struct.” Print the unsorted data to a report (in a file). Invoke the sort routine to sort the data into ascending lexicographic order by department. Print the sorted results to your file after returning to the main program. May I suggest using a subprogram which prints the contents of a struct element.

Further instructions:

After completing the option, implement the option sort as a pointer sort! Print the unsorted data to a report (in a file). Invoke the sort routine to sort the data into ascending lexicographic order by department using the “D” option sort. Print the sorted results to your file in the main program. Now invoke the pointer sort using the original raw data. Again, print the results in the report clearly marked as resulting from the pointer sort. You must use traditional subscript notation (e.g., “array[ J ]”) when accessing elements of an array.


And lastly, here is my code. I tried a few times to get the pointer sort to work, with no avail. I forgot to mention that all of this is supposed to be in its own file or be its own library, so any help with doing that would be appreciated too. (I tried and it gave me over 100 errors when compiling.)

Code:

---

#include <iostream>
#include <iomanip>
#include <string.h>
#include <fstream>

using namespace std;

void insertionsort(struct eRec r[],int n,char fileOutName[]);
void pointinsertionsort(struct eRec r[], int n,char fileOutName[]);
void print(struct eRec p1[], int n, char fileOutName[], int choice);

struct eRec
{
        char g[20];
        char s[20];
        char d[20];
        float pr;
        char e[16];
};

int main()
{
        char fileInName[25];
        char fileOutName[25];
        char response;
        int filecount = 0;  //The number of lines in the file.

        FILE *inFile;              // Logical input file name in program.
        FILE *outFile;                          // Logical output file name in program.

        //Gets the file name of input and then checks to see if it exists
        printf("What is the name of the input file (max 25 characters)? ");
        scanf("%s", &fileInName);
        inFile = fopen(fileInName,  "r");
        if (inFile == NULL)
        {
                printf("This file does not exist.");
                exit(1);
        }

        //Gets the file out name and then checks to see if it already exists
        //If so then it asks for you to choose whether or not to override.
        printf("What is the name of the output file (max 25 characters)?");
        scanf("%s", &fileOutName);
        if((outFile = fopen(fileOutName, "r" )) != NULL )
        {
                printf("\nA file by the name %s exists.\n", fileOutName);
                printf("Do you wish to overwrite (Y or N): ");
                //Skip <cr> in buffer with "%*c", i.e., one character
                scanf("%*c %c", &response);

                if( (response == 'n') || (response == 'N') )
                { // should close file first
                        printf("\nProgram aborted to prevent overwirte!");
                        exit(1);
                }
        }
        outFile = fopen( fileOutName, "wt" );
        if( outFile == NULL )
        {
                printf("Could not create the output file! Program terminating.");
                exit(1);
        }


        struct eRec sort[20];
        char givname[20];
        char surname[20];
        char department[20];
        char eyecolor[20];
        float payrate;
        int c = 0;
        printf("GivenName \t Surname \t Department \t PayRate \t EyeColor \n");
        while((fscanf(inFile,"%s%s%s%f%s ", surname, givname, department, &payrate, eyecolor))!= EOF)
        {
                strcpy(sort[c].g, givname);
                strcpy(sort[c].s, surname);
                strcpy(sort[c].d, department);
                sort[c].pr = payrate;
                strcpy(sort[c].e, eyecolor);
                printf("%s \t %s \t %s \t %f \t %s\n", sort[c].g, sort[c].s, sort[c].d, sort[c].pr, sort[c].e);
                c++;
        }

        print(sort, c, fileOutName, 1);
        insertionsort(sort,c,fileOutName);
        pointinsertionsort(sort,c,fileOutName);
        fclose(inFile);
        fclose(outFile);

return 0;
}

void print(struct eRec t[], int n, char fileOutName[], int choice)
{
    FILE *outFile;
        outFile = fopen(fileOutName,"a+");
        if (choice == 1)
        {
                        fprintf(outFile, "Unsorted.\n");
        }
        if (choice == 2)
        {
                        fprintf(outFile, "\nSorted.\n");
        }
        if (choice == 3)
        {
                        fprintf(outFile, "\nSorted with pointers!\n");
        }
        fprintf(outFile, "GivenName \t Surname \t Department \t PayRate \t EyeColor \n");
        for(int i = 0; i < n; i++)
        {
                fprintf(outFile,"%s\t %s\t %s\t %f\t %s\t\n", t[i].g, t[i].s, t[i].d, t[i].pr, t[i].e);
        }
        fclose(outFile);
}

void insertionsort(struct eRec r[], int n, char fileoutname[])
{
        int i;
    int result;
        int looper;
        struct eRec temp;
        struct eRec m;

          for(int j = 1; j < n; j++)
          {
                m = r[j];
            i = j - 1;
            temp = r[j];
              looper = 1;
                while(looper != 0)
                {
                if((strcmp(m.d, r[i].d)) >= 0)
                {
                    r[i + 1] = temp;
                    looper = 0;
                    }
            else
            {
                                r[i + 1] = r[i];
                                i--;
                                if(i == 0)
                                {
                                        r[0] = temp;
                                        looper = 0;
                        }
                        }
            }

        }
        for(int l = 0; l < n; l++)
        {
                printf("%d. %s %s, %s\n", l+1, r[l].g, r[l].s, r[l].d);
    }
        print(r,n,fileoutname,2);
}

void pointinsertionsort(struct eRec r[], int n, char fileoutname[])
{
    int i;
        int temp2;
        int max;
        int pntr[n];
        for(int t = 0; t < n; t++)
        {
                pntr[t] = t;
        }
        for(int t = (n -1); t > 0; t--)
        {
                max = 0;
                for(int j = 1; j <= t; j++)
                {
                        if ( strcmp(r[pntr[j]].d, r[pntr[max]].d) > 0)
                        {
                                max = j;
                        }
                }
                temp2 = pntr[max];
                pntr[max] = pntr[t];
                pntr[t] = temp2;
        }
          //for(int j = 1; j < n; j++)
          //{
        //        m = r[j];
        //          i = j - 1;
        //          temp2 = pntr[j];
          //          looper = 1;
        //          while(looper != 0)
        //          {
    //            temp = r[pntr[i]];
        //              if((strcmp(m.d, temp.d))>0)
        //              {
    //                pntr[i+1] = temp2;
    //                looper = 0;
        //            }
    //        else
    //        {
        //                        pntr[i + 1] = pntr[i];
        //                        i--;
        //                        if(i == 0)
        //                        {
        //                                pntr[0] = temp2;
        //                                looper = 0;
    //                    }
        //                }
        //        }
    //}
        for(int p = 0; p < n; p++)
        {
                printf("%d. Pointer: %d\n", p+1, pntr[p]);
    }
        print(r,n,fileoutname,3);
}

---

Thank you, any suggestions or help on how to fix this is greatly appreciated.

Oh yeah, the input file:

Code:

---

Smith        Sam                Computer_Services        18.24                Blue
Jones        Mary                Accounting                8.96                Green
Jones        Tom                Sales                        16.27                Hazel
Cameron        Bob                Computer_Services        22.01                Blue
Diaz        Alvarado        Sales                        19.26                Blue
Cooper        Peter                Management                6.72                Steel
Dick        Moby                Water_Sports                53.34                Brown
Bayles        Aaron                Hacker                        78.33                Hazel

---

What exactly do you mean by pointer sort (e.g sorting an array of pointers into the original data)?

As to this code you have a couple of problems inputting strings:

Code:

---

scanf("%s", &fileInName);

---

fileInName is already a pointer, you shouldn't take its address.

Heh, thanks, that was pointed out to me by another person in another one of my codes and I just forgot to change it.

Thank you :D

I think it is just by using an array of ints, but I'm not quite sure... Which is kinda why I'm asking.

As I am reading more of the notes, I found this which might help explain it:

Code:

---

Traditional sorts work by moving records.

            Unsorted                      Sorted
0        Joe        15                0        Adam        12
1        Sam        20                1        Betty        34
2        Betty        34                2        Joe        15
3        Adam        12                3        Sam        20
4        Sara        25                4        Sara        25

A pointer sort logically re-arranges records via pointers as opposed to physically moving records.

Unsorted
        Pt                                       
0        0                0        Joe        15       
1        1                1        Sam        20       
2        2                2        Betty        34       
3        3                3        Adam        12       
4        4                4        Sara        25       

Sorted                                                                    Sort Pass
        Pt                                                        1        2        3        4
0        3                0        Joe        15                        0        0        2        3
1        2                1        Sam        20                        1        3        3        2
2        0                2        Betty        34                        2        2        0        0
3        1                3        Adam        12                        3        1        1        1
4        4                4        Sara        25                        4        4        4        4

---

Please indent your code properly and replace tabs with the corrrect number of spaces before posting.

If you've been asked to sort pointers then you should probably sort pointers. Sure the sort passes are shown using indexes, but that's probably only because it's easier for you to follow the example.
Once you have your data in an array you need to start by making an array of pointers to those items.
Then make a printing routine that uses your array of pointers. Call it with the unsorted pointer array to see that it outputs things in the original order.
Next write the sorting algorithm.
Then call your printing routine again with the array of pointers that now points to the items in sorted order.
The only difference then between sorting an array directly and sorting an array of pointers is that the comparison will involve a dereference, and the item type being sorted is of course a pointer-to-item instead, that's it.

Your current pointinsertionsort function uses Selection Sort, not Insertion Sort.

your insertionsort appears to correctly perform the Insertion Sort algorithm, though it could be simplified somewhat. It's doing too much however. It should only be responsible for sorting an array of pointers, not printing them out or anything else. That's the work of other functions. Try writing a simple list of high level tasks to be performed and make each one of those its own function.

g, s, d, pr and e are not suitable variable names. You should definitely get marks off for using those names in your struct.
You should not be declaring seperate arrays for each of those things either. You can scanf directly into the variables within the struct. Or at worst if you read into temporary variables first, then those temporaries need not be an array.

I don't see any guarantees that the file doesn't contain more than 20 records. If you can't find anything in your assignment that says you can assume there are never more than 20 then you need to use dynamic memory allocation.

You need to learn about the switch statement. A switch should be used instead of may "if (choce == x)" statements.

btw, apart from the "using namespace std;" this appears to be entirely C code, not C++.

Your code has a buffer overrun vulnerability as mentioned. If they're not teaching how to prevent such problems then they damn well should be.

Well, thank you for the harsh help and I wish that I could do all of that, and had all of the time, but my program is due in 4 hours, and I had to make the thing work for the situation that came up.

The biggest problem I see with me trying to do all this, and especially for the harsh criticism is to note that I have only taken one class on C and C++. And this class was taken with several others (19 hours actually) and I barely had time to listen in class.

Lets see, I honestly have barely any knowledge when it comes to using pointers in C/C++, but, the only reason that I have the names so short in the struct is because I wanted it to be easier on me to write it out quickly. Usually they would be givenname, surname, department, payrate, eyecolor and all of that.

Meh, I'm just being defensive, so I'm sorry. After this semester, I'm going to work on some of the code to see if I can get it running at a higher standard and fully. Thanks for the comments and pointers to where I need to try and fix my code.

Now, my little excuses aside, I would like to try and learn to make this better, if some people are willing. My normal code isn't at this low of a level, but I make exceptions when I'm stuck in a sticky time situation.

Not trying to be harsh, just giving definitive and decisive criticism.:)
I know it's hard starting out, and deadlines make it harder still. I wouldn't expect you to fix every issue, but the more that's pointed out, the more you can choose to change whatever is easiest for you to improve on. The grader probably wont be going any easier on your coding though I'm afraid.
Overall I'd say you've done a good job.

Actually I gotta go sleep now, good luck.