Implementation of Quicksort in C

My code is based on the pseudo code given in the book  “Introduction To Algorithms” by Cormen, Leiserson, Rivest and Stein.

#include <stdio.h>
#include <conio.h>
#include <time.h>

#define SIZE_OF_ARRAY 4000

int arraySort[SIZE_OF_ARRAY];

int Partition(int arrayToSort[], int start, int end);
void QuickSort(int arrayToSort[], int start, int end);

int Partition(int arrayToSort[], int start, int end)
{
 int i, j, temp, retVal;

 i = start - 1;

 for( j = start; j < end; j++)
 {
 if (arrayToSort[j] <= arrayToSort[end])
 {
 i = i + 1;
 // exchange A[i] with A[j]
 temp = arrayToSort[i];
 arrayToSort[i] = arrayToSort[j];
 arrayToSort[j] = temp;
 }
 }
 // exchange A[i+1] with A[r]
 temp = arrayToSort[i+1];
 arrayToSort[i+1] = arrayToSort[end];
 arrayToSort[end] = temp;

 retVal = i + 1;

 return retVal;
}

void QuickSort(int arrayToSort[], int start, int end)
{
 int mid;

 if (start < end)
 {
 mid = Partition(arrayToSort, start, end);
 QuickSort(arrayToSort, start, mid - 1);
 QuickSort(arrayToSort, mid, end);
 }
}

int wmain(void)
{
 int i;

 printf("The array to sort is: \n");
 for (i = 0; i < SIZE_OF_ARRAY; i++)
 {
 arraySort[i] = SIZE_OF_ARRAY - i;
 printf("%d\t", arraySort[i]);
 }
 printf("\n");

 QuickSort(arraySort, 0, SIZE_OF_ARRAY - 1);

 printf("The sorted array is: \n");
 for (i = 0; i < SIZE_OF_ARRAY; i++)
 {
 printf("%d\t", arraySort[i]);
 }
 printf("\n");

 printf("Enter to exit the program\n");
 getchar();

 return 1;
}
Advertisements

PCB Design Fundamentals – A Design Guide

Recently i had the privilege to get some hands on training from one of the senior guys working at the Switzerland headquarters of our company. Till date, i had only learned about PCB design by reading books with a bit of experience coming from having dealt with PCB design vendors. It was very interesting to see the actual application of the principles i learned from someone very knowledgeable and experienced, first hand. The most interesting part of the training was the part where the concept of return paths was explained and how to take care of this while doing PCB design. It is something which i had not understood previously during my reading of books and application notes.

Rather than regurgitating what i learned and doing a shoddy job of it, i will just share the link to the design guide which my experienced colleagues have put out there for the benefit of customers of our company and others who might benefit from our products and work.

http://developer.toradex.com/hardware-resources/arm-family/carrier-board-design 

On the above link you will find a link to the Apalis Carrier Board Design Guide which you should read.

Enjoy!!!

Implementation of Merge Sort in C

The kings and the imperial powers have from times immemorial used the “Divide and Conquer” methodology to rule over their subjects and kingdoms. A very effective method indeed if you were to consider the example of Indian history and how the British used this for consolidating their authority over the Indian subcontinent. But, did you know that this “Divide and Conquer” paradigm can also be used in developing efficient algorithms for solving quiet a few problems effectively.

One such case is the problem of sorting. Merge sort uses the divide and conquer approach for solving the sorting problem. If you were to use a simple sorting algorithm like the Insertion sort, for let’s say sorting an array of a million numbers,it would take quiet a while to arrive at the solution. The same sorting problem can be solved much faster using the Merge sort algorithm.

Now, i won’t go in to details explaining merge sort and insertion sort (already a lot of literature is available on this on the internet), but, there is something called as asymptotic notation for denoting the worst or average case running time of such algorithms. The average case running time of Insertion sort is Theta(n squared) while that of Merge sort is Theta( n * log n). This implies that for a large enough “n” merge sort will always outperform insertion sort, though for small problems insertion sort might be more suitable. These details you can find in an algorithm and data structures book like “Introduction To Algorithms” by Cormen, Leiserson, Rivest and Stein. The implementation below is based on the pseudo code given in this book.

If you are more interested you can look up how the “Divide and Conquer” approach is used for designing algorithms and also how the asymptotic notation is used in their analysis.

The below code gives an implementation of merge sort in C and also shows how for sorting a 10000 element array, the number of CPU cycles taken by insertion sort is more than merge sort.

#include <stdio.h>
#include <conio.h>
#include <time.h>

int arrayToSort[10000];

void InsertionSort(int arrayToSort[], int start, int end)
{
    int i, j, key;
    clock_t cstart, cfinish;
    cstart = clock();
    for (j = start; j <= end; j++)
    {
        key = arrayToSort[j];
        i = j - 1;
        while ( i >= 0 && arrayToSort[i] >= key)
        {
            arrayToSort[i+1] = arrayToSort[i];
            i = i - 1;
        }
        arrayToSort[i+1] = key;
    }
   cfinish = clock();

   printf("The number of CPU clock cycles for Insertion Sort is %d\n", (cfinish - cstart));

   printf("Press any key to continue\n");
   getchar();

   printf("The result of Insertion Sort is:\n");

   for ( i = start; i < end; i++)
       printf("%d\t", arrayToSort[i]);
   printf("\nPress any key to continue\n");
   getchar();
}

void Merge(int tempArray[], int start, int mid, int end)
{
 int leftArray[5001];
 int rightArray[5001];
 int n1 = mid - start + 1;
 int n2 = end - mid;
 int i, j, k;

 for (i = 0; i < n1; i++)
 {
     leftArray[i] = tempArray[start + i];
 }
 for (j = 0; j < n2; j++)
 {
     rightArray[j] = tempArray[mid + j + 1];
 }
// Assign the Sentinel value
 leftArray[i] = 99999;
 rightArray[j] = 99999;
 i = 0;
 j = 0;
 for (k = start; k <= end; k++)
 {
     if(leftArray[i] <= rightArray[j])
    {
        tempArray[k] = leftArray[i];
        i = i + 1;
    }
    else
    {
        tempArray[k] = rightArray[j];
        j = j + 1;
    }
  }
}

void MergeSort(int tempArray[], int start, int end)
{
 int mid;
 if(start < end)
 {
     mid = (start + end) / 2;
     MergeSort(tempArray, start, mid);
     MergeSort(tempArray, (mid+1), end);
     Merge(tempArray, start, mid, end);
 }
}

int main(void)
{
 int i;
 clock_t start, finish;

 // Initialize the array for the simulation of worst case in Insertion Sort
for ( i = 0; i < 10000; i++)
    arrayToSort[i] = 10000 - i;
InsertionSort( arrayToSort, 0, 10000);
// Initialize the array again for the simulation of worst case in Merge Sort
for ( i = 0; i < 10000; i++)
    arrayToSort[i] = 10000 - i;
start = clock();
MergeSort(arrayToSort, 0, 9999);
finish = clock();

printf("The number of CPU clock cycles for Merge Sort is %d\n", (finish-start));

printf("Press any key to continue\n");
getchar();

printf("The result of Merge Sort is:\n");

for ( i = 0; i < 10000; i++)
    printf("%d\t", arrayToSort[i]);

 printf("Press any key to exit\n");
 getchar();

 return 1;
}

On my Intel Core-i5 laptop, the number of cycles for insertion sort comes out to be 160 and for merge sort it comes out to 37.

Hope you will find this interesting enough to get started on learning algorithms and data structures.