Thread: Straight Insertion Sort function problem

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    27

    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.

  2. #2
    Registered User
    Join Date
    May 2008
    Posts
    27
    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

  3. #3
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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("&#37;s", &fileInName);
    fileInName is already a pointer, you shouldn't take its address.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  4. #4
    Registered User
    Join Date
    May 2008
    Posts
    27
    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

    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
    Last edited by StaticKyle; 05-11-2008 at 04:23 PM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    May 2008
    Posts
    27
    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.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 08-02-2008, 06:23 AM
  2. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  3. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  4. structure vs class
    By sana in forum C++ Programming
    Replies: 13
    Last Post: 12-02-2002, 07:18 AM
  5. qt help
    By Unregistered in forum Linux Programming
    Replies: 1
    Last Post: 04-20-2002, 09:51 AM