C++

Forum

 
Algorithm review

Mishalit (4)
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.
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
 
int binSearch(vector<int> 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<int> pushOnIndex(vector<int> vec, int index, int number)
{
    vector<int> 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<int> sortVec(vector<int> vec){
    vector<int> 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<int> nums = {66, 190, 45, -123, -445, 990, -1, 0, 30001, -999, 22, 23, 25, 1, 12, 32, 52, 72};
    vector<int> sorted_vec = sortVec(nums);
}
AbstractionAnon (6954)
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <vector>
#include <iostream>
using namespace std;

void sortVec(vector<int> & 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<int> 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
deleted account xyzzy (5768)
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.
seeplus (6591)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
ptrdiff_t binarySearch(const std::vector<int>& 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);
}


seeplus (6591)
1
2
 
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/

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
	const std::vector v { 1, 2, 3, 4, 5, 6 };
	std::vector<int> v1;

	std::copy_n(v.begin(), 3, std::back_inserter(v1));

	std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " "));
}


Last edited on
jonnin (11437)
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
Mishalit (4)
Thanks a lot guys, much appreciated.
deleted account xyzzy (5768)
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.
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
 
#include <iostream>
#include <vector>
#include <numeric> // for std::iota

int main()
{
   // let's create a sized vector, contents default initialized
   std::vector<int> 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<int> 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.
seeplus (6591)
Using C23++ std::ranges::to so that the vector can be const (can't be if using std::iota):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <iterator>

int main() {
	const std::vector v { std::ranges::to<std::vector>(std::ranges::iota_view{1, 7}) };

	std::ranges::copy(v, std::ostream_iterator<decltype(v)::value_type>(std::cout, " "));
	std::cout << '\n';

	const auto v2 { v };

	std::cout << '\n';
	std::ranges::copy(v2, std::ostream_iterator<decltype(v2)::value_type>(std::cout, " "));
	std::cout << '\n';
}


or for reversed sequential:

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

Last edited on
Topic archived. No new replies allowed.