What is wrong with this code? Not getting the right output.
void selectionSort(vector<int>& arr, int n)
{
for(int i = 0; i < n-1; i++ )
{
int min = arr[i];
for(int j = i+1; j < n; j++)
{
if(arr[j] < min)
min = arr[j];
}
swap (min, arr[i]);
}
}
You are using the local variable min in the swap where you needed to use the vector element.
swap(arr[index_min], arr[i]) // `index_min` is the index of the current min value.
The variable min stores the value of the element arr[i]
int min = arr[i];
After this call of the function swap
swap (min, arr[i]);
the value stored in the element arr[i] can be lost. You need to swap values of two elements of the vector.
Also the second parameter of the function only confuses.
void selectionSort(vector<int>& arr, int n)
For example the vector can have less elements than the value of n.
Either declare the function like
void selectionSort(vector<int>& arr );
and use the member function size() to determine the number of elements in the vector.
Or declare the function like
void selectionSort( std::vector<int>::iterator first,
std::vector<int>::iterator last );
Or declare the function as a template function that uses forward iterators.
Here is a demonstration program.
#include <iostream>
#include <utility>
#include <vector>
#include <iterator>
void selectionSort( std::vector<int> &v )
{
for ( std::vector<int>::size_type i = 0; i < v.size(); i++ )
{
auto min_i = i;
for ( auto j = i + 1; j < v.size(); j++ )
{
if ( v[j] < v[min_i] ) min_i = j;
}
if ( min_i != i ) std::swap( v[i], v[min_i] );
}
}
int main()
{
std::vector<int> v = { 9, 7, 6, 5, 4, 3, 2, 1, 0 };
for ( const auto &item : v )
{
std::cout << item << ' ';
}
std::cout << '\n';
selectionSort( v );
for ( const auto &item : v )
{
std::cout << item << ' ';
}
std::cout << '\n';
}
The program output is
9 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 9
Or if to use iterators then the function can look the following way as shown in the demonstrative program below.
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
template <typename ForwardIterator>
void selectionSort( ForwardIterator first, ForwardIterator last )
{
for ( ; first != last; ++first )
{
auto min_it = first;
for ( auto next = std::next( first ); next != last; ++next )
{
if ( *next < *min_it ) min_it = next;
}
if ( min_it != first ) std::iter_swap( min_it, first );
}
}
int main()
{
std::vector<int> v = { 9, 7, 6, 5, 4, 3, 2, 1, 0 };
for ( const auto &item : v )
{
std::cout << item << ' ';
}
std::cout << '\n';
selectionSort( std::begin( v ), std::end( v ) );
for ( const auto &item : v )
{
std::cout << item << ' ';
}
std::cout << '\n';
}
Again the program output is
9 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 9
Using iterators you can sort any subrange of a vector.
Instead of the inner for loop in the function definition above you can use standard algorithm std::min_element. In this case the function will look the following way
template
template <typename ForwardIterator>
void selectionSort( ForwardIterator first, ForwardIterator last )
{
for ( ; first != last; ++first )
{
auto min_it = std::min_element( first, last );
if ( min_it != first ) std::iter_swap( min_it, first );
}
}
