title: Implementing a quicksort algorithm for a vector of objects
body: <p>I was given an assignment to implement a quicksort algorithm into my C++ program. The homework is a part of series which started with objects and inheritance, but our lector didn't really explain quicksort to us.</p>
  
  <p>However, I can't really understand how do I select the vector of an object that is to be sorted and how do I set the low and high limits.</p>
  
  <p>Here is the code</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;string&gt;
  #include &lt;vector&gt;
  #include &lt;algorithm&gt;
  #include &lt;iterator&gt;
  #include &lt;functional&gt;
  
  using namespace std;
  
  template &lt;typename T&gt; T AskFor(string text) {
    cout &lt;&lt; text &lt;&lt; endl;
    T result;
    cin &gt;&gt; result;
    cin.clear();
    return result;
  }
  
  class Vehicle {
  public:
    Vehicle(string producer, string model, int year)
      : model(model) {
        setProducer(producer);
        setYear(year);
    }
  
    void output() {
      cout &lt;&lt; "  producer(vehicle): " &lt;&lt; producer &lt;&lt; endl;
      cout &lt;&lt; "  model(vehicle): " &lt;&lt; model &lt;&lt; endl;
      cout &lt;&lt; "  year(vehicle): " &lt;&lt; year &lt;&lt; endl;
    }
  
    void setProducer(const string producer) {
      if (isProducerValid(producer)) {
        this-&gt;producer = producer;
      }
    }
  
    string getProducer() const {
      return producer;
    }
  
    void setModel(const string model) {
      this-&gt;model = model;
    }
  
    string getModel() const {
      return model;
    }
  
    void setYear(const int year) {
      if (isYearValid(year)) {
        this-&gt;year = year;
      }
    }
  
    int getYear() const {
      return year;
    }
  
    static bool isYearValid(int year) {
      return year &gt;= 1950 &amp;&amp; year &lt;= 2016;
    }
  
    static bool isProducerValid(string producer) {
      static string PRODUCERS[] { "Toyota", "Audi", "BMW", "Mercedes" };
      return find(begin(PRODUCERS), end(PRODUCERS), producer) != end(PRODUCERS);
    }
  
  private:
    string producer;
    string model;
    int year;
  };
  
  class Vendor {
  public:
      Vendor(string v_name, string address, string phone, vector&lt;string&gt; delivery)
          : v_name(v_name),
          address(address),
          delivery(delivery) {
          setPhone(phone);
      }
  
      void setVendorName(const string v_name) {
          this-&gt;v_name = v_name;
      }
  
      string getVendorName() const {
          return v_name;
      }
  
      void setAddress(const string address) {
          this-&gt;address = address;
      }
  
      string getAddress() const {
          return address;
      }
  
      void setPhone(const string phone) {
          this-&gt;phone = phone;
      }
  
      string getPhone() const {
          return phone;
      }
  
      void setDelivery(const vector&lt;string&gt; delivery) {
          this-&gt;delivery = delivery;
      }
  
      vector&lt;string&gt; getDelivery() const {
          return delivery;
      }
  
      static bool isPhoneNumber(string phone) {
          if (phone.empty()) {
              return false;
          }
          return all_of(begin(phone), end(phone), isdigit);
      }
  
  private:
      string v_name;
      string address;
      string phone;
      vector&lt;string&gt; delivery;
  };
  
  class SparePart {
  public:
    SparePart(string id, string name, Vehicle* v, int price, int time_to_replace,
              bool is_new = true, string description = "", string manual = "")
      : id(id),
        name(name),
        vehicle(v),
        price(price),
        time_to_replace(time_to_replace),
        is_new(is_new),
        description(description),
        manual(manual) {}
  
    double replacementPrice() {
      return price + time_to_replace * 20;
    }
  
    int warranty() const {
      return is_new ? 36 : 3;
    }
  
    virtual void output() {
      cout &lt;&lt; "  ID: " &lt;&lt; id &lt;&lt; endl;
      cout &lt;&lt; "  name: " &lt;&lt; name &lt;&lt; endl;
      vehicle-&gt;output();
      if (is_new) cout &lt;&lt; "  new" &lt;&lt; endl; 
      else {
        cout &lt;&lt; "  recycled" &lt;&lt; endl;
      }
      cout &lt;&lt; "  description: " &lt;&lt; description &lt;&lt; endl;
      cout &lt;&lt; "  manual: " &lt;&lt; manual &lt;&lt; endl;
    }
  
    virtual ~SparePart() = 0;
  
    void setId(const string id) {
      this-&gt;id = id;
    }
  
    string getId() const {
      return id;
    }
  
    void setName(const string name) {
      this-&gt;name = name;
    }
  
    string getName() const {
      return name;
    }
  
    void setDescription(const string description) {
      this-&gt;description = description;
    }
  
    string getDescription() const {
      return description;
    }
  
    void setManual(const string manual) {
      this-&gt;manual = manual;
    }
  
    string getManual() const {
      return manual;
    }
  
    void setPrice(const double price) {
      this-&gt;price = price;
    }
  
    double getPrice() const {
      return price;
    }
  
    void setIsNew(const bool is_new) {
       this-&gt;is_new = is_new;
    }
  
    void setTimeToReplace(const int time_to_replace) {
      this-&gt;time_to_replace = time_to_replace;
    }
  
    int getTimeToReplace() const {
      return time_to_replace;
    }
  
  private:
    string id;
    string name;
    string description;
    string manual;
    double price;
    bool is_new;
    int time_to_replace;
    Vehicle* vehicle;
  };
  
  class AvailableSparePart : public SparePart {
  public:
    AvailableSparePart(string id, string name, Vehicle* v, int price, int time_to_replace,
      int quantity, string location, bool is_new = true, string description = "", string manual = "")
      : SparePart(id, name, v, price, time_to_replace, is_new, description, manual),
        quantity(quantity),
        location(location) {}
  
    double price() {
      return replacementPrice();
    }
  
    int time() {
      return getTimeToReplace();
    }
  
    void output() {
      cout &lt;&lt; "Available Spare Part" &lt;&lt; endl;
      SparePart::output();
      cout &lt;&lt; "  time: " &lt;&lt; time() &lt;&lt; endl;
      cout &lt;&lt; "  price: " &lt;&lt; price() &lt;&lt; endl;
    }
  
    void setQuantity(const int quantity) {
      this-&gt;quantity = quantity;
    }
  
    int getQuantity() const {
      return quantity;
    }
  
    void setLocation(const string location) {
      this-&gt;location = location;
    }
  
    string getLocation() const {
      return location;
    }
  
  private:
    int quantity;
    string location;
  };
  
  class ContractedSparePart : public SparePart {
  public:
    ContractedSparePart(string id, string name, Vehicle* v, int price, int time_to_replace,
      int delivery_time, double delivery_price, Vendor* vendor, bool is_new = true,
      string description = "", string manual = "")
      : SparePart(id, name, v, price, time_to_replace, is_new, description, manual),
        delivery_time(delivery_time),
        delivery_price(delivery_price),
        vendor(vendor) {}
  
    double price() {
      return replacementPrice();
    }
  
    int time() {
      return getTimeToReplace() + delivery_time;
    }
  
    void output() {
      cout &lt;&lt; "Contracted Spare Part" &lt;&lt; endl;
      SparePart::output();
      cout &lt;&lt; "  time: " &lt;&lt; time() &lt;&lt; endl;
      cout &lt;&lt; "  price: " &lt;&lt; price() &lt;&lt; endl;
    }
  
    void setDeliveryTime(const int delivery_time) {
      this-&gt;delivery_time = delivery_time;
    }
  
    int getDeliveryTime() const {
      return delivery_time;
    }
  
    void setDeliveryPrive(const double delivery_price) {
      this-&gt;delivery_price = delivery_price;
    }
  
    double getDeliveryPrice() const {
      return delivery_price;
    }
  
  private:
    Vendor* vendor;
    int delivery_time;
    double delivery_price;
  };
  
  enum class Action {
    ADD_VEHICLE,
    ADD_VENDOR,
    ADD_PART,
    ADD_PART_QUANTITY,
    LIST_PARTS,
    CALCULATE_COST,
    EXIT
  };
  
  Action menu() {
    string prompt = "Choose an option:\n"
                    "1. Add a new vehicle\n"
                    "2. Add a new vendor\n"
                    "3. Add a new spare part\n"
                    "4. Add part quantity\n"
                    "5. List spare parts\n"
                    "6. Calculate the cost of replacement\n"
                    "7. Exit";
    while (true) {
      switch (AskFor&lt;int&gt;(prompt)) {
      case 1:
        return Action::ADD_VEHICLE; break;
      case 2:
        return Action::ADD_VENDOR; break;
      case 3:
        return Action::ADD_PART; break;
      case 4: 
        return Action::ADD_PART_QUANTITY; break;
      case 5:
        return Action::LIST_PARTS; break;
      case 6:
        return Action::CALCULATE_COST; break;
      case 7:
        return Action::EXIT; break;
      default:
        cout &lt;&lt; "Please enter a number between 1 and 6" &lt;&lt; endl;
      }
    }
  }
  
  struct PartAndNumber {
    PartAndNumber(SparePart* part, int number)
      : part(part), number(number) {}
  
    SparePart* part;
    int number;
  };
  
  void add_vehicle(vector&lt;Vehicle*&gt;&amp; vehicles);
  void add_vendor(vector &lt; Vendor*&gt;&amp; vendors);
  void add_part(vector&lt;PartAndNumber*&gt;&amp; parts, const vector&lt;Vehicle*&gt;&amp; vehicles, const vector&lt;Vendor*&gt;&amp; vendors);
  void add_available_part(vector&lt;PartAndNumber*&gt;&amp; parts, Vehicle* vehicle);
  void add_contracted_part(vector&lt;PartAndNumber*&gt;&amp; parts, Vehicle* vehicle, const vector&lt;Vendor*&gt;&amp; vendors);
  void add_part_number(vector&lt;PartAndNumber*&gt;&amp; parts);
  void list_parts(const vector&lt;PartAndNumber*&gt;&amp; parts);
  void calculate_cost(const vector&lt;PartAndNumber*&gt;&amp; parts);
  
  int main() {
    vector&lt;Vehicle*&gt; vehicles;
    vector&lt;PartAndNumber*&gt; parts;
    vector&lt;Vendor*&gt; vendors;
  
    while (true) {
      Action action = menu();
      switch (action) {
      case Action::ADD_VEHICLE:
        add_vehicle(vehicles);
        break;
      case Action::ADD_VENDOR:
        add_vendor(vendors);
        break;
      case Action::ADD_PART:
        add_part(parts,vehicles,vendors);
        break;
      case Action::ADD_PART_QUANTITY:
        add_part_number(parts);
        break;
      case Action::LIST_PARTS:
        list_parts(parts);
        break;
      case Action::CALCULATE_COST:
        calculate_cost(parts);
        break;
      case Action::EXIT:
        return 0;
      }
    }
  }
  
  void add_vehicle(vector&lt;Vehicle*&gt;&amp; vehicles) {
    string producer;
    while (true) {
      producer = AskFor&lt;string&gt;("New vehicle (producer): ");
      if (Vehicle::isProducerValid(producer)) {
        break;
      }
      cout &lt;&lt; "Producer name is invalid. Try again." &lt;&lt; endl;
    }
  
    string model = AskFor&lt;string&gt;("New vehicle (model):");
  
    int year;
    while (true) {
      year = AskFor&lt;int&gt;("New vehicle (year):");
      if (Vehicle::isYearValid(year)) {
        break;
      }
      cout &lt;&lt; "Year is invalid. Try again." &lt;&lt; endl;
    }
  
    vehicles.push_back(new Vehicle(producer, model, year));
  
    cout &lt;&lt; "**************************************" &lt;&lt; endl;
    cout &lt;&lt; "The vehicle was added to the database" &lt;&lt; endl;
    cout &lt;&lt; "**************************************" &lt;&lt; endl;
  }
  
  void add_vendor(vector &lt;Vendor*&gt;&amp; vendors) {
    string v_name = AskFor&lt;string&gt;("New vendor (name): ");
    string address = AskFor&lt;string&gt;("New vendor (address): ");
    string phone;
  
    while (true) {
      phone = AskFor&lt;string&gt;("New vendor (phone):");
      if (Vendor::isPhoneNumber(phone)) {
        break;
      }
      else cout &lt;&lt; "Phone is invalid. Try again." &lt;&lt; endl;
    }
  
    vector&lt;string&gt; delivery;
    string del;
    do {
      cout &lt;&lt; "New vendor(delivery) or q to stop: ";
      if (del != "") {
        delivery.push_back(del);
      }
    } while ((cin &gt;&gt; del) &amp;&amp; del != "q");
  
    vendors.push_back(new Vendor(v_name, address, phone, delivery));
  
    cout &lt;&lt; "**************************************" &lt;&lt; endl;
    cout &lt;&lt; "The vendor was added to the database" &lt;&lt; endl;
    cout &lt;&lt; "**************************************" &lt;&lt; endl;
  }
  
  void add_part(vector&lt;PartAndNumber*&gt;&amp; parts, const vector&lt;Vehicle*&gt;&amp; vehicles, const vector&lt;Vendor*&gt;&amp; vendors) {
    string prompt = "Choose the type of spare part : Available(1) or Contracted(2); or q to exit : ";
    do {
      string model = AskFor&lt;string&gt;("Vehicle model: ");
  
      Vehicle* vehicle = nullptr;
      for (auto v : vehicles) {
        if (v-&gt;getModel() == model) {
          vehicle = v;
          break;
        }
      }
      if (vehicle == nullptr) {
        cout &lt;&lt; "Could not find a vehicle with this model." &lt;&lt; endl;
        return;
      }
  
      switch (AskFor&lt;char&gt;(prompt)) {
        case '1':
        add_available_part(parts, vehicle);
        return;
        break;
      case '2':
        add_contracted_part(parts, vehicle, vendors);
        return;
        break;
      case 'q':
        return;
        break;
      default:
        cout &lt;&lt; "No such option!";
      }
    } while (true);
  }
  
  void add_available_part(vector&lt;PartAndNumber*&gt;&amp; parts, Vehicle* vehicle) {
    string id = AskFor&lt;string&gt;("New spare part(id): ");
  
    for (auto p : parts) {
      if (p-&gt;part-&gt;getId() == id) {
        cout &lt;&lt; "Already available" &lt;&lt; endl;
        return;
      }
    }
  
    string name = AskFor&lt;string&gt;("New spare part(name): ");
    int price = AskFor&lt;int&gt;("New spare part(price): ");
    int time_to_replace = AskFor&lt;int&gt;("New spare part(time to replace): ");
    bool is_new = AskFor&lt;bool&gt;("New spare part(1 for new, 0 for recycled): ");
    string description = AskFor&lt;string&gt;("New spare part(description): ");
    string manual = AskFor&lt;string&gt;("New spare part(manual): ");
    int quantity = AskFor&lt;int&gt;("New spare part(quantity): ");
    string location = AskFor&lt;string&gt;("New spare part(location): ");
  
    auto part = new AvailableSparePart(id, name, vehicle, price, time_to_replace, quantity, location, is_new, description, manual);
    parts.push_back(new PartAndNumber(part, 0));
  
    cout &lt;&lt; "**************************************" &lt;&lt; endl;
    cout &lt;&lt; "The spare part was added to the database" &lt;&lt; endl;
    cout &lt;&lt; "**************************************" &lt;&lt; endl;
  
  }
  
  void add_contracted_part(vector&lt;PartAndNumber*&gt;&amp; parts, Vehicle* vehicle, const vector&lt;Vendor*&gt;&amp; vendors) {
    string id = AskFor&lt;string&gt;("New spare part(id): ");
  
    for (auto p : parts) {
      if (p-&gt;part-&gt;getId() == id) {
        cout &lt;&lt; "Already available" &lt;&lt; endl;
        return;
      }
    }
  
    string v_name = AskFor&lt;string&gt;("New spare part(vendor name): ");
  
    Vendor* vendor = nullptr;
    for (auto v : vendors) {
      if (v-&gt;getVendorName() == v_name) {
        vendor = v;
        break;
      }
    }
    if (vendor == nullptr) {
      cout &lt;&lt; "Could not find a vendor with this name." &lt;&lt; endl;
      return;
    }
  
    string name = AskFor&lt;string&gt;("New spare part(name): ");
    int price = AskFor&lt;int&gt;("New spare part(price): ");
    int time_to_replace = AskFor&lt;int&gt;("New spare part(time to replace): ");
    bool is_new = AskFor&lt;bool&gt;("New spare part(1 for new, 0 for recycled): ");
    string description = AskFor&lt;string&gt;("New spare part(description): ");
    string manual = AskFor&lt;string&gt;("New spare part(manual): ");
    int delivery_time = AskFor&lt;int&gt;("New spare part(delivery time): ");
    double delivery_price = AskFor&lt;double&gt;("New spare part(delivery price): ");
  
    auto part = new ContractedSparePart(id, name, vehicle, price, time_to_replace, delivery_time, delivery_price, vendor, is_new, description, manual);
    parts.push_back(new PartAndNumber(part, 0));
  
    cout &lt;&lt; "**************************************" &lt;&lt; endl;
    cout &lt;&lt; "The spare part was added to the database" &lt;&lt; endl;
    cout &lt;&lt; "**************************************" &lt;&lt; endl;
  }
  
  void add_part_number(vector&lt;PartAndNumber*&gt;&amp; parts) {
    string id = AskFor&lt;string&gt;("Spare part (id): ");
    for (auto p : parts) {
      if (p-&gt;part-&gt;getId() == id) {
        int parts_number = AskFor&lt;int&gt;("Number of parts: ");
        p-&gt;number = parts_number;
        cout &lt;&lt; "***************************************************" &lt;&lt; endl;
        cout &lt;&lt; "The number of spare parts was added to the database" &lt;&lt; endl;
        cout &lt;&lt; "***************************************************" &lt;&lt; endl;
        return;
      }
    }
    cout &lt;&lt; "A spare part with this ID is not available."; 
  }
  
  void list_parts(const vector&lt;PartAndNumber*&gt;&amp; parts) {
      double total_price = 0;
    for (auto p : parts) {
      p-&gt;part-&gt;output();
      cout &lt;&lt; endl;
      double total_current_price = p-&gt;part-&gt;replacementPrice() * p-&gt;part-&gt;getTimeToReplace();
      total_price = +total_current_price;
    }
    quicksort(parts, , parts.back);
    cout &lt;&lt; "The total price is" &lt;&lt; total_price &lt;&lt; endl;
  }
  
  void calculate_cost(const vector&lt;PartAndNumber*&gt;&amp; parts) {
    string id = AskFor&lt;string&gt;("Spare part(id): ");
    for (auto p : parts) {
      if (p-&gt;part-&gt;getId() == id) {
        cout &lt;&lt; "The cost for replacement is $" &lt;&lt; p-&gt;part-&gt;replacementPrice() &lt;&lt; endl;
        return;
      }
    }
    cout &lt;&lt; "A spare part with this ID is not available.";
  }
  
  SparePart::~SparePart() {}
  
  template &lt;class Comparable&gt;
  void quicksort(vector&lt;Comparable&gt;&amp; a)
  {
      quicksort(a, 0, a.size() - 1);
  }
  
  template &lt;class Comparable&gt;
  void quicksort(vector&lt;Comparable&gt;&amp; a, double low, double high)
  {
      if (low + 10 &gt; high) {
          insertionSort(a);
      }
      else {
          double middle = (low + high) / 2;
          if (a[middle] &lt; a[low]) swap(a[low], a[middle]);
          if (a[high] &lt; a[low]) swap(a[low], a[high]);
          if (a[high] &lt; a[middle]) swap(a[middle], a[high]);
          Comparable pivot = a[middle];
          swap(a[middle], a[high - 1]);
  
  
          int i, j;
          for (i = low, j = high - 1; ;) {
              while (a[++i] &lt; pivot) {}
              while (pivot &lt; a[--j]) {}
  
              if (i &lt; j) swap(a[i], a[j]);
              else break;
          }
          swap(a[i], a[high - 1]);
  
          quicksort(a, low, i - 1);
          quicksort(a, i + 1, high); 
      }
  }
  </code></pre>
  
  <p>Thank you for the help!</p>