A car company manufactures three models of electrical cars: mx, my, mz. From time to time, the company wouldlike topromote thesemodelswithaparticularorder, for example,{“my”, “mx”, “mz”}. The promotion order would then be used to sort the company’sonline car inventory.Part AImplementafunctionto sort a givencar inventory based on a givenpromotion order. The following code skeleton gives the signature of the function.You must NOTchange the function signature; otherwise, all tests will automatically FAIL. class Assign1{public String[] sortCarInventory(String[] carInventory, String[] promotionOrder) {// Write your implementationhere.return carInventory;}}ArgumentscarInventoryand promotionOrderare String arrays.A test inputcould be:carInventory = {“mz”, “my”, “my”, “mx”, “mz”, “mx”, “my”, “mz”}promotionOrder = {“mz”, “mx”, “my”}Thesample outputreturned fromcalling sortCarInventory(…) with the above input would be:{“mz”, “mz”, “mz”, “mx”, “mx”, “my”, “my”, “my”}Assumptions:1)promotionOrder array always contains3distinctstrings in “mx”, “my”, and“mz”ofa particular order.2)carInventory array only containsstrings in “mx”, “my”, or “mz”.NotecarInventory couldcontain only one or two strings.Required:1)Your algorithm can at the mostiterate through the carInventory array for TWOpasses.2)Your algorithm mustrun with constant space, i.e.,O(1) space,meaningyour algorithm would need to perform sorting of the carInventory array in place by mutating the carInventory array.It can NOTuse any auxiliary spacethat is related to the input car inventory size.3)You can NOTuse the bucket–sorting algorithm.4)Using any Java data collection typeother than the fixed–size arrayis NOTallowed.5)Breaking either one of the requirements in 1), 2),3), or 4)would result ina 50%penalty toyour Assignment 1 grade.Hint:1)Use indices to trackandswap string elements in carInventoryaccording to promotionOrder.
Part BShowyour algorithm has O(n) time complexity(nis thesize of carInventory)and O(1) space complexity.You would first analyze your implementation logicto separate the constant and non–constant operations, then come up withfunctions for thetime complexity and the space complexity with respect tothe input array sizen, then simplify further to the O notations. ProgrammingLanguage and Environment•Programming Language: You must use Java Open JDK 1.8.xfor this assignment. This is available on edoras. •File Name: You must name your file Assign1.javafor it to run with the autograderon Gradescope. •Source Code Commenting: Your program should have appropriate comments at appropriate places.Refer to the best programming practices in the Syllabus on Canvas. Points will be deducted if yourcode does not have good comments.•Plagiarism Check: Points will be deducted if there is plagiarism found in your code. An automatedprogram structure comparison algorithm will be used to detect software plagiarism. An affidavit of academic honesty stating the program is written by your group will need to be submitted along with your submission of the code. Additional details are provided in the Turning In section
0 comments