Merge Sort - for my students...

Using divide-and-conquer policy we can solve a sorting problem. The divide-and-conquer method suggests the sorting algorithm with the following structure.: if n is one, terminate; otherwise partition the collection of elements into two or more sub collections.; sort each; combine the sub collections into a single sorted collection.

It can be depicted as follows:

void Sort(a[], n)

{

    if(n>= k) { //k is global

        i = n/k;

        j = n-i;

    Let A consist of the first i elements in a[]

    Let B consists of the remaining j elements in E

    Sort(A,i);

    Sort(B,j);

    merge(A,B,a,i,j); //merge A and B into a[]

}

 else sort a[] using insertion sort.

}

In the above pseudo code, if we make k = 2, we get merge sort.

The complete source code of Merge Sort can be found here.

Analysis of Merge Sort:

From the following algorithm of Merge Sort, the run time T(n) can be deduced as follows:

void MergeSort(int a[], int low, int high)

{

int mid;

if(low(high))

{

mid = (low+high)/2; ==> Θ(1)

MergeSort(a,low,mid); ==>T(n/2)

MergeSort(a,mid+1,high);==>T(n/2)

merge(a,low,mid,high);==>Θ(n)

}

}

Therefore we can write T(n) = 2T(n/2) + Θ(n)

Comparing it with the Master theorem, we get a = 2, b  = 2 and d = 1. Hence a = b^d which means it is the second condition of the Master Theorem.

Thus we get T(n) = Θ (n log n)

Quick Sort - for my students...

Quick Sort is a sorting algorithm where we apply Divide and Conquer policy. In this sorting algorithm, the n elements to be sorted are partitioned into three segments - a left segment, a middle segment and a right segment. The middle segment is called pivot. The middle segment exactly contains one element. The partition is done in such a way so that all the elements in the left segment have key less than the pivot and all the elements in the right segment have keys greater than the pivot. As a result, the left segment and the right segment can be sorted independently.

The basic principle of Quick sort is as follows:

• Select an element from a[0:n-1] for middle. This element is called pivot.
• Partition the remaining element in such a fashion that all elements in the left of the pivot have keys less than the pivot, and all the elements in the right segment have keys greater than the pivot.
• Sort left segment using quick sort recursively
• Sort right segment using quick sort recursively
• The answer will be left followed by middle followed by right.

The algorithm of the quick sort can be found here.

Debugging of the Algorithm of the code:

Step I: To begin with we get m = 0, n = 6, hence k = 3. After doing swap(&list[m],&list[k]), we get key = 5. The following two steps make i = 1 and j = 6.

Step II: Now the loop starts.

II while loop fails as list[i] (7) is not less than key (5). Hence i does not increase and it remains 1. The III while loop succeeds (as list[j]  > key)and hence j is decremented. So j becomes 5. In the next iteration of the III while loop, the list[j]>k condition fails, hence j remains 5 and we exit the III while loop. So we exchange list[i] and list[j] and the array becomes {5,1,8,3,2,7,9}

Next the II while loop succeeds and we increment i. Hence i becomes 2. The III while loop also succeeds and hence j becomes 4. So list[i] = list [2] = 8 and list[j] = list[4] = 2. So when we swap between list[i] and list[j], the array becomes list {5,1,2,3 8,7,9}.

Next the II while loop succeeds two times and we get i = 4. The III while loop also succeeds and we get j = 3. As j becomes larger than i, we come out of the I while loop.

Next we do swap(&list[m],&list[j]). And the list becomes list {3,1,2,5,8,7,9}

After that we recursively sort list{3,1,2}, the left segment and list{8,7,9}, the right segment.

See how all the elements of the left segment are less than 5 and all the elements in the right segment are greater than 5.

This is how we achieve the Quick Sort.

Pointer Semantics Vs Value Semantics

Value semantics means we directly deal with the values and we pass copies of that value around. We can say that nobody will change the value.

However, in pointer semantics we deal with pointer, and anyone can change the value at the pointer location.

Consider the following program.

/*

 * main.c

 *

 *  Created on: Sep 18, 2010

 *      Author: administrator

 */

#include

void f (int * p, int * q) {

p = q;

*p = 2;

}

int i = 0, j = 1;

int main ( )

{

f(&i, & j);

printf("%d %d\n", i, j) ;

return 0;

}

The result will be 0 and 2. Why? Let me explain it to you.

We have two global variable i and j and we pass the pointer of these two variables to the function f.  When we do p = q, we actually loose the reference of i, and we get two pointers namely p and q both pointing to j. then when we do * p = 2, we actually change the value of j to 2. 

The whole thing can be depicted by the following diagram...

However, as we lost the reference of i in the step p = q, in the main program, the value of i that gets printed is the global variable that is 0. Hence we get the result as i = 0 and j = 2.

Hope this explains the pointer arithmetic to my students...