Description
Concepts
- The object (element) to be sorted
- We take restaurant as an example since it usually has more than one attribute
- Quick sort applying the Multiple-Key sorting
- The order of the conditions in your if-else defines the priority of each key
Template (feel free to copy-and paste)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Restaurant {
public:
Restaurant(string name, int food_rating, int price, int service_rating, int distance):
name(name), food(food_rating), price(price), service(service_rating), distance(distance) {}
string name;
int food;
int price;
int service;
int distance;
};
class Sort {
public:
int partition(vector<Restaurant>& arr, int low, int high) {
auto pivot = arr[high];
int i = low - 1;
for(int j = low; j <= high - 1; ++j) {
if( /* Compare the key with the highest priority */ ) {
// Do the quicksort swapping
} else if( /* Comparison: second-highest priority key */ ) {
// Do the quicksort swapping
} else if( /* third-highest key */ ) {
// Do the quicksort swapping
} else { // Handle the "tie" situation
// Do the quicksort swapping
}
}
swap(arr[i+1], arr[high]);
return i + 1;
}
void quicksort(vector<Restaurant>& arr, int low, int high) {
if(low < high) {
int pivot = partition(arr, low, high);
quicksort(arr, low, pivot);
quicksort(arr, pivot+1, high);
}
}
};
int main(void) {
Sort sortbody;
string rest_name;
int food, price, service, dist;
vector<Restaurant> rest;
while(cin >> rest_name) {
cin >> food >> price >> service >> dist;
Restaurant new_rest(rest_name, food, price, service, dist);
rest.push_back(new_rest);
}
sortbody.quicksort(rest, 0, rest.size()-1);
for(int i = 0; i < rest.size(); ++i) {
cout << rest[i].name << endl;
}
return 0;
}
Input
You can utilize this or implement your own input:
McDonnald 3 3 2 1
KFC 4 3 2 3
Subway 4 4 3 2
Starbucks 4 5 4 2
BurgerKing 3 3 3 5
Output
See whether your sorting algorithm works as intended.