(Solved): A car company manufactures three models of electrical cars: mx, my, mz. From time to time, the com ...

A car company manufactures three models of electrical cars: mx, my, mz. From time to time, the company would like to promote these models with a particular order, for example, {"my", "mx", "mz"}. The promotion order would then be used to sort the company's online car inventory. Part A - Coding Implement a function to sort a given car inventory based on a given promotion order. Write your code in the given sortcar.cpp (see below): vector SortCar::sortCarInventory(vector carInventory, vector promotionOrder) { // Write your implementation here return car Inventory; } Arguments carInventory and promotionOrder are std::string vectors. A test input could be: vector carInventory {"mz", "my", "my", "mx", "mz", "mx", "my", "mz"} vector promotionOrder {"mz", "mx", "my"} The sample output returned from calling sortCarInventory(...) with the above input would be: {"mz", "mz", "mz", "mx", "mx", "my", "my", "my"} Assumptions: 1. promotionOrder vector always contains 3 distinct strings in "mx", "my", and "mz" of a particular order. 2. carInventory vector: possible car model strings contained in carInventory are "mx", "my", or "mz". Note carInventory may contain no string, one string, or more than one string. Algorithm Requirements: 1. Your algorithm must run with linear time complexity, i.e., O(n), with n being the size of input carInventory array. 2. Your algorithm can at the most iterate through the carInventory array for TWO passes. 3. Your algorithm must run with constant auxiliary space complexity, i.e., O(1), meaning your algorithm would need to perform sorting of the carInventory array in place by mutating the carInventory vector. It can NOT use any auxiliary space that is related to the input car inventory size. 4. You can NOT use the bucket-sorting algorithm. 5. You can ONLY use std::vector class, using any C++ STL class other than the std::vector is NOT allowed. 6. Breaking either one of the requirements in 1), 2), 3), 4), or 5) would result in a 50% penalty to your Assignment 1 grade. Hint: ? Use indices to track and swap string elements in carInventory according to promotion Order. Part B Complexity Analysis Show your algorithm has O(n) time complexity (n is the size of carInventory) and O(1) auxiliary space complexity. You would first analyze your implementation logic to separate the constant and non-constant operations relevant to the input carInventory array size, then come up with functions for the time complexity and the space complexity with respect to the input carInventory array size n, then simplify further to the O notations (note: Big O analysis considers the worst case scenarios).