-
-
Save master-elodin/7f29e0704b9f40c6c53cc42382a3ed3d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <string> | |
| #include <vector> | |
| using namespace std; | |
| static bool should_swap(string a, string b, int index) | |
| { | |
| int a_char = (int)tolower(a[index]); | |
| int b_char = (int)tolower(b[index]); | |
| return a_char > b_char || should_swap(a, b, index + 1); | |
| } | |
| static bool bsearch(vector <string> sorted_word_list, string search_term) | |
| { | |
| int length = sorted_word_list.size() - 1; | |
| int mid_index = length / 2; | |
| if(length == -1) | |
| { | |
| // base case: all elements have been removed from vector, so return false | |
| return(false); | |
| } | |
| else | |
| { | |
| if(sorted_word_list.at(mid_index) == search_term) | |
| { | |
| // search term found at midpoint, so return true | |
| return(true); | |
| } | |
| else if(should_swap(search_term, sorted_word_list.at(mid_index), 0)) | |
| { | |
| // search term was after the midpoint, so search again with that half of the vector | |
| sorted_word_list.erase(sorted_word_list.begin(), sorted_word_list.begin() + mid_index + 1); | |
| return(bsearch(sorted_word_list, search_term)); | |
| } | |
| else | |
| { | |
| // search term was before the midpoint, so search again with that half of the vector | |
| sorted_word_list.erase(sorted_word_list.begin() + mid_index, sorted_word_list.begin() + length + 1); | |
| return(bsearch(sorted_word_list, search_term)); | |
| } | |
| } | |
| } | |
| static vector <string> make_vector(int argc, char **argv) | |
| { | |
| // initialize empty vector | |
| vector <string> input; | |
| // add all relevant elements to vector | |
| for(int i = 1; i < argc; i++) | |
| { | |
| input.push_back(argv[i]); | |
| } | |
| return(input); | |
| } | |
| static vector <string> bubble(vector <string> word_list) | |
| { | |
| // get number of items in vector | |
| int input_size = word_list.size(); | |
| // sort vector | |
| for(int i = 0; i < input_size - 1; i++) | |
| { | |
| for(int j = 0; j < input_size - 1; j++) | |
| { | |
| if(should_swap(word_list.at(j), word_list.at(j+1), 0)) | |
| { | |
| word_list.at(j).swap(word_list.at(j+1)); | |
| } | |
| } | |
| } | |
| return(word_list); | |
| } | |
| static void print_vector(string sort_mode, vector <string> word_list, bool ascend) | |
| { | |
| // prints vector according to instructions | |
| int input_size = word_list.size(); | |
| if(sort_mode == "input: ") | |
| { | |
| cout << "input (" << (ascend ? "forward" : "backward") << ") : "; | |
| } | |
| else if(sort_mode == "bubble: ") | |
| { | |
| cout << "bubble (" << (ascend ? "forward" : "backward") << ") : "; | |
| } | |
| else | |
| { | |
| cout << "unknown call to print function" << endl; | |
| } | |
| if(ascend) | |
| { | |
| for(int i = 0; i < input_size; i++) | |
| { | |
| cout << word_list.at(i) + ", "; | |
| } | |
| cout << endl; | |
| } | |
| else | |
| { | |
| for(int i = input_size - 1; i >= 0; i--) | |
| { | |
| cout << word_list.at(i) + ", "; | |
| } | |
| cout << endl; | |
| } | |
| } | |
| int main(int argc, char **argv) | |
| { | |
| // initialize empty vector | |
| vector <string> input; | |
| cout << input.size() << endl; | |
| input = make_vector(argc, argv); | |
| // print vector using print_vector forwards and backwards | |
| print_vector("input: ", input, true); | |
| print_vector("input: ", input, false); | |
| // sort word input using bubble sort | |
| input = bubble(input); | |
| // print sorted vector using print_vector forwards and backwards | |
| print_vector("bubble: ", input, true); | |
| print_vector("bubble: ", input, false); | |
| // search vector | |
| string search_word; | |
| cout << "search: "; | |
| cin >> search_word; | |
| if(bsearch(input, search_word)) | |
| { | |
| cout << "found" << endl; | |
| } | |
| else | |
| { | |
| cout << "not found" << endl; | |
| } | |
| return(0); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment