Re: sorts and iterators
On 6/30/2013 10:50 AM, Christopher Pisz wrote:
I am brushing up for an upcoming interview. They let me know beforehand
that they will be asking about sorting algorithms and expect me to write
some code. They let me know I should study, so I am studying :)
I know the old college academic exercises where I can make a struct that
represents a node and implement my own linked list, etc. etc. I'd like
to try some custom sorts and performance time them like I would in the
real world. So, I ask myself, how would I do it in the real world?
I would most likely have some stl container or a class that implements
iterators. I am also aware the stl has a build in sort with O(nlog(n))
complexity.
So, how do I go about implementing a sort that uses iterators? I am not
really sure where to start.
I did some Googling and see stl sort requires swap and a move copy. I
believe these are new c++13 features? Can we assume I am still using the
2003 standard for now and then try again using C++13?
My current job was using really out of date tools and I haven't had the
chance yet to catch up on the new standard.
I gave it a shot and came up with the following code. std::swap appears
to actually be swapping the iterators instead of the values of the
iterators. The loop goes on forever. I am not sure I understand the use
of std::swap anymore. What should I do different? I want to swap the
contents of the element, but keep the iterator pointing to the same
position.
#include <algorithm>
#include <iostream>
#include <vector>
//-------------------------------------------------------------------------------
/// Bubble Sort
/// Complexity O(n^2)
template<typename iterator>
void BubbleSort(iterator begin, iterator end)
{
// Nothing to do when container is empty
if( begin == end )
{
return;
}
iterator previous = begin;
iterator current = previous;
++current;
for(; current != end; ++current)
{
std::cout << "Current: " << *current;
std::cout << " Previous: " << *previous << " " << std::endl;
if( *current < *previous )
{
// This appears to swap the internal pointer and actually
swap the iterators instead of the values?
std::swap(current, previous);
}
std::cout << "sCurrent: " << *current;
std::cout << " sPrevious: " << *previous << " " << std::endl;
previous = current;
}
}
//------------------------------------------------------------------------------
/// Test driver
int main()
{
typedef std::vector<unsigned int> Collection;
Collection collection;
collection.push_back(5);
collection.push_back(2);
collection.push_back(4);
collection.push_back(1);
collection.push_back(3);
/*
// Using STL sort
std::sort(collection.begin(), collection.end());
for(Collection::const_iterator it = collection.begin(); it !=
collection.end(); ++it)
{
std::cout << ' ' << *it;
}
std::cout << '\n';
*/
// Bubble sort
BubbleSort(collection.begin(), collection.end());
system("pause");
return 0;
}