Can someone help me with this problem? Just have to fill in where the code says run 1.

Finish the given program to implement and run bucket_sort. Starter code is provided. The program will read a file name and the read the data for the array from that file and run bucket sort on that array to sort it. It will print the array before and after sorting and the buckets.It will repeat these steps as long as the user wants to. Files:

1. This program consists of 3 files list.h, list.c - these should NOT be modified at all. and bucket_sort.c - You should write your code in this file, starting with run1(). Do NOT modify main(). The given files compile and run with Valgring with instructions

   compile: gcc -g bucket_sort_sol.c list.c -lm Run: valgrind --leak-check=full --show-leak-kinds=all ./a.out 

   However bucket_sort.c has only a placeholder in run1().
2. run_placeholder.txt - shows the program output when running with the bucket_sort.c as given (before you add your code).
3. run_student.txt - shows the program output AFTER a the student solution was added. Your final program should have this behavior.
4. a.out here is the program executable (creared on Ubuntu).
5. data1.txt, neg1.txt, dex1.txt - Data files. These are UNIX text files. They have the Unix end-of-line (EOL) terminator LF. Note that Windows has CR LF and Mac has CR. Thus do not mix files from different systems. Run your code on a Unix environment (omega, VM, or Ubuntu) and use the provided Unix files. To download them, open them (in browser) and RIGHT-CLICK -> "Save As". DO NOT copy paste in a local text file as that may be saved with your OS's EOL (CR or CR LF). See https://en.wikipedia.org/wiki/Newline). You may want to know that some editors (and a command in the Unix system) will allow you to save the file in a specific format if you need to make that change. For an example for reading from files see (on the Daily page) program examples1.c covered at the beginning of class. File format - The first number in the file is N (to be used as the size of the array) and on the next line there are N integers. E.g.

   6 9 1 7 5 8 2 

   means the size of the array will be 6 and the array will be {9,1,7,5,8,2}.

Use as number of buckets the size of the array. To compute the index for the bucket use the formula that adjusts the range based on the array data (provided in slides).For example for array {9,1,7,5,8,2} max=9, min=1, max-min+1=9, N=6 => number 7 goes to index=round_down(((7-1)/(9-1+1))*6) = round_down((6/9)*6) = round_down(4/3) = 1 = round_down(4) = 4. Use the formula as given here and make sure you get the SAME indexes as me. There is a particular bug/issue that you are very likely to have in your code and I want you to be aware of it and fix it so that it will always work (even in cases where you cannot change the order in which the operations are done). That is how the indexes shown are produced:

Bucketsort: min=1, max = 9, N=6 buckets arr[0]= 9, idx = 5 arr[1]= 1, idx = 0 arr[2]= 7, idx = 4 arr[3]= 5, idx = 2 arr[4]= 8, idx = 4 arr[5]= 2, idx = 0

bucket_sort.c

/* * Updated 2/25/2021 - Alexandra Stefan */ #include  #include  #include  #include "list.h" /* compile with -g to collect debugging info needed for Valgrind: gcc -g bucket_sort.c list.c run with Valgrind: valgrind --leak-check=full --show-leak-kinds=all ./a.out run without Valgrind: ./a.out */ void print_array(int arr[], int N); /* // recommended helper functions: // function to insert a new node in a sorted list. nodePT insert_sorted(nodePT L, nodePT newP); // function to sort an array sing bucket sort void bucket_sort(int arr[], int N) */ void print_array(int arr[], int N){ int j; printf(" array: "); for(j= 0; j 
list.h
 
/* * Updated 2/25/2021 - Alexandra Stefan */ #ifndef LIST_H #define LIST_H typedef struct node * nodePT; // POINTER to NODE (memory address of NODE) struct node { int data; struct node * next; // it is the same as: nodePT next; }; nodePT array_2_list(int arr[], int N); /* Creates a new node, that contains the value specified in the argument, * and that points to next_in. */ nodePT new_node(int value_in); /* Note that these functions may not have all the security checks. E.g. not all the functions reading and setting members of a node pointer, check that the node is not NULL */ /* -------- LIST */ // List implementation uses a DUMMY NODE void destroy_list(nodePT L); // Iterates through list and counts nodes. int compute_length(nodePT L); /* Inserts new_node to the specified list, at the position right after the node called "previous". Inserting at the begining (as new first node) is not handled by this function. */ void insert_node_after(nodePT previous, nodePT new_node); /* Inserts in list L, a the new node newP, after the node prev. If prev is NULL it means newP must be linked to the beginning of L It uses the list representation (L points to the first node with data) */ nodePT insert_node(nodePT L, nodePT prev, nodePT newP); /* Delete the node after the node "prev". Note that this is works on nodes. It does not matter how a list is represented. prev is just a node. */ void delete_node_after(nodePT prev); /* Deletes from list L, the node after prev. If prev is NULL it means that the first node of L must be deleted. It uses the list representation (L points to the first node with data). */ nodePT delete_node(nodePT L, nodePT prev); void print_list_vert(nodePT my_list); void print_list_horiz(nodePT my_list); // for each node prints both data field and the mem address of that node // (not the field next, but address of the node) void print_list_pointer(nodePT my_list); #endif /* LIST_H */ 
 
list.c
 
/* * Updated 03/08/2021 - Alexandra Stefan Fixed the i<2 to i #include  #include "list.h" // ------------- Node functions /* Creates a new link, that contains the value specified in the argument, * and that points to NULL. */ struct node * new_node(int value_in) { struct node * result = (struct node *) malloc(sizeof (struct node)); result->data = value_in; result->next = NULL; return result; } /* -------- LIST functions */ // List implementation uses a DUMMY NODE /* Deallocates memory for all nodes in the list and the list object itself. */ void destroy_list(nodePT L) { nodePT next; nodePT curr = L; while (curr != NULL) { next = curr->next; free(curr); curr = next; } } /* Inserts new_node after the node "prev". Note that this is works on nodes. It does not matter how a list is represented. prev is just a node. */ void insert_node_after(nodePT prev, nodePT newP) { if (prev == NULL) { printf(" Cannot insert after a NULL node. No action taken."); } else { newP->next = prev->next; prev->next = newP; } } /* Inserts in list L, a the new node newP, after the node prev. If prev is NULL it means newP must be linked to the beginning of L It uses the list representation (L points to the first node with data) */ nodePT insert_node(nodePT L, nodePT prev, nodePT newP){ if (prev == NULL) { // inserts at the begining of the list L newP->next = L; return newP; // return address of the new first node } else { insert_node_after(prev, newP); // does not affect the list head return L; } } /* Delete the node after the node "prev". Note that this is works on nodes. It does not matter how a list is represented. prev is just a node. */ void delete_node_after(nodePT prev) { if (prev == NULL) { printf(" Cannot delete after a NULL node. No action taken."); } else { nodePT toDel = prev->next; if (toDel != NULL){ prev->next = toDel->next; free(toDel); } } } /* Deletes from list L, the node after prev. If prev is NULL it means that the first node of L must be deleted. It uses the list representation (L points to the first node with data). */ nodePT delete_node(nodePT L, nodePT prev){ if (prev == NULL) { // delete the first node from L if (L==NULL) { // no node in the list. nothing to delete return NULL; } else { // delete the first node and return the address of the new first node nodePT newPtr = L->next; free(L); return newPtr; } } else { delete_node_after(prev); // does not affect the list head return L; } } // Swaps 2 nodes after prev. // If prev is NULL or not enough nodes for swapping, it does nothing. void swap_2_after(nodePT prev){ if (prev == NULL) { printf(" Cannot swap after a NULL node. No action taken."); } else { if ( (prev->next == NULL) || (prev->next->next == NULL) ) { printf(" Not enough nodes! "); return; } nodePT A = prev->next; // 1st node in the swap, code crashes if NULL nodePT B = prev->next->next; // 2nd node in the swap, code crashes if NUL nodePT C = B->next; // first nodes after the nodes to be swapped (A, B). Ok to be NULL. prev->next = B; //8 B->next = A; //9 A->next = C; //10 } } int compute_length(struct node * L) { if (L == NULL) { return 0; } int counter = 0; struct node * curr; for (curr = L; curr != NULL; curr = curr->next) { counter++; } return counter; } void print_list_vert(struct node * my_list) { if (my_list == NULL) { printf("  : list is NULL "); return; } int i = 0; struct node * curr; printf(" List items: "); for (i = 0, curr = my_list; (curr != NULL); curr = curr->next) { printf("item %d: %d ", i, curr->data); i++; } printf(" Length of above list = %d ", i); } void print_list_horiz(struct node * my_list) { if (my_list == NULL) { printf("  : List is NULL "); return; } int i = 0; struct node * curr; printf(" List items: "); for (i = 0, curr = my_list; (curr != NULL); curr = curr->next) { printf("%5d ", curr->data); i++; } printf(" Length of above list = %d ", i); } void print_list_pointer(struct node * my_list) { if (my_list == NULL) { printf("  : List is NULL "); return; } int i = 0; struct node * curr; printf(" List items: "); for (i = 0, curr = my_list; (curr != NULL); curr = curr->next) { printf("%-16d ", curr->data); i++; } printf(" List pointers: "); for (i = 0, curr = my_list; (curr != NULL); curr = curr->next) { printf("%-16p ", curr); i++; } printf(" Length of above list = %d ", i); } nodePT array_2_list(int arr[], int N) { if (N==0) { return NULL; // no data in the array. return empty list } int i; nodePT lastP, newP; nodePT L = new_node(arr[0]); // special case for first node printf(" N=%d ", N); lastP = L; // the last node of L is also the first node so far. for (i = 1; i < N; i++) { newP = new_node(arr[i]); lastP->next = newP; lastP = newP; } return L; } /* // Same code, but without the using the fct new_node nodePT array_2_list(int arr[], int N) { printf(" N = %d ", N); int j; nodePT lastP, newP; // special case for first node: create it and vase its pointer in L nodePT L = malloc(sizeof(struct node)); L->data = arr[0]; L->next = NULL; lastP = L; // it is also the last node in the list so lastP points to it for (j = 1; j < N; j++) { // create new node and write data in it newP = malloc(sizeof(struct node)); newP->data = arr[j]; newP->next = NULL; lastP->next = newP; // link the new node after the last node in the list, lastP lastP = newP; // this new node, is now the last node in the list so make // lastP point to it (i.e. copy in lastP the content of newP). } return L; } */
 
data1.txt
 
6 9 1 7 5 8 2
 
neg1.txt
 
5 7 -10 90 -4 50
 
dex1.txt
 
4 2147483646 2147483647 -2147483648 -2147483647