Prev: Need to investigate contents of *.lib files
Next: How do you perform configuration management?
From: NSS GRG on 8 Sep 2009 03:11
hello everyone,
Im doing a project in C++. I want to make a program that simulates
link-lists and sorting algorithms. Can anyone help me please.
From: Pascal J. Bourguignon on 8 Sep 2009 05:33
NSS GRG <gurkhali69(a)gmail.com> writes:
> Im doing a project in C++. I want to make a program that simulates
> link-lists and sorting algorithms. Can anyone help me please.

What aspects of link-lists and sorting algorithms do you want to simulate?


For example, assuming you want to simulate the time various sorting
algorithms take to sort a vector, you could write:


#include <iostream>
#include <iomanip>
#include <math.h>

class Time {
double timeInSeconds;
public:
Time(double seconds):timeInSeconds(seconds){}
double seconds(){return timeInSeconds;}
};

class SortSimulator {
public:
virtual ~SortSimulator(){}
virtual Time sortTime(int vectorSize)=0;
};


class BubbleSortSimulator:public SortSimulator {
double constant;
public:
BubbleSortSimulator(double aConstant=1.0):constant(aConstant){}
virtual ~BubbleSortSimulator(){}
virtual Time sortTime(int vectorSize){
return(constant*vectorSize*vectorSize);
}
};


class QuickSortSimulator:public SortSimulator {
double a;
double b;
public:
QuickSortSimulator(double aVal=1.0,double bVal=1.0):a(aVal),b(bVal){}
virtual ~QuickSortSimulator(){}
virtual Time sortTime(int vectorSize){
return(a*vectorSize*log(vectorSize*b));
}
};


int main(){
BubbleSortSimulator b1(2.0); // a bubble sort with some slowness.
BubbleSortSimulator b2; // a well optimized bubble sort.
QuickSortSimulator q1(10.0); // quicksort tends to be slower.
QuickSortSimulator q2(3.0); // a well optimized quick sort.


std::cout<<std::setw(8)<<"Size"<<" "
<<std::setw(19)<<"BubbleSort 1"
<<std::setw(19)<<"BubbleSort 2"
<<std::setw(19)<<"QuickSort 1"
<<std::setw(19)<<"QuickSort 2"
<<std::endl;
for(int vsize=10;vsize<1000000;vsize*=10){
std::cout<<std::setw(8)<<vsize<<" : "
<<std::setw(19)<<std::fixed<<b1.sortTime(vsize).seconds()
<<std::setw(19)<<std::fixed<<b2.sortTime(vsize).seconds()
<<std::setw(19)<<std::fixed<<q1.sortTime(vsize).seconds()
<<std::setw(19)<<std::fixed<<q2.sortTime(vsize).seconds()
<<std::endl;
}

return(0);
}

/*
-*- mode: compilation; default-directory: "~/src/tests-c++/" -*-
Compilation started at Tue Sep 8 11:31:16

SRC="/home/pjb/src/tests-c++/sort-simu.c++" ; EXE="sort-simu" ; g++ -g3 -ggdb3 -o ${EXE} ${SRC} && ./${EXE} && echo status = $?

Size BubbleSort 1 BubbleSort 2 QuickSort 1 QuickSort 2
10 : 200.000000 100.000000 230.258509 69.077553
100 : 20000.000000 10000.000000 4605.170186 1381.551056
1000 : 2000000.000000 1000000.000000 69077.552790 20723.265837
10000 : 200000000.000000 100000000.000000 921034.037198 276310.211159
100000 : 20000000000.000000 10000000000.000000 11512925.464970 3453877.639491
status = 0

Compilation finished at Tue Sep 8 11:31:16
*/


So we can see that for small vectors, a good implementation of
BubbleSort might be faster than a bad implementation of QuickSort, but
as soon as you have more elements to sort, QuickSort, even a bad
implementation will be much faster.

--
__Pascal Bourguignon__
From: NSS GRG on 9 Sep 2009 05:31
thank you very much..i want to graphically show the process how link
list operates? so i wonder if u could share me your valuable views.
thankx
From: Pascal J. Bourguignon on 9 Sep 2009 06:03
NSS GRG <gurkhali69(a)gmail.com> writes:

> thank you very much..i want to graphically show the process how link
> list operates? so i wonder if u could share me your valuable views.


Well if you want to represent graphically internal objects such as
list nodes and pointers, this will require a little more work.

Simplistic algorithms to represent graphically nodes and pointers may
work well for simple cases, but soon enough you will want to show more
sophisticated graphs, with structure sharing or cycles. At this
point, it might be easier to use a graph library to do the drawing.

Have a look at graphviz and ogdf.

http://www.graphviz.org
http://www.ogdf.net

With either of these libraries you should be able to generate a graph
corresponding to your data structures, before and after any operation.


--
__Pascal Bourguignon__
From: ekkehard.horner on 9 Sep 2009 09:27
NSS GRG schrieb:
> hello everyone,
> Im doing a project in C++. I want to make a program that simulates
> link-lists and sorting algorithms. Can anyone help me please.

Google-ing for
algorithm visualization animation sorting
will give you
lots of references
e.g.
http://scholar.google.de/scholar?q=algorithm+visualization+animation+sorting&hl=de&um=1&ie=UTF-8&oi=scholart
some theory
e.g. http://www.dcs.warwick.ac.uk/pvw04/p11.pdf
a sample application + java code
e.g. http://cg.scs.carleton.ca/~morin/misc/sortalg/
http://thomas.baudel.name/Visualisation/VisuTri/

Repeat this with
"data structure" visualization animation list

Adding the keyword
cpp
and you'll be send to graphviz
http://www.graphviz.org/Documentation/GN99.pdf
 | 
Pages: 1
Prev: Need to investigate contents of *.lib files
Next: How do you perform configuration management?