you are required to implement the quick sort algorithm for sections of students, and a method...

  

Transcribed Image Text:

you are required to implement the quick sort algorithm for sections of students, and a method that verifies if a given tree array represents a heap. You are provided with two class files: Student.java and Section.java. For simplicity, each student has only two attributes: ID and GPA. A student can be presented as a string consisting of their ID and GPA. A student can be presented as a string consisting of their ID and GPA. For example, a student with an ID of 33251 and a GPA of 3.44 can be presented as "33251 (3.44)". Students are sorted in ascending order based on their GPA (students with a lower GPA are placed in front of those with a higher GPA). If two students have the same GPA, then the one with the lower ID should show up before the one with the higher ID. To compare two students, you need to compare their GPAS first, and then their IDs. Here are some examples: Student 33251(3.44) is smaller than student 42641 (3.95) because 3.44 is lower than 3.95. Student 19832(2.93) is greater than student 29831(2.87) because 2.93 is higher than 2.87. Student 29753(3.07) is greater than student 13528(3.07) because although their GPAs are identical, the first student has a higher ID than the second student. For the homework, you are provided with two additional files: Homework.java and TestHomework.java. You are required to complete the following methods in Homework: ☐int compares (Student s1, Student s2) This method takes two student objects and returns -1, 0, or 1 if s1 is smaller, equal to, or greater than s2, respectively. You need to compare their GPAs first and if they have the same GPA, then compare their IDs. void quickSort (Student[] studentArray, int first, int last) This method takes a student array as well as two indices. It sorts the students in the range specified by first and last with quick sort. It first calls the split method to partition the elements in the range into two subarrays, and sorts both subarrays recursively. It repeats this process until the entire array is sorted. int split (Student[] studentArray, int first, int last) This is a helper method for quick sort which takes a student array and two indices. It begins by selecting the first element in the student array as the pivot, and then moves elements so that everything in the left subarray is smaller than the pivot and everything on the right is greater than the pivot. The method returns the final index of the pivot. You are required to call the compares method to make comparisons between students. boolean isHeap(int[] A) This method takes an int array as the parameter and verifies if the elements saved in this array form a heap. You can assume that the array represents a complete binary tree so the shape property is already satisfied. You will need to verify that the elements meet the order property requirement for heaps. Return true if this is a heap, false otherwise. This method is separate from the above methods and has nothing to do with the Student or Section classes used by other methods. Test your code: You are provided with a test driver implemented in "TestHomework.java" (do not make any changes to this file!) so there is no need to write your own testing code. You are also given a data file "Sections.dat" that contains five pre-generated test sections as well as the sorted arrays. Each section has different numbers of students, so your program should work for any size section. (Note: you may need to move your data file for your IDE to be able to read it. For jGRASP, you can leave the data file in the same folder as your java files. For IntelliJ, you should place it in your project folder in which you see directories like out and src, etc.) Once you have completed the above classes, you can run the test. You should create a plain text file named "output.txt", copy and paste the output (if your code crashes or does not compile, copy and paste the error messages) this file and save it. Grading Rubric: Code does not compile: -10 Code compiles but crashes when executed: -5 ☐ Changes were made outside the required methods: -5 Has output file: 6 compares was correctly implemented: 5 ☐ quickSortRec was correctly implemented: 5 split was correctly implemented: 10 isHeap was correctly implemented: 10 ☐passes 8 test cases (3 pts each): 24 Sample Output: Test 1: quickSort() ==> [Passed] Original Section: [32336(2.68), 15739 (3.69), 34065 (2.98), 27165(3.31), 28179 (2.27), 11933(2.98), 35508 (3.34), 30209 (2.19), 24768 (2.58), 23015 (3.63), 37109 (3.1), 33453 (2.68), 15254 (3.31), 32899 (2.98)] Expected Section: [30209 (2.19), 28179(2.27), 24768 (2.58), 32336(2.68), 33453 (2.68), 11933(2.98), 32899(2.98), 34065 (2.98), 37109 (3.1), 15254 (3.31), 27165 (3.31), 35508 (3.34), 23015 (3.63), 15739 (3.69)] Yours: [30209 (2.19), 28179(2.27), 24768 (2.58), 32336(2.68), 33453(2.68), 11933 (2.98), 32899(2.98), 34065(2.98), 37109 (3.1), 15254(3.31), 27165(3.31), 35508 (3.34), 23015 (3.63), 15739(3.69)] Test 2: quickSort() ==> [Passed] Original Section: [13042 (3.13), 23394(2.65), 36600(2.18), 15075 (2.06),14479(3.13), 32135 (3.72), 22517(3.01), 17913(2.06)] Expected Section: [15075 (2.06), 17913(2.06), 36600 (2.18), 23394(2.65), 22517 (3.01), 13042 (3.13), 14479(3.13), 32135(3.72)] Yours: [15075 (2.06), 17913(2.06), 36600 (2.18), 23394 (2.65), 22517(3.01), 13042 (3.13), 14479 (3.13), 32135(3.72)] Test 7: isHeap ([50, 43, 27, 35, 44, 15, 22, 20]) ==> [Passed] Expected: false Yours: false Test 8: isHeap ([32, 27, 30, 19, 16, 21, 3, 10, 2, 4]) ==> [Passed] Expected: true Yours: true Total test cases: 8 Correct: 8 Wrong: 0 3/.../ 2 usages public class Homework { 3 J 3 1 // student comparison no usages public int compares (Student s1, Student s2) { } // TODO: implement this method return -1; // replace this statement with your own return // This is the wrapper method for quick sort // Do not make any changes to this method! 1 usage public void quickSort(Student[] studentArray) { quickSortRec (studentArray, first: 0, last: studentArray.length A 11 ^ V // This is the recursive helper method for quickSort that sorts the students based on their GPAS in // increasing order. // Note: If two students have the same GPA, then the one with lower student ID should show up in front of // the one with higher ID. 1 usage public void quickSortRec (Student[] studentArray, int first, int last) { // TODO: implement this method // This method splits a Student array into two sections, with all the elements less than the pivot in the // left section and all the elements greater than the pivot in the right section no usages public int split(Student[] studentArray, int first, int last) - 1); H H // This method splits a Student array into two sections, with all the elements less than the pivot in the // left section and all the elements greater than the pivot in the right section no usages public int split (Student[] studentArray, int first, int last) { } // TODO: implement this method @ } return -1; // replace this statement with your own return // This method takes an int array which represents a complete binary tree as // the parameter. It checks if the tree stored in the array is a heap. 3 usages public boolean isHeap (int[] A) { // TODO: implement this method return false; // replace this statement with your own return you are required to implement the quick sort algorithm for sections of students, and a method that verifies if a given tree array represents a heap. You are provided with two class files: Student.java and Section.java. For simplicity, each student has only two attributes: ID and GPA. A student can be presented as a string consisting of their ID and GPA. A student can be presented as a string consisting of their ID and GPA. For example, a student with an ID of 33251 and a GPA of 3.44 can be presented as "33251 (3.44)". Students are sorted in ascending order based on their GPA (students with a lower GPA are placed in front of those with a higher GPA). If two students have the same GPA, then the one with the lower ID should show up before the one with the higher ID. To compare two students, you need to compare their GPAS first, and then their IDs. Here are some examples: Student 33251(3.44) is smaller than student 42641 (3.95) because 3.44 is lower than 3.95. Student 19832(2.93) is greater than student 29831(2.87) because 2.93 is higher than 2.87. Student 29753(3.07) is greater than student 13528(3.07) because although their GPAs are identical, the first student has a higher ID than the second student. For the homework, you are provided with two additional files: Homework.java and TestHomework.java. You are required to complete the following methods in Homework: ☐int compares (Student s1, Student s2) This method takes two student objects and returns -1, 0, or 1 if s1 is smaller, equal to, or greater than s2, respectively. You need to compare their GPAs first and if they have the same GPA, then compare their IDs. void quickSort (Student[] studentArray, int first, int last) This method takes a student array as well as two indices. It sorts the students in the range specified by first and last with quick sort. It first calls the split method to partition the elements in the range into two subarrays, and sorts both subarrays recursively. It repeats this process until the entire array is sorted. int split (Student[] studentArray, int first, int last) This is a helper method for quick sort which takes a student array and two indices. It begins by selecting the first element in the student array as the pivot, and then moves elements so that everything in the left subarray is smaller than the pivot and everything on the right is greater than the pivot. The method returns the final index of the pivot. You are required to call the compares method to make comparisons between students. boolean isHeap(int[] A) This method takes an int array as the parameter and verifies if the elements saved in this array form a heap. You can assume that the array represents a complete binary tree so the shape property is already satisfied. You will need to verify that the elements meet the order property requirement for heaps. Return true if this is a heap, false otherwise. This method is separate from the above methods and has nothing to do with the Student or Section classes used by other methods. Test your code: You are provided with a test driver implemented in "TestHomework.java" (do not make any changes to this file!) so there is no need to write your own testing code. You are also given a data file "Sections.dat" that contains five pre-generated test sections as well as the sorted arrays. Each section has different numbers of students, so your program should work for any size section. (Note: you may need to move your data file for your IDE to be able to read it. For jGRASP, you can leave the data file in the same folder as your java files. For IntelliJ, you should place it in your project folder in which you see directories like out and src, etc.) Once you have completed the above classes, you can run the test. You should create a plain text file named "output.txt", copy and paste the output (if your code crashes or does not compile, copy and paste the error messages) this file and save it. Grading Rubric: Code does not compile: -10 Code compiles but crashes when executed: -5 ☐ Changes were made outside the required methods: -5 Has output file: 6 compares was correctly implemented: 5 ☐ quickSortRec was correctly implemented: 5 split was correctly implemented: 10 isHeap was correctly implemented: 10 ☐passes 8 test cases (3 pts each): 24 Sample Output: Test 1: quickSort() ==> [Passed] Original Section: [32336(2.68), 15739 (3.69), 34065 (2.98), 27165(3.31), 28179 (2.27), 11933(2.98), 35508 (3.34), 30209 (2.19), 24768 (2.58), 23015 (3.63), 37109 (3.1), 33453 (2.68), 15254 (3.31), 32899 (2.98)] Expected Section: [30209 (2.19), 28179(2.27), 24768 (2.58), 32336(2.68), 33453 (2.68), 11933(2.98), 32899(2.98), 34065 (2.98), 37109 (3.1), 15254 (3.31), 27165 (3.31), 35508 (3.34), 23015 (3.63), 15739 (3.69)] Yours: [30209 (2.19), 28179(2.27), 24768 (2.58), 32336(2.68), 33453(2.68), 11933 (2.98), 32899(2.98), 34065(2.98), 37109 (3.1), 15254(3.31), 27165(3.31), 35508 (3.34), 23015 (3.63), 15739(3.69)] Test 2: quickSort() ==> [Passed] Original Section: [13042 (3.13), 23394(2.65), 36600(2.18), 15075 (2.06),14479(3.13), 32135 (3.72), 22517(3.01), 17913(2.06)] Expected Section: [15075 (2.06), 17913(2.06), 36600 (2.18), 23394(2.65), 22517 (3.01), 13042 (3.13), 14479(3.13), 32135(3.72)] Yours: [15075 (2.06), 17913(2.06), 36600 (2.18), 23394 (2.65), 22517(3.01), 13042 (3.13), 14479 (3.13), 32135(3.72)] Test 7: isHeap ([50, 43, 27, 35, 44, 15, 22, 20]) ==> [Passed] Expected: false Yours: false Test 8: isHeap ([32, 27, 30, 19, 16, 21, 3, 10, 2, 4]) ==> [Passed] Expected: true Yours: true Total test cases: 8 Correct: 8 Wrong: 0 3/.../ 2 usages public class Homework { 3 J 3 1 // student comparison no usages public int compares (Student s1, Student s2) { } // TODO: implement this method return -1; // replace this statement with your own return // This is the wrapper method for quick sort // Do not make any changes to this method! 1 usage public void quickSort(Student[] studentArray) { quickSortRec (studentArray, first: 0, last: studentArray.length A 11 ^ V // This is the recursive helper method for quickSort that sorts the students based on their GPAS in // increasing order. // Note: If two students have the same GPA, then the one with lower student ID should show up in front of // the one with higher ID. 1 usage public void quickSortRec (Student[] studentArray, int first, int last) { // TODO: implement this method // This method splits a Student array into two sections, with all the elements less than the pivot in the // left section and all the elements greater than the pivot in the right section no usages public int split(Student[] studentArray, int first, int last) - 1); H H // This method splits a Student array into two sections, with all the elements less than the pivot in the // left section and all the elements greater than the pivot in the right section no usages public int split (Student[] studentArray, int first, int last) { } // TODO: implement this method @ } return -1; // replace this statement with your own return // This method takes an int array which represents a complete binary tree as // the parameter. It checks if the tree stored in the array is a heap. 3 usages public boolean isHeap (int[] A) { // TODO: implement this method return false; // replace this statement with your own return

Answer rating: 100% (QA)

Given is the programming for Java import javautilScanner public class QuickSort public static void m... View the full answer