Created
April 27, 2017 00:16
-
-
Save sax1johno/88e3f064b390610c2f2fe5743e4a7cb4 to your computer and use it in GitHub Desktop.
Binary Search, Linear Search, and Bubble Sort implementations from 04/26/2017
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 <vector> | |
#include <iostream> | |
int linearSearch(std::vector<int> &vectorToSearch, int itemToTest); | |
void bubbleSort(std::vector<int> &vectorToSort); | |
int binarySearch(std::vector<int> &vectorToSearch, int numToTest); | |
int main() { | |
std::vector<int> myVector; | |
myVector.push_back(5); | |
myVector.push_back(20); | |
myVector.push_back(18); | |
myVector.push_back(3); | |
myVector.push_back(9); | |
myVector.push_back(4); | |
myVector.push_back(11); | |
myVector.push_back(30); | |
myVector.push_back(2); | |
myVector.push_back(8); | |
myVector.push_back(14); | |
myVector.push_back(22); | |
myVector.push_back(24); | |
int idx = linearSearch(myVector, 14); // This should return the index of where the item was found | |
std::cout << "Found item at index " << idx << std::endl; | |
std::cout << "Before sorting: " << std::endl; | |
for (int num : myVector) { | |
std::cout << num << " "; | |
} | |
bubbleSort(myVector); | |
std::cout << std::endl << "After sorting: " << std::endl; | |
for (int num : myVector) { | |
std::cout << num << " "; | |
} | |
idx = linearSearch(myVector, 14); // This should return the index of where the item was found | |
std::cout << "Found item at index " << idx << std::endl; | |
int x = 1; | |
std::cin >> x; | |
idx = binarySearch(myVector, 4); // Should return the index where the item was found | |
std::cout << "Using binary search, we found 4 at index " << idx << std::endl; | |
idx = linearSearch(myVector, 4); // This should return the index of where the item was found | |
std::cout << "Using linear search, we found 4 at index " << idx << std::endl; | |
idx = binarySearch(myVector, 28); // Should return the index where the item was found | |
std::cout << "Using binary search, we found 28 at index " << idx << std::endl; | |
idx = linearSearch(myVector, 28); // This should return the index of where the item was found | |
std::cout << "Using linear search, we found 28 at index " << idx << std::endl; | |
//x = 5 / x; | |
//std::cout << x << std::endl; | |
//std::cin >> x; | |
} | |
void bubbleSort(std::vector<int> &vectorToSort) { | |
// Save off the size so we don't have to compute it every time. | |
int size = vectorToSort.size(); | |
// Loop through the list twice to do bubble sort. | |
// The inner loop swaps items in the vector if needs be. | |
// The outer loop makes sure we run the swaps enough times to actually be sorted. | |
for (int i = 0; i < size; i++) { | |
for (int j = 0; j < size - 1; j++) { | |
// Do we need to swap? | |
if (vectorToSort[j] > vectorToSort[j + 1]) { | |
// Yes, we do. | |
int temp = vectorToSort[j + 1]; | |
vectorToSort[j + 1] = vectorToSort[j]; | |
vectorToSort[j] = temp; | |
} | |
} | |
} | |
} | |
// This should return the index of where the item was found | |
int linearSearch(std::vector<int> &myVect, int numToTest) { | |
// loop through the vector | |
for (int i = 0; i < myVect.size(); i++) { | |
// if we found the item we were looking for | |
if (myVect[i] == numToTest) { | |
// return the index | |
return i; | |
} | |
} | |
// If we looped through the entire vector and never returned, we never found the item. | |
// so return -1 as an error condition. | |
return -1; | |
} | |
int binarySearch(std::vector<int> &myVect, int numToTest) { | |
//if (myVect.size() < 1) { | |
// return -1; | |
//} | |
bool done = false; | |
int start = 0; | |
int end = myVect.size(); | |
while (!done) { | |
// Get midpoint. | |
int midpoint = floor((start + end / 2)); | |
// Special case ending (base case). | |
if (end - start <= 2) { | |
// check the remaining two items | |
if (myVect[end] == numToTest) return end; | |
if (myVect[start] == numToTest) return start; | |
// if numToTest doesn't match either one, we never found the item. | |
return -1; | |
} | |
// Check value at midpoint against numToTest. | |
if (myVect[midpoint] == numToTest) { | |
// if midpoint == numToTest return midpoint. | |
return midpoint; | |
} | |
else if (myVect[midpoint] < numToTest) { | |
// else if midpoint < numToTest | |
// set start to midpoint | |
start = midpoint; | |
} | |
else { | |
// else | |
// set end to midpoint | |
end = midpoint; | |
} | |
} | |
return -1; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment