Coder's Guild Mailing List

Sorting

Posted by Ng Oon Keat on 1999-07-25

Hi. I am having problems in sorting algorithm, I hope that you guys can
help me out. 

I wrote Insertion Sort, Merge Sort and Heap Sort in C++, but I don't know
what should I put the ASSIGNMENT and COMPARISON counters in the code.

This is a part of Insertion Sort :

#define compGT(a,b) (a > b)

void Sort :: InsertionSort(int N)
{
   int i, v, j, x;
	a = new int[N];
	Fill(a, N);

   for (i = 1; i <= N; i++)
   {
	v = a[i];
	  for (j = i-1; j >= 0 && compGT(a[j], v); j--)
		a[j+1] = a[j];
	  a[j+1] = v;
   }

This is a part of Merge Sort :

void Sort :: MSort(int *array, int l, int r)
{
	int i, j, k, m, *b;
   b = new int[r];

   if (r > l)
   {
	m = (r+l)/2;
	  MSort(array, l, m);
	  MSort(array, m+1, r);
	  for (i = m+1; i > l; i--)
		b[i-1] = a[i-1];
	  for (j = m; j < r; j++)
		b[r+m-j] = a[j+1];
	  for (k = l; k <= r; k++)
		a[k] = (b[i]<b[j]) ? b[i++] : b[j--];
   }
}

This is part of Heap Sort :

void Sort :: UpHeap(int k)
{
	int v;

	v = a[k]; a[0] = itemMax;

	while(a[k/2] <= v)
	{
		a[k] = a[k/2];
		k = k/2;
	}
	a[k] = v;
}

Please help me to add the ASSIGNMENT and COMPARISON counters in these three
codes, thanks a lot !

Regards,
Kelly

Previous post | Next post | Timeline | Home