### Algorithm review

Hey guys,
I'm coming back to study cpp after few years of stopping.
Tried to implement a sorting algorithm on std::vector,
Kindly have a look at the solution, tell me how bad it is.
Any feed back is appreciated.
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162`` ``````int binSearch(vector vec, int number, int smallest, int largest) { int vec_ptr = ((largest - smallest) / 2) + smallest; if (number == vec[vec_ptr]) return vec_ptr; if (number > vec[vec_ptr]) { if (smallest == vec_ptr && largest == (vec_ptr + 1)) return largest; smallest = vec_ptr; return binSearch(vec, number, smallest, largest); } if (number < vec[vec_ptr]) { if (smallest == vec_ptr && largest == (vec_ptr + 1)) return smallest; largest = vec_ptr; return binSearch(vec, number, smallest, largest); } } vector pushOnIndex(vector vec, int index, int number) { vector cpy_vec; for (int i = 0; i < index; i++) cpy_vec.push_back(vec[i]); cpy_vec.push_back(number); for (int i = index; i < vec.size(); i++) cpy_vec.push_back(vec[i]); return cpy_vec; } vector sortVec(vector vec){ vector sorted_vec; sorted_vec.push_back(vec[0]); for (int i = 1; i < vec.size(); i++) { if (vec[i] > sorted_vec[sorted_vec.size() - 1]) { sorted_vec.push_back(vec[i]); continue; } if (vec[i] < sorted_vec[0]) { sorted_vec = pushOnIndex(sorted_vec, 0, vec[i]); continue; } int pos = binSearch(sorted_vec, vec[i], 0, sorted_vec.size() - 1); sorted_vec = pushOnIndex(sorted_vec, pos, vec[i]); } return sorted_vec; } int main() { vector nums = {66, 190, 45, -123, -445, 990, -1, 0, 30001, -999, 22, 23, 25, 1, 12, 32, 52, 72}; vector sorted_vec = sortVec(nums); }``````
Line 23: You're passing vec by value. Then you proceed to make another copy.
There's no need to make a second copy when the first vector is already a copy.
Copying a vector can be an expensive operation depending on the size of the vector.

Line 34: You're passing vec by value again and returning sorted vec. It makes the most sense to pass vec by reference in both cases. If you want to sort a vector, there is seldom a reason to maintain the original vector in it's original order.

I assume you know there is a library function that can sort vectors.
https://cplusplus.com/reference/algorithm/sort/?kw=sort

edit:
Here's a classic bubble sort:
 ``1234567891011121314151617181920212223`` ``````#include #include using namespace std; void sortVec(vector & vec) { for (int i = 0; i < vec.size() - 1; ++i) for (int j = i+1; j < vec.size(); ++j) { if (vec[i] > vec[j]) swap(vec[i], vec[j]); } } int main() { vector nums = { 66, 190, 45, -123, -445, 990, -1, 0, 30001, -999, 22, 23, 25, 1, 12, 32, 52, 72 }; sortVec(nums); for (auto num : nums) cout << num << " "; cout << endl; return 0; }``````
Last edited on
 Tried to implement a sorting algorithm on std::vector

Prefer using what the C++ stdlib provides instead of writing your own.

https://en.cppreference.com/w/cpp/algorithm/sort

I understand writing your own functionality as a learning experience, though.
How does binSearch() indicate to the caller if a value is not found?

smallest, largest, index etc should be type size_t and not type int.

If .size() is used, then the variable type should also be size_t (or ptrdiff_t) and not int.

For binSearch() consider:

 ``1234567891011121314`` ``````ptrdiff_t binarySearch(const std::vector& arr, int x, size_t low, size_t high) { if (low > high) return -1; const auto mid { ((high - low) / 2) + low }; if (x == arr[mid]) return mid; if (x > arr[mid]) return binarySearch(arr, x, mid + 1, high); return binarySearch(arr, x, low, mid - 1); }``````

 ``12`` ``````for (int i = 0; i < index; i++) cpy_vec.push_back(vec[i]);``````

See std::copy_n() and std::back_inserter()
https://cplusplus.com/reference/algorithm/copy_n/
https://cplusplus.com/reference/iterator/back_inserter/

 ``12345678910111213`` ``````#include #include #include #include int main() { const std::vector v { 1, 2, 3, 4, 5, 6 }; std::vector v1; std::copy_n(v.begin(), 3, std::back_inserter(v1)); std::copy(v1.begin(), v1.end(), std::ostream_iterator(std::cout, " ")); }``````

Last edited on
how much abuse do you want :) I mean, you are trying to learn, and getting back into the language, and those are GOOD things if its what you want or need to do.

but alongside/similar to the above comments:
- your time would be better spent doing the exact same program by using the c++ library calls that do the same things. Once you can do it using those tools, THEN if you want to understand how to write a library type function, you can take a crack at it. But you will do a LOT more using of the built in tools than crafting your own: using the c++ ones is a critical language skill, crafting your own library type routines is not.

- your code is married to one kind of vector, that of type <int>. Your sort won't even work on a vector of unsigned int, int64, char, or other things. It has very low reusability.

people can find many, many problems with your (and mine, and almost anyone's) code esp if its 'immature' (haven't spent the time on it for industrial quality). Don't take it too hard ... to write a perfected sort that works on all types of input using the best algorithms and cleanly written is likely a months long effort; may even dip into threading and other topics.
Last edited on
Thanks a lot guys, much appreciated.
If you are filling a known size vector with sequential values you could use std::iota, and leverage copying a vector to a new vector using the container's overloaded constructor.
 ``123456789101112131415161718192021222324252627282930`` ``````#include #include #include // for std::iota int main() { // let's create a sized vector, contents default initialized std::vector v (9); // let use std::iota to fill the vector with sequentially increasing values // https://en.cppreference.com/w/cpp/algorithm/iota std::iota(v.begin(), v.end(), -4); for ( const auto& itr : v ) { std::cout << itr << ' '; } std::cout << '\n'; // you could use std::copy to make a copy of your vector // better to use the functionality of the vector's constructor std::vector v2 (v); // let's confirm the vector and its contents were copied. for ( const auto& itr : v2 ) { std::cout << itr << ' '; } std::cout << '\n'; }``````

http://coliru.stacked-crooked.com/a/ce405f6c19ed01ef

Please note none of this requires anything later than C++11.
Using C23++ std::ranges::to so that the vector can be const (can't be if using std::iota):

 ``123456789101112131415161718`` ``````#include #include #include #include #include int main() { const std::vector v { std::ranges::to(std::ranges::iota_view{1, 7}) }; std::ranges::copy(v, std::ostream_iterator(std::cout, " ")); std::cout << '\n'; const auto v2 { v }; std::cout << '\n'; std::ranges::copy(v2, std::ostream_iterator(std::cout, " ")); std::cout << '\n'; }``````

or for reversed sequential:

 `` `` ``const std::vector v { std::ranges::to(std::ranges::iota_view{1, 7} | std::views::reverse) };``

Last edited on