Data files: names30.txt,names_all.txt- names_all.txt contains both female and male names and thus a name used both as male and female will show up twice. That is fine. You do not need to do anything...

Data files:Write a program named insertion_sort.c.
It reads a file with names, loads it and sorts them in increasing order using insertion sort.
This program will be "memory-efficient" by allocating only exactly as much space is needed to store each string. Do NOT use something like:char table[6267][101];orchar table[30][101];as it wastes space.
The program will print how much such memory it allocated.
It will implement a more generic version of insertion sort. The algorithm is the same, but the comparison function used for strings should NOT be a hardcoded strcmp, but it should be passed as an argument to the insertion_sort function. You can read more about passing functions as parameters in C and also see the funct_param.c file above.
Steps and requirements:

  1. Ask the user to enter a filename and load store that data in a dynamically allocated array of strings. See the above document showing how data should be stored.

  2. The space to store each string MUST be allocated dynamically (e.g. malloc or calloc). The space to store the pointers to these locations can be allocated either dynamically (malloc/calloc) or as an array of N pointers (e.g. data[N]).

  3. (8 points) Your program must NOT have any memory errors when ran with Valgrind on omega. See on the Code page the Valgrind section for examples of how to run the code with Valgrind and what the Valgrind report should look like.
    If your program has only "unconditional jump" errors AND it HAS NO memory leaks/memory lost, invalid read or invalid write then you can get 4 out of the 8 points. If you have any memory leak, memory lost, invalid read or invalid write you get none of the 8 points here.
    I recommend you run VAlgrind after each main step to catch errors early on. That way as you add new code you know the old one is safe and if any new errors appear, should be easier to find and fix.

  4. The files are expected to have the format:

    • one name per line. (No spaces, or tabs)

    • a name can have at most 100 characters in it. To read the name from the file it is ok to use a char array of size 101 (e.g. char buffer[101]) to read a line from the file.

    • There is no upper limit on the number of possible lines in the file.

    • the file name will be at most 100 characters (including the extension). To read the file name it is ok to use a char array of size 101 here to read the filename from the user (e.g. char buffer[101]).

  5. Since you do not know how many words will be in the file in total you must read it twice: first to count the number of lines (anything works here), and then again to read the words from it. When reading the words from the file I recommend using fscanf for each word. (Using strtok is an overkill and with other methods you may need 'clean' the word - e.g. remove \n from the end).

  6. Keep track of the total number of Bytes needed to store the names. For each word you should count both how many Bytes you malloc/calloc for the name and the 8Bytes for the pointer to that name. You should get the EXACT number as I have in the sample run.
    E.g. I got 441B for 30 names as follows: 441B = 30pointers*8B + 201chars*1B. The 201 chars (that were malloc'ed) were counted by the program and 30 is the number of words in the file.

  7. When you MOVE the data as part of sorting, move/copy the pointers not the strings, (DO NOT use strcpy).See the tables in the above document showing how data should be stored.

  8. Note that it is ok to use strcpy to copy the names from the buffer into the actual space in the program (e.g. the box for Mike). Just do not use it in any way when sorting.

  9. Implement a generic version of insertion sort, by passing the comparison function as an argument. The comparison functions should have the same signature as strcmp in C so that you can use pass strcmp as the argument. strcmp signature:

    int strcmp(const char *leftStr, const char *rightStr );
    The comparison functions you implement should use the same conventions as strcmp: :

    • if leftStr compares less than rightStr the function returns a strictly negative number

    • if leftStr compares equal to the rightStr the function returns 0

    • if leftStr compares greater than the rightStr the function returns a strictly positive number

  10. Implement the following 3 different comparison functions:

    1. comp_length- compares by string length. A shorter name compares less than a longer name. E.g. Sam ≤ Marcy, Sam == Joe

    2. comp_mixt- complex comparison function for strings. When comparing two strings, it compares them first by string length. If the lengths are different, it uses that. If the lengths are equal, it compares the strings using regular string comparison (with the strcmp from C) and returns the result of that comparison.
      E.g. Sorted names would be:Joe, Sam, Mark, Tico, Alice, Alexandra

      You want to write a function that takes 2 strings and returns something negative, positive or 0. See an example of what the function should return for these pairs of strings:
      ("Sam", "Alice")  returns a negative value  (b.c. "Sam"<"alice" i.e.="" "sam"="" is="" shorter="" than="" "alice")="" ("alice",="" "sam")="" returns="" a="" positive="" value="" (b.c.="" "alice"="">"Sam" i.e. "Alice" is longer than "Sam") ("Sam", "Tom")    returns a negative value  (b.c. "Sam" < "tom"="" i.e.="" they="" have="" the="" same="" length="" but=""><"tom" by="" strcmp)="" ("tom",="" "sam")="" returns="" a="" positive="" value="" (b.c.="" "tom"=""> "Sam" i.e. they have the same length but "Tom">"Sam" by strcmp) ("Tom", "Tom")    returns 0  (b.c. "Tom" == "Sam" i.e. they have the same length and "Tom"=="Sam" by strcmp)

    3. comp_greater- Use the definition below

      int comp_greater(const char *leftStr, const char *rightStr ){ return -strcmp(leftStr, rightStr); }

  11. See below part of my main function calling insertion sort with the above methods as arguments:

    printf("\n Data is loaded"); printf("\n Allocated space for storing the data: %7d B ( %d char and %d pointers)",size_in_bytes, allocated, n); printf("\n Pointer size: %d Bytes\n", sizeof(void*)); printf("\nOriginal data: \n"); print_data(table, n); printf("\n-------- compare by LENGTH only --------------\n"); insertion_sort_ptr(table, n, comp_length); print_data(table, n); printf("\n-------- compare by strcmp --------------\n"); insertion_sort_ptr(table, n, strcmp); // here strcmp is the one from the C-library (NOT implemented by me) print_data(table, n); printf("\n-------- compare by GREATER --------------\n"); insertion_sort_ptr(table, n, comp_greater); print_data(table, n); printf("\n-------- compare by LENGTH and lexicografic --------------\n"); insertion_sort_ptr(table, n, comp_mixt); print_data(table, n); free_table(table, n);

Feb 22, 2021

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here