-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathSortingAlgorithms.cpp
291 lines (269 loc) · 18.9 KB
/
SortingAlgorithms.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <emscripten/bind.h>
using namespace emscripten;
using std::vector;
using std::string;
using std::swap;
// Restaurant names come from https://namesbee.com/restaurant-names/
class Restaurant
{
private:
public:
int rating;
float distance;
string cuisine;
string name;
float simScore;
};
// passes in the data set, the searched values, and the preferred way of sorting (distanceOrRating is true if distance is preferred)
void setSimScores(vector<Restaurant>& dataSet, float prefDistance, int prefRating, string prefCuisine, bool distanceOrRating)
{
// sets sim scores with a preference towards distance
if(distanceOrRating)
{
for(int i = 0; i < dataSet.size(); i++) {
int simScoreCuisine = -1;
int ratingFit = 1;
if(dataSet[i].cuisine == prefCuisine | prefCuisine == "Any")
{
simScoreCuisine = 1;
}
if(dataSet[i].rating < prefRating & prefRating != 0) {
ratingFit = (dataSet[i].rating - prefRating) / 5.0;
}
dataSet[i].simScore = (.75 * ((prefDistance - dataSet[i].distance) / prefDistance)) + ratingFit + simScoreCuisine;
}
}
// sets sim scores with a preference towards rating
else
{
for(int i = 0; i < dataSet.size(); i++)
{
int simScoreCuisine = -1;
int disFit = 1;
if(dataSet[i].cuisine == prefCuisine | prefCuisine == "Any")
{
simScoreCuisine = 1;
}
if (dataSet[i].distance > prefDistance & prefDistance != 10000) {
disFit = (prefDistance - dataSet[i].distance) / prefDistance;
}
dataSet[i].simScore = disFit + (.75 * ((dataSet[i].rating - prefRating) / 5.0)) + (1 * simScoreCuisine);
}
}
}
// function that finds values that are lower and higher than the pivot and swaps them accordingly
int partition(vector<Restaurant> &array, int low, int high)
{
float pivot = array[low].simScore;
int up = low - 1;
int down = high + 1;
while(true)
{
do {
up++;
} while (array[up].simScore > pivot);
do {
down--;
} while (array[down].simScore < pivot);
if (up >= down)
return down;
swap(array[up], array[down]);
}
}
// randomize pivot
int partition_r(vector<Restaurant> &array, int low, int high) {
srand(time(NULL));
int random = low + rand() % (high-low);
swap(array[random], array[low]);
return partition(array, low, high);
}
// call with the dataset, 0, and the size - 1
void QuickSort(vector<Restaurant> &array, int low, int high)
{
if(low >= high)
{
return;
}
if(low < high)
{
int pivot = partition_r(array, low, high);
QuickSort(array, low, pivot);
QuickSort(array, pivot + 1, high);
}
}
void Merge(std::vector<Restaurant>& array, int start, int mid, int end){
int leftCount = mid - start + 1;
int rightCount = end - mid;
std::vector<Restaurant> left;
std::vector<Restaurant> right;
//Left and right subarrays
for(int i = 0; i < leftCount; i++){
left.push_back(array[start + i]);
}
for(int i = 0; i < rightCount; i++){
right.push_back(array[mid + 1 +i]);
}
int leftIndex = 0;
int rightIndex = 0;
int arrIndex = start;
//Initial merge instructions
while(leftIndex < leftCount && rightIndex < rightCount){
if(left[leftIndex].simScore > right[rightIndex].simScore){
swap(array[arrIndex], left[leftIndex]);
leftIndex++;
}
else{
swap(array[arrIndex], right[rightIndex]);
rightIndex++;
}
arrIndex++;
}
//Copy leftover values
while(leftIndex < leftCount){
swap(array[arrIndex], left[leftIndex]);
leftIndex++;
arrIndex++;
}
while(rightIndex < rightCount){
swap(array[arrIndex], right[rightIndex]);
rightIndex++;
arrIndex++;
}
}
void MergeSort(std::vector<Restaurant>& array, int start, int end){
if(start < end) {
int mid = (end + start) / 2;
MergeSort(array, start, mid);
MergeSort(array, mid + 1, end);
Merge(array, start, mid, end);
}
}
// function to create a vector with the specific number of restaurant objects
vector<Restaurant> makeData(int numbOfRestaurant)
{
vector<Restaurant> dataSet;
// possible cuisines and names
vector<string> cuisineTypes {"American", "French", "Mexican", "Italian", "Japanese", "Indian", "Chinese","Ethiopian", "Lebanese", "Kosher", "Thai", "Spanish", "Cuban"};
vector<string> restaurantNames {"Benno Restaurant", "Benno Restaurant", "Big Moe's Diner" , "Pizza Italian Heart", "Smokey's Texas Grill",
"USA Bakery", "Papa John's", "Karachi Silver Spoon", "Pizzeria Cafe", "Jockey", "Oriole", "Zahav",
"Gramercy Tavern", "Le Bernardin", "Alinea", "Daniel", "Manresa", "Lahaina Grill", "Canlis", "Le Coucou",
"Le Diplomate", "The Modern", "Momofuku Ko", "Vernick Food & Drink", "Monteverde Restaurant & Pastificio",
"Girl & The Goat", "Next Restaurant", "Eleven Madison Park", "Marea", "Boka", "Gotham", "Benu", "Saison",
"Talula's Garden", "Blue Hill", "Charleston", "Le Pigeon", "Highlands Bar & Grill", "Vetri Cucina",
"Gabriel Kreuther","Del Posto", "Coquine", "Kokkari Estiatorio", "Quince", "Acquerello", "Blue Smoke",
"Bohemian","Carmine's Italian Restaurant","Club A Steakhouse", "Your Aesthetic","Alphabet Eatery",
"Let's Ambush","Anna Bella", "Arrow Spoon", "The Taste and Beyond", "Blind Faith","Blue Valley",
"Breakfast at any Time", "Cast Diners", "Cheesy Love", "Chef First", "The Eclectic Taste","Chef Parade",
"Chicken and Spices", "Chili Flora", "Chipotle Meal", "Classic Corn in", "Crazy Cut","Crazy Grill",
"The Lakhani", "The Hebbet", "Seven Spices", "Hot Gear", "Hollo Follo", "Hill Crest","Heart Beats food",
"Harley Food Center", "Grebb", "Brewhouse", "Dine Fine", "Perfect Place","Pointe Restaurant", "The Spice",
"Gourmet Meal", "Tavern", "Fresh Ingredients", "Umami Burger","Amsterdam", "Finest Dining", "Tofino",
"Pasta Beach", "French Gourmet", "Oasis Cafe", "Mediterranean Seafood", "Sensory Experience", "Fish and Chips",
"Phuc Noodle", "Captiva Island", "Perfect Dish", "Pinch Kitchen", "Pita Pan", "Plane Grill", "Planet of the Grapes",
"Plumed Horse", "PM Fish & Steak House", "Poke Life", "Project Juice", "Quick Eats", "Rainforest Cafe",
"Ready Restaurants", "Red Dragon", "Red Tablecloth", "Revelry Bistro", "Rice House", "Rich Table", "Rocco's Cafe",
"Rock and Roll cafe", "Rolls", "Salted Grill", "Fred's Tacos Corner", "Fatty Fingers", "Eat Bite", "Desi Eatery",
"Dagny's Delight", "Curry Out", "Crew Cafe", "The Elephant and the Mouse", "The Lazy Lemur", "Naan Better", "The Hungrella",
"Hurry Curry", "Mad Munch", "MadWings", "Chophouse", "Porridge Cafe", "Homemade Bagels", "Strip Steak", "Burger King",
"Steam Plant", "Pho Shizzle", "Salty Squid", "Sea Spice", "Shaker + Spear", "Skillet Counter", "Sloppy Eats",
"Soul Food", "Spice Villa", "Spicy Dragon", "Street Delights", "Sugar Blast", "Sunrise Cafe", "Taco Mayo",
"Tall Oaks Cafe", "Bones Restaurant", "ATOMIX", "Cafe Monarch", "Charleston Grill", "Restaurant Gordon Ramsay",
"Spoon and Stable", "Melisse Restaurant", "Jean-Georges", "Rose's Luxury", "Frasca Food and Wine", "FIG",
"The Old Fashioned", "The Table", "Mama's Fish House", "COI", "GW Fins", "Open Zest", "Palm Crown",
"The New Montana Restaurant", "Sharp Knives", "Snack Bar Express", "Street Stuff", "Sweet Munchies",
"Suede Dinner", "Vintage Burgers", "Wave's", "West Coast Chef", "Tribal Fiesta", "Chipotle Mexican Grill",
"Banana Leaf", "Spear Smoque", "Thai Me Up", "Thai The Knot", "The Back Room", "The Breakfast Story",
"The Cafe Baraco", "The Capital Grille", "The Chef in the Hat","The Dinning Room", "The Fishery",
"The Food Place", "The French Gourmet", "The Golden Stool", "Les Nomades", "The Original", "CRUST",
"Gordon Ramsay Hell's Kitchen", "LEON", "Aliada", "Patina Restaurant", "Cliff House", "Lawry's The Prime Rib",
"Bryant Park Grill", "Rudy & Paco Restaurant and Bar", "Gibsons Bar & Steakhouse", "Atelier Crenn",
"Orchids at Palm Court", "The Compound Restaurant", "Masa", "Crisp", "The Aviary", "Tasty Elements",
"Starbelly", "Pier 23", "Lord Stanley", "Gemini", "Catch 35", "Blue Plate", "Burger & Beer Joint",
"CRUST", "Full Moon", "Grubstake", "Hot & Crusty", "A Salt & Battery", "Chart House", "Double Decker",
"Foxsister", "Halls Chophouse", "King and Queen", "Lazy Bear", "Mad for Chicken", "Americano", "Buccan",
"Blue Hill At Stone Barns", "Boston's Restaurant & Sports Bar", "Cured", "Johnny Rockets", "The Root Cafe",
"Lantern", "Handle", "Chin Chin Las Vegas", "Next Door American Eatery","V's Italiano Ristorante",
"S. Egg Brunch Restaurant North Scottsdale", "Eat Restaurant", "The Breakfast Bar", "The Chef",
"La Lucha", "Chimney Park Restaurant & Bar", "Chez Panisse", "Vie Restaurant", "Pizzeria Delfina Mission",
"The Sea Spice", "German Food", "The Ledbury", "Stateside", "The Capital Grille", "The Egg & Us", "The Local Eatery",
"The River Seafood", "Townsend", "Wise Sons", "Zero Restaurant", "Bean Around", "Chewy Balls", "Double Knot",
"Fog Harbor", "Hereford Grill", "Like No Udder", "Munch Box", "North Beach", "Queenstown Public House",
"True Food Kitchen", "The Local House", "Stomach Clinic", "Sundown at Granada", "HG Sply Co.", "Toulouse Knox Street",
"Taverna", "Al Biernat's", "Up On Knox", "Thai Thai Restaurant", "Pecan Lodge", "The Capital Grille",
"The Polo Bar", "The Red Door", "The Rosebud", "The Saddle River Inn", "The Slanted Door", "The Spanish Kitchen",
"Tin Roof", "Top of the Market", "Townsend", "Udupi", "Unique Meals", "Urban Remedy", "Vegans Come Here",
"Vessel Restaurant", "Vietnamese Street Food", "Walton's Restaurant", "Water Grill", "Wok This Way",
"Xin Chao Vietnamese Restaurant", "Your Cook", "Columbia Restaurant Celebration", "CityGrocery",
"The Proper Restaurant & Bar", "Moto", "ROKU", "The Mill Restaurant", "Turn", "Heart Attack Grill",
"Top NotchHamburgers", "Honest Restaurant Lowell", "Proof Restaurant", "Kura Revolving Sushi Bar",
"Di Fara Pizza", "Valor Glencoe", "All Set Restaurant & Bar", "Sister", "Chipotle", "Story Restaurant",
"Thrive", "The Pantry Restaurant", "The Federal", "Tom's Sushi House", "Le Parfait", "Bright", "Sabor",
"Dinner by Heston Blumenthal", "Scully St James's", "Angler","Dobar", "Kinship", "Caviar Bar",
"Fishing with Dynamite", "Conch it Up Soul Food", "California Pizza Kitchen", "BeaverChoice", "Pita Pan",
"Sears Fine Food", "The Bear & The Monarch", "The Patio", "Zareen's", "Sushi Tomi", "Cascal",
"Crepevine Restaurants", "Eureka!", "Paul Martin's America", "Napoletana Pizzeria", "Le Petit Bistro",
"ViVe Sol", "SAJJ Mediterranean", "Ding Tai Fung", "El Mercado Restaurant", "MELT", "Dozens Restaurant",
"BREWED", "The Standard", "Nusr-Et Steakhouse Dallas", "Steve & Cookie's By the Bay", "The Oven",
"Carlos' Bistro", "AVANT Restaurant", "The Taste", "The Peak", "Social", "Nathan's Famous", "The Local",
"Fine Burgers & Drinks", "The Place", "Zona Italian Restaurant", "Start Restaurant", "Sizzler",
"Los Padres Mexican Food", "The Point Restaurant", "The Point Bar & Grill", "A&W", "The Loop Minneapolis",
"Fin Japanese Cuisine", "Around the Corner", "Lawry's Restaurants, Inc.", "Benihana", "Hanna's",
"Casa Bonita", "Curbside Burgers", "The Dallas World Aquarium", "Denny's", "The Roof", "Cinco Mexican Cantina",
"Companion Bakery", "Breakfast Nook", "The Inn at Little Washington", "Local Beer, Patio and Kitchen",
"The Original Mexican Restaurant","St Francis Winery & Vineyards", "The MARK", "Cinemark Hollywood Movies 20",
"US Foods CHEF'STORE", "Darden Restaurants", "All Elite Food", "Alpine Meadow", "At Your Service", "Bacon Babe Burgers",
"Bankers Hill", "Barefoot Bar & Grill", "Basic Kneads Pizza", "BBQ Night", "Beanburgers", "Before the Bistro","Big Bills",
"Big Chef", "Big Mountain", "Bistro","Bite Me Sandwiches", "Bite-Sized", "Blue Collar", "Blue Mermaid", "Boogie bites",
"Bread And Butter", "Breakfast House", "Brick House Stackhouse", "Brothers Railroad Inn", "Burger & Beer Joint",
"Burger UK London", "Burma Love", "Cafe21", "Cafe Coyote", "Cafe Provence", "California Pizza Kitchen", "Cat Heads BBQ",
"Catch of the Day", "Cheesy", "Chewy Balls", "Chicago", "Chilango", "Chops N' Drinks", "Circus", "City View Restaurant",
"Coffee and Cake", "Corner", "Cosmopolitan Restaurant", "Crabby Dick's", "Crown Crest", "Crusty Chicken", "Curated Cuisine",
"Curry", "Daily Grill", "Dedicated Dining", "Delightful Dining", "Detox Kitchen", "Dine Dime", "Dining Delight",
"Dining Room Ready", "Dinner by HestonBlumenthal", "Double Knot", "Drink And Dive", "East Meets West", "Eat Your Heart Out",
"El Charro of Iola", "Emerald Grill", "Everest", "Famous Lunch", "Fiddler's Green", "Fine Dining Delivered", "Food O'clock",
"Firefly Resort", "Five Oceans", "Flame On", "Fog City", "Food Addict", "Fishing with Dynamite", "Food Court", "Food Formula",
"Food Town", "FoodiesUnites", "Foodstuff", "Formal Performance", "Full Belly Belles", "Garage Kitchen + Bar", "Gem Cafe",
"Geronimo", "Golden Era", "Goldfinch Tavern", "Good Morning", "King and Queen", "King Lee's", "Mad Chicken", "Mad for Chicken",
"Fury Kitchen", "Koi's Sushi's", "Last Time", "Le Parfait", "Lettuce Eat", "Lionfish", "Little London", "Long Eel",
"Lord Stanley", "Love Shack Foods", "Lunch Chow", "Malabar", "Marina Kitchen", "Masa Grill Kabob", "Maude", "Meat U There",
"Mess Hall", "Blue Mermaid", "Duke's Seafood", "Hillstone", "Cat Heads BBQ", "Eatmore Fried Chicken", "Great Eastern",
"BarefootBar & Grill", "Little Sheep", "Metro Cafe", "Ocean Star", "Peking Inn", "Single Shot", "Thai Me Up",
"Harbor City", "Metropolitan Grill", "Rice House", "The House", "The Kitchen", "The Mission", "Tin Roof", "Barley Mash",
"Coaster Saloon","Waterfront", "The Old Spaghetti", "Tanta", "Sotto", "Revelry Bistro", "Next", "Kum Den Bar",
"Goldfinch Tavern", "Zum Schweizerhaus", "Spice Bazaar", "Urchig", "Alpenclub", "Stand", "Ski Lodge Engelberg", "McDongalds Borger"};
// creates restaurant object's with randomized data and inserts it into the vector
for(int i = 0; i < numbOfRestaurant; i++)
{
Restaurant newRestaurant = Restaurant();
newRestaurant.rating = rand() % 6;
float temp = rand() % 100 ;
temp = temp / 100;
newRestaurant.distance = rand() % 49 + temp;
int cuisineLocation = rand() % cuisineTypes.size();
newRestaurant.cuisine = cuisineTypes.at(cuisineLocation);
int nameLocation = rand() % restaurantNames.size();
newRestaurant.name = restaurantNames.at(nameLocation);
dataSet.push_back(newRestaurant);
}
return dataSet;
}
EMSCRIPTEN_BINDINGS(my_module) {
class_<Restaurant>("Restaurant")
.constructor<>()
.property("rating",&Restaurant::rating)
.property("distance", &Restaurant::distance)
.property("cuisine", &Restaurant::cuisine)
.property("name", &Restaurant::name)
.property("simScore", &Restaurant::simScore)
;
function("setSimScores", &setSimScores);
function("makeData", &makeData);
function("QuickSort", &QuickSort);
function("MergeSort", &MergeSort);
register_vector<Restaurant>("vector<Restaurant>");
register_vector<string>("vector<string>");
}