Sorting .....Comparison Sort

Sorting is a technique which is defined such as,

if A[i] and A[j] are two elements of an array, then the array is sorted if for all i and j

A[i] <= A[j] for all i < style="font-weight: bold;">

QuickSort.

You can find the algorithm of QuickSort here on Wikipedia.

I would just touchbase on algo.

QuickSort(int start, int end, int * arr){

if(start < end){
int q = partition(start,end,arr);
QuickSort(start,q-1,arr)
QuickSort(q+1,end,arr)
}
}
This is a recursive defintion of QuickSort. The main function is the partition which returns the index of pivot element. The function runs in a way that if Pivot=arr[end] is the element initially chosen as the pivot. Then at the end of function, the pivot is placed at its correct position q. All the elements with index less than q are smaller than Pivot and all elements greater than q are greater than Pivot. During the entire course of algorithm, Pivot at index q doesn't changes its position.

Iterative version

QuickSort(int start,end, arr){

bounds = {start,end}
pushToStak(bounds);

while(notEmpty(){
bound = popStack()
while(bound.lowerVal < q =" partition(lower,upperval,arr)"> end-1){
Tempbounds = (start,q-1)
bound.lowerVal = q+1
else{
Tempbounds = {q+1,end)
bound.upperVal = q-1
}
pushStack(Tempbounds )
bound
}
}
}

You can find the C implementation of this code on code.goggle.com.
Download QuickSort.

Binary Tree Traversal

There are 3 basic ways to traverse a Binary TREE:-
a) PreOder
b) InOrder
c) PostOrder

And,its very easy to define them recursively

PreOrder:-

a)Visit the Root
b)Visit the Left Sub tree in PreOrder
c)Visit the Right Sub tree in Preorder.

Same can be done for InOrder and Postorder where Root is visited at stage b) and stage c) respectively.

Here is a sample code
PreOrder ( Tree tree){

if(tree!=null){
printf(tree->info);
PreOrder(tree->left);
PreOrder(tree->right);
}
}

Writing recursive definition is easy,
writing iterative version is bit tricky.

You can find the iterative version of all three here. I have posted them at code.google.com.

Feel free to use it and send me your suggestion/comments/feedback.

Cheers,
Kapil Dalwani

Why Let-Them-C ???

Well, to most of the India students who have written some piece of C code, this title would sound similar. Yes, I wanted it to name it "Let Us C" from the famous C language book authored by Yashwant Kanitkar. But, I ddin't wanted to go into legal issues and decided to name it as "Let Them C".. !

I will try to cover problems, suggestion, code etc related to technical problems faced by me during professional experience. So, its a blog meant only for Coders...other can do a void return.

Feel free to contribute, hack, code etc this website.

Cheers,
Kapil Dalwani

P.S. why is the background black?? Well just my way of showing that I care for Mother Earth....