Excersices

[maniac]

Hi :) Can you recommend me a good site with C++ excercises? Exercises about data structures like stack and linked list, about inheritance and other useful and logical things :)

[vlad from moscow]

Excersice #1. Write Bubble sort for forward iterator. :)

[maniac]

Here it is:

         list<int>::iterator Iter = A.begin();
         while(Iter != A.end())
			{				
				list<int>::iterator Iter2 = Iter;
				Iter2++;
				while(Iter2 != A.end())
					{
						if(*Iter > *Iter2)
							{
								int *help = new int;
								*help = *Iter;
								*Iter = *Iter2;
								*Iter2 = *help;
							}
						Iter2++;
					}
				Iter++;
			}

I used directly the <list> library. :)

[vlad from moscow]

Now write it as a general algorithm.

[vlad from moscow]

Instead of this code snip

	int *help = new int;
	*help = *Iter;
	*Iter = *Iter2;
	*Iter2 = *help;

use algorithm std::iter_swap

[vlad from moscow]

By the way the algorithm you showed is not the pure Bubble sort because it does not compare adjacent elements.

[maniac]

What do you mean by saying general algorithm? Something like this code?
And I don't know if you meant just to use iter_swap(Iter, Iter2);
Here is the code:

#include<iostream>
#include<list>
using namespace std;

int main()
    {
         list<int> A;
         A.push_back(2);
         A.push_back(3);
         A.push_back(1);
	 A.push_back(9);
	 A.push_back(0);
	 A.push_back(7);
         
         list<int>::iterator Iter = A.begin();
         while(Iter != A.end())
			{				
				list<int>::iterator Iter2 = Iter;
				Iter2++;
				while(Iter2 != A.end())
					{
						if(*Iter > *Iter2)
							{
								/*int *help = new int;
								*help = *Iter;
								*Iter = *Iter2;
								*Iter2 = *help;*/
								iter_swap(Iter, Iter2);
							}
						Iter2++;
					}
				Iter++;
			}

		 list<int>::iterator IterP = A.begin();
		 for(IterP; IterP != A.end(); IterP++)
			{
				cout << *IterP << " ";
			}

		 cout << endl;
         
         system("pause");      
         return 0;
    }

Greetings :)

[vlad from moscow]

I mean to write a template function that can be used with any container having a forward iterator.

[maniac]

Oh ok. I will think about that :)

[vlad from moscow]

And how is the algorithm named? It looks like a modified selection sort with superfluous swaps.

[vlad from moscow]

As I can guess you simply found that code snip in internet.:) It is not your code.

[maniac]

Oh no.. you can be sure it is my code. I have always done the bubble sort that way (usually for arrays) . I'm new to iterators and that's why I'm a bit confused. Do you think that I will ask for help and then just copy the code from somewhere? :D

[vlad from moscow]

But it is not the Bubble sort algorithm Can you give a reference where this algorithm is described? As I said it looks more as some modification of the selection sort algorithm.

[maniac]

I read it in one book but there are many sites that show it this way. For example mathbits.com/MathBits/CompSci/Arrays/Bubble.htm
I usually do it that way like in the first code that I gave you.. not with the swap function. If it is not pure bubble sort that means that I haven't understand it well. Van you give me example or source to read how it should look like? :)

[vlad from moscow]

The bubble sort is described in many books on data structures and algorithms. I advice to read "Data Structures & Algorithms in Java" by Robert Lafore. Though sometimes his code examples contain bugs nevertheless the text is written with simple clear language.

[vlad from moscow]

The algorithm you showed in fact is some modification of the selection sort. You search the minimum element and substitute the first element of a subsequence for this minimumj element. There is no problem to write such an algorithm with forward iterator. It is more interestiong to realize the bubble sort with using forward iterator.

[Smac89]

This site does not give you exercises in as much as it shows how to implement certain data structures maybe even better than you will learn at school.

http://eternallyconfuzzled.com/jsw_home.aspx

[maniac]

@Smack89, thanks for the great link :)

@vlad: I tought about what you said for the template function but I couldn't do it. I searched for some information and found this:

template<class Iterator>
void Bubble_Sort(Iterator Begin, Iterator End)
	{
		Iterator i, j;
		for(i = Begin; i != End; i++)
			for(j = Begin; j != i; j++)
				{
					if(*i < *j) iter_swap(i, j);
				}
	}

This time it's not my code (http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Bubble_sort#C.2B.2B) :D. I tested it with list and vector containers and it's working. In fact it was not so hard. Just a normal template(but as I said, I'm new to iterators and I tought that it will be much harder).
You was asking about that right? And is this the right Bubble Sort?

Greetings :)

[abhishekm71]

int *help = new int; 
*help = *Iter; 
*Iter = *Iter2; 	
*Iter2 = *help;

One more point: You are leaking memory here.

[vlad from moscow]

Again I very doubt that this algorithm is the bubble sort algorithm. It more resembles the insertion sort algorithm. I think you should not trust such internet references as you pointed out.
Let consider the algorithm.

It splits the sequence into two parts. The left part is partially sorted and the right part is unsorted. Then the algorithm takes the first element of the unsorted part and looks where it can be inserted in the partially sorted part. If it founds the position where the new element can be inserted it in fact shifts right all other elements after the position by means of using the swap operation.

So during the discussion of the exercise of writing the bubble sort algorithm you showed two other algorithms: 1) selection sort, 2) insertion sort.:)
Till now we did not see the bubble sort algorithm.:)

But in any case your examples of algorithms are interesting.