Excersices

[vlad from moscow]

By the way the modification of the insertion algorithm you showed has one shortage. This algorithm is not stable while the ordinary insertion sort algorithm is stable.

[Yueeng]

Hey i think that the bubble-sort you write in the very beginning doesn't seem right.

In the simplest form it' should be something like:

for (int i=0;i<N;++i)
{
    for (int j=0;j<(N-i-1);++j)
    {
        if (a[j]>a[j+1]) swap(a[j],a[j+1]);
     }
}

your code forgot the "j<(N-i)" part.

@vlav
After another thought, using iterator for bubble sort is a little bit difficult i think. Since the iterator can only move between begin() and end(), how could you calculate the "j<(N-i)" part?

@Smac89
Thanks for the nice site!

@maniac
And by the way maybe the USACO testing site is the one you want.

EDIT: Corrected, j should start with 0.

[vlad from moscow]

@Yueeng
@vlav
After another thought, using iterator for bubble sort is a little bit difficult i think. Since the iterator can only move between begin() and end(), how could you calculate the "j<(N-i)" part?

It is the trick I would like to see in your realization.:)

[maniac]

Mmm can you show it to me with arrays, please? Because I can't get the idea. Is it something like the one that @Yueeng showed?

@Yueeng, thanks for the suggestion. I will view it closer later, but I think it will be very useful :)

[abhishekm71]

@Yueeng
shouldn't the loop for j start from 0?

@vlad
Something like this:??

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

using namespace std;

int main()
{
    std::vector<int> myVec( 10 );
    for ( int i = 0; i < 10; ++i )
      myVec[i] = 10 - i;

    typedef std::vector<int>::iterator iter_type;

    iter_type rev_it ( myVec.end() );
    for ( iter_type it1 = myVec.begin(); it1 != myVec.end() - 1; ++it1 ) {
        for ( iter_type it2 = myVec.begin(); it2 < rev_it - 1; it2++ ) {
        if ( *it2 > *( it2 + 1 ) )
          std::iter_swap( it2, it2 + 1 );
      }
      rev_it--;
    }
    for ( iter_type it1 = myVec.begin(); it1 != myVec.end(); ++it1 ) {
      std::cout << *it1 << " ";
    }
    std::cout << std::endl;
    return 0;
}

[vlad from moscow]

Expression rev_it--; is allowed only for bidirectional iterators. Forward iterators have no such operation.

[abhishekm71]

yup.. I don't know how they are declared.

However, surprisingly the above code compiles and runs fine on my Qt Creator IDE

[vlad from moscow]

Yes, it is the Bubble sort algorithm. Now try to write it using forward iterator. It is what I suggested in the very beginning of the thread.:)

[vlad from moscow]

As for you code then it uses random access iterator. For example

myVec.end() - 1

or

it2 + 1

Forward iterator has only one operation: increment..

[abhishekm71]

Well hows the following crude attempt?

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

template <class T>
void mySort( const T& it_begin, const T& it_end ) {
    T rev_it = it_end;
    for ( T it1 = it_begin; ++it1 != it_end; ) {
        T it2 = it_begin;
        T temp_it = it_begin;
        for ( ; it2 != rev_it ; ) {
            temp_it = it2;
            if ( ++it2 != rev_it )
                if ( *temp_it > *( it2 ) )
                    std::iter_swap( temp_it, it2 );
        }
        rev_it = temp_it;
    }
}

int main()
{
    std::vector<int> myVec( 10 );
    for ( int i = 0; i < 10; ++i )
      myVec[i] = 10 - i;

    typedef std::vector<int>::iterator iter_type;

    mySort<iter_type> (myVec.begin(), myVec.end());
/*
    iter_type rev_it ( myVec.end() );
    for ( iter_type it1 = myVec.begin(); it1 != myVec.end() - 1; ++it1 ) {
        for ( iter_type it2 = myVec.begin(); it2 < rev_it - 1; it2++ ) {
        if ( *it2 > *( it2 + 1 ) )
          std::iter_swap( it2, it2 + 1 );
      }
      rev_it--;
    }*/
    for ( iter_type it1 = myVec.begin(); it1 != myVec.end(); ++it1 ) {
      std::cout << *it1 << " ";
    }
    std::cout << std::endl;
    return 0;
}

[Smac89]

void bubble_sort(void *array, size_t num, size_t ptr_size, int (*cmp)(void *, void *)) {
	int didSwap;
	size_t temp;
	do {
		didSwap = 0;
		for (temp = 0; (temp+1) < num; ++temp)
			if ((*cmp)((int *)(array+(temp*ptr_size)), (int *)(array+(-~temp*ptr_size)))) {
				std::swap(*(int *)(array+(temp*ptr_size)), *(int *)(array+(-~temp*ptr_size)));
				didSwap = 1;
			}
		num = temp;
	} while (didSwap);
}

Full c code:

#include <stdio.h>
#include <string.h>

int compare(void *a, void *b) {
	return (strcmp(*(char **)a, *(char **)b)) > 0;
}

void swap (void *a, void *b) {
	char *temp = *(char **)a;
	*(char **)a = *(char **)b;
	*(char **)b = temp;
}

void bubble_sort(void *array, size_t num, size_t ptr_size, 
			int (*cmp)(void *, void *), void (*swp)(void *, void *)) {
	int didSwap;
	size_t temp;
	do {
		didSwap = 0;
		for (temp = 0; (temp+1) < num; ++temp)
			if ((*cmp)((int *)(array+(temp*ptr_size)), (int *)(array+(-~temp*ptr_size)))) {
				(*swp)((int *)(array+(temp*ptr_size)), (int *)(array+(-~temp*ptr_size)));
				didSwap = 1;
			}
		num = temp;
	} while (didSwap);
}
 
int main ( void ) {
	char *array[] = {"Florida", "Oregon", "California", "Georgia"};
	bubble_sort(array, 4, sizeof (char *), compare, swap);
	
	printf("{");
	for ( int r = 0; r < 4; ++r ) printf(" %s", array[r]);
	puts(" }");
	
	return 0;
}

Edit2:
Wonder how qsort does it's swapping of values. Anyone know?

[Yueeng]

@abhishekm71
Yes you are right, thanks for your correction!
Obviously i'm not that familiar with the idea lies behind it, thus a mistake appeared.

@Smac89
The quick sort doesn't do the swap like( t=a, a=b, b=t), instead it's like the data moving part of Insert sort.
I know it's not clear as what i said, but take a look at the algorithm and you will see.

[Yueeng]

I think this will do:

vector<int> vNum;
void BubbleSort()
{
	for (vector<int>::iterator it=vNum.begin();
			it!=vNum.end();
			++it)
	{
		for (vector<int>::iterator it2=vNum.begin();
				distance(vNum.begin(),it)<distance(it2,vNum.end());
				++it2)
		{
			vector<int>::iterator it3=it2;
			it3++;
			if (*it2>*it3)
			{
				int t=*it2;
				*it2=*it3;
				*it3=t;
			}
		}
	}
}

It's the same idea, just a different implement. The key in this func is the distance(), it calculate the distance between two iterators.