Category Archives: Coding

The “quick-sort” adventure & some great links to learn it.

Recently I had to figure out the workings of quick sort,one the fastest and easiest sorts to implement. There is a heap load of tutorials about quick sort apart from the videos demonstrations and animations showing the inner workings of quick sort. Before I link to the resources which I found helpful in learning quick sort, here is my implementation of quick sort in C.
[cpp]
int partition_data(int* data, int low, int high)
{
if(low > high)
return -1;

int down = low;
int up = high;
//just assume and take the first element as the pivot value and index
int pivot = low ;
int pivot_element = data[pivot];

while(down < up){ //keep moving down till the you find an element whose value is greater than the pivot element. //this element should be on the right side of the pivot element while(data[down] <= pivot_element && down < high) down++; //keep moving up till you find an element which is smaller than the pivot element. // this element should be on the left side of the pivot element. while(data[up] > pivot_element && up > low)
up–;

//swap the elements
if(down < up){ swap(data[down], data[up]); } } //swap the pivot and the up element data , placing the pivot in its correct position swap(data[pivot], data[up]); //extra step just for the sake of clarity pivot = up; return pivot; } void qik_sort(int *data, int low, int high) { if(high > low){
int pivot = partition_data(data, low, high);
print_data(data, 10);
//sort the low -> pivot array
qik_sort(data, low, pivot – 1);
//sort the pivot -> high array
qik_sort(data, pivot + 1, high);
}
}
[/cpp]

The version is a bit more documented than the ones you would generally find online. Also I assume my notes here will help me in recollecting quick sort in the future(This time it took me 3 days to figure it out).

Some helpful resources for learning quick sort are as follows:

  • http://www.comp.dit.ie/rlawlor/Alg_DS/sorting/Quick%20Sort%20Explanation.pdf
  • – The example given makes it worth a read.

  • http://m3peeps.org/qs.htm
  • – One of the most easy to understand explanations of quick sort.

  • http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L16-QuickSort.htm
  • http://betterexplained.com/articles/sorting-algorithms/
  • http://www.angelfire.com/pq/jamesbarbetti/articles/sorting/001_QuicksortIsBroken.htm
  • – Great analysis and great resource to getting more out of the simple quick sort.

  • http://stackoverflow.com/questions/6903064/handling-duplicate-keys-in-quicksort
  • – Mandatory stackoverflow.com links

  • http://stackoverflow.com/questions/11355621/pseudo-quicksort-time-complexity
  • – Mandatory stackoverflow.com links

Font for programmers.

Programming fonts trigger as passionate debate as sometimes politics or religion do. Every programmer has his/her favorite font,but mostly the monotype small fonts rule programmers heart.
The clarity of such fonts is very important. Here is some information about some programmer fonts that I have collected over the past few weeks.

Dina rules!!
My favorite, which seems to be favorite among quite some programmers, is the Dina font. The clarity is amazing and the width saving fits more code into the screen. Just google for Dina and you can find many posts about how Dina has made their programming life easy :). While making the programming life easy is more of a psychological thing, but one thing is clear that Dina makes code easy to read on the screen.
Here is a sample of Dina in action in Carbide.c++.

Dina in action.

Dina in action.


Continue reading

Project reviews : An essential exercise to maintain momentum and direction in hobby projects.

For a past month I have been coding a Symbian native application as a hobby project. What was initially a month’s exercise(according to my earlier estimates), is not even 50% over after nearly a month. There is progress , daily checkins and visual progress in terms of the UI development. But the project still seems hopelessly over-schedule. So what went wrong?
I decided to preside over this question to understand the factors affecting my progress. I made a long list of features, features of my application. Then I tagged them according to the phase they were conceptualized. And finally the version in which they will be released. Check the pie chart of the same.

Features added in phase?

So as it is clear from the pie chart, as I continued coding I did not stick to the feature list which I had planned. Adding more killer features to the app only adds on to the agony and stretches the limits of the developers interest. The most important thing is to freeze the feature set and even if some “absolutely needed” feature emerges, it should be added to the list of features so that work can be done on it subsequently.
Continue reading

Some OpenGL ES links.

  1. Linear Algebra Video Lectures from MIT Open Courseware.
  2. A First Course in Linear Algebra – Online book.

OpenGL – Just links for making OpenGL ES work on various platforms

OpenGL ES for Symbian links

C++0x is ready to rule.

In March 2011, a star was born and no one noticed. Atleast, the interpreted types did not. 🙂

The C++0x standard is approved and soon we will see compilers shouting from the top of their roofs that they support C++0x.

I am still reading about it, so here is the link dump of the most important C++0x links:

Also, there is one video which sums up C++0x quite well:

CPP Common Knowledge notes!!

[cpp]
class TestCode
{
//This is a test for Syntax highlighter!!!
};
[/cpp]
Item #11 : Compiler puts stuff in classes.
Compiler puts a virtual function table ptr in each class object with virtual functions.
Virtual function table pointer not same across platforms!!
Compiler may not put all these extra constructs in a struct.
Virtual inheritance is required when the diamond inheritance is causing issues.
For example:
[cpp]
class Base
{
public:
virtual void foo();
};

class D1 : public virtual Base
{
public:
void foo2();
};

class D2 : public virtual Base
{
public:
void foo3();
};

class SD : public D1, public D2
{
// We have taken care of the diamond inheritance issue with the virtual keyword
// so compiler is gonna shut up now!!
};
[/cpp]
Item #12 : Assignment & initialization are different.
These two ops not so diff in built-in types like int, char etc.
For user-defined types, it would not be advisable to perform user-defined assignment.
[cpp]

class X
{
char* buf;
mutable bool modified;
Y obj;
public:X()
{
buf = new char[100];
for(int i = 0;i<100;i++)
modified = false;
if( < 98)
return;
buf[index] = c;
modified = true;
}

void printdata()
{
cout << "Data is "<<;
ptr =static_cast(::operator new(sizeof(X)+100));// X::buf is not init!!
ptr->setData(0,’c’);
}
[/cpp]
Item #13 : Copy operations.
Copy construction and copy assignment are different operations.
[cpp]
class Hoo
{
char* buf;
int size;
public:
//copy CTor
Hoo()
{
buf = 0x00;
size = 0x00;
}

~Hoo()
{
if(buf)
{
delete[] buf;
buf = NULL;
}
size = 0x00;
}

void setData(char* data, int asize)
{
size = asize;
buf = new char[size + 1];
memset(buf, 0x00, size+1);
strncpy(buf, data, size);
}

Hoo(Hoo const &amp; hoo)
{
setData(hoo.getBuf(), hoo.getSize());
}

Hoo& operator= (Hoo const &hoo)
{
if(this != &hoo)
{
if(buf)
{
delete[] buf;
buf = NULL;
}
size = 0x00;
setData(hoo.getBuf(), hoo.getSize());
}
return *this;
}

char* getBuf() const
{
return buf;
}

int getSize() const { return size;}

};

void copy_ctor_assgn()
{
Hoo data;
data.setData("Hello",5);
Hoo dat2(data);
//copy ctor invoked here
Hoo dat3;
dat3 = dat2;// assgn operator invoked here
}
[/cpp]
Item #14 :Function Pointers.
Legal to point to inline functions, but the resultant call will not be inline.The compiler will not be able to determine at compile time what function is being called.
Can also point to an overloaded function. The particular function called will depend on the match between the function ptr type and the overloaded functions.