Tranlating old code to the STL style

VeganFanatic

OK I found a sort algorithm on Wikipedia, that is done like the std::sort so I figured why not convert the who lot that I have to STL. Blah. First the new sort

template<class ForwardIterator> void comb(ForwardIterator first, ForwardIterator last){
static const double shrink_factor = 1.247330950103979;
typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
difference_type gap = std::distance(first, last);
bool swaps = true;
while ( (gap > 1) || (swaps == true) ){
if (gap > 1)
gap = static_cast<difference_type>(gap/shrink_factor);
swaps = false;
ForwardIterator itLeft(first);
ForwardIterator itRight(first); std::advance(itRight, gap);
for ( ; itRight!=last; ++itLeft, ++itRight ){
if ( (*itRight) < (*itLeft) ){
std::iter_swap(itLeft, itRight);
swaps = true;
}
}
}
}

So now the old bubble sort

template <typename T> void bubble(std::vector<T> &a) { // O(n^2)
size_t size = a.size() - 1;
for (int pass = 0; pass < size; pass++) {
for (int n = 0; n < size; n++) {
if (a[n] > a[n+1])
std::swap(a[n], a[n+1]);
}
}
}

and this is as far as I have gone so far

template<class ForwardIterator> void bubble(ForwardIterator first, ForwardIterator last){
typedef typename std::iterator_traits<ForwardIterator>::difference_type difference_type;
difference_type size = std::distance(first, last);
}

http://www.contract-developer.tk

Stuart Dootson

How's this?

template <typename T>
void bubble(std::vector<T> &a)
{
typedef typename std::vector<T>::iterator Iter;
Iter last = a.end()-1;
for(Iter pass=a.begin();pass!=last;++pass)
for(Iter n=a.begin();n!=last;++n)
if (*n > *(n+1))
std::iter_swap(n, n+1);
}

or this, which doesn't keep re-sorting the items at the end of the vector that have already been sorted…

template <typename T>
void bubble(std::vector<T> &a)
{
typedef typename std::vector<T>::iterator Iter;
for(Iter last = a.end()-1;last!=a.begin();--last)
for(Iter n=a.begin();n!=last;++n)
if (*n > *(n+1))
std::iter_swap(n, n+1);
}

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p CodeProject MVP for 2010 - who'd'a thunk it!

VeganFanatic

After a few moments looking over the book I figured out that I need to watch the pointers close when using the STL method of iterators. This is not well covered in any of the books I have. No big deal, that is what forums are for. Here is what I ended up with that does work properly.

template <typename iterator> void bubble(iterator first, iterator last) { // O(n^2)
iterator i, j;
for (i = first; i != last; ++i)
for (j = first; j < i; ++j)
if (*i < *j)
std::iter_swap(i, j); // or std::swap(*i, *j);
}

Now I have this other sort that is annoying me.

template <class iterator> void gnome(iterator first, iterator last){ // O(n^2)
iterator pos = first;
iterator temp;
while (pos <= last) {
if ((pos == first) || (*pos >= *(pos-1)))
++pos;
else {
//{int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
std::iter_swap(pos, pos-1);
--pos;
}
}
}

This one does not work, not sure what the problem is.

http://www.contract-developer.tk

Stuart Dootson

What iterators are you calling it with? This sample program seems to sort the data OK…

#include <vector>
#include <iostream>
#include <iterator>

template <class iterator> void gnome(iterator first, iterator last){ // O(n^2)
iterator pos = first;
iterator temp;
while (pos <= last) {
if ((pos == first) || (*pos >= *(pos-1)))
++pos;
else {
//{int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
std::iter_swap(pos, pos-1);
--pos;
}
}
}

int main(int, char**)
{
std::vector<int> vec;

vec.push_back(4);
vec.push_back(3);
vec.push_back(5);
vec.push_back(-10);
vec.push_back(13);
vec.push_back(2);
vec.push_back(1);

gnome(vec.begin(), vec.end()-1);

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

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p CodeProject MVP for 2010 - who'd'a thunk it!

VeganFanatic

here is the call routine

void RunGnomeSort(void) {
size_t size = 10000;
std::vector<int> data;
data.resize(size);
for (int i = 0; i < size; i++)
data[i] = (int)rand();
sort::gnome(data.begin(),data.end());
//for (int i = 0; i < size; i++)
//std::cerr << data[i] << std::endl;
data.resize(0);
}

http://www.contract-developer.tk

Stuart Dootson

Right - it's this line: sort::gnome(data.begin(),data.end()); Like in my example, that should be sort::gnome(data.begin(),data.end()-1); data.end() points to the element after the last element in the vector, and the sort routine explicitly accesses the last parameter.

Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p CodeProject MVP for 2010 - who'd'a thunk it!

VeganFanatic

Then I guess I need to change the function a tad, so that its a drop in comparable to std::sort. I changed the code while (pos < last) { from <= That has it working now, thanks for spotting that. Now I think I will post the code on Wilipedia as the algorithm is not super clear.

http://www.contract-developer.tk