C Program for Quick Sorting - Quick Sort Program in to Sort Numbers

Quick sort is one of the most efficient sorting algorithms. Here i post a C program to implement Quick sorting. This program is to sort given numbers is ascending order. To sort in descending order using quick sort, only slight changes are needed in program. Changes needed for sorting in descending order are marked in the program as comments.

#include<stdio.h>
void quicksort(int [10],int,int);
int main()
  {
  int x[20],size,i;
  printf("Enter size of the array: ");
  scanf("%d",&size);
  printf("Enter %d elements: ",size);
  for(i=0;i<size;i++)
     scanf("%d",&x[i]);
  quicksort(x,0,size-1);
  printf("Sorted elements: ");
  for(i=0;i<size;i++)
     printf(" %d",x[i]);
  return 0;
  }

void quicksort(int x[10],int first,int last)
  {
  int pivot,j,temp,i;
  if(first<last)
     {
     pivot=first;
     i=first;
     j=last;
     while(i<j)
        {
        while(x[i]<=x[pivot]&&i<last)//for descending, use >= instead of <=
            i++;
        while(x[j]>x[pivot])//for descending, use < instead of >=
            j--;
        if(i<j)
            {
            temp=x[i];
            x[i]=x[j];
            x[j]=temp;
            }
        }
    temp=x[pivot];
    x[pivot]=x[j];
    x[j]=temp;
    quicksort(x,first,j-1);
    quicksort(x,j+1,last);
}
}

Output:
Enter size of the array: 5

Enter 5 elements:
3
8
0
1
2
Sorted elements: 0 1 2 3 8

Algorithm and C Program to Find Candidate Key from Functional Dependencies

First of all, we will see the algorithm to find candidate keys from functional dependencies. The input is functional dependencies.

Algorithm:

1. Find the attributes that are neither on the left and right side

2. Find attributes that are only on the right side

3. Find attributes that are only on the left side

4. Combine the attributes on step 1 and 3

5. Test if the closures of attributes on step 4 constitutes all the attributes. If yes it is a candidate key.

6. If not, find the relation exteriors, that is the attributes not included in step 4 and step 2.

7. Now test the closures of attributes on step 4 + one attribute in step 6 one at a time. All those combinations are candidate keys if their closures constitute all the attributes.

C Program:

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

struct fd
 {
   int left[8],right[8];
   int lcount,rcount;
   }f[10];

int attrcount,closcount=0,fdcount,closure[10];
char attr[10][25];
int nolnor[8],ronly[8],lonly[8],merg1n3[8],exteriors[8];

void getclosure();
void get_nolnor();
void get_ronly();
void get_lonly();
void get_merg1n3();
int iscomplete();

void getclosure()
{
int i,j,k,l=0,issubset,found;
do
 {
   for(i=0;i<=fdcount;i++)//Checking each functional dependancy
    {
      issubset=1;
      for(j=0;j<f[i].lcount;j++)//select each attr in leftside
   {
         found=0;
         for(k=0;k<closcount;k++) //checking with each element of 

closure
          

{
            if(closure[k]==f[i].left[j])
             

{
               found=1;
               break;
               }
            }
         if(found==0)
    {
          

issubset=0;
            break;
            }
   }
  if(issubset==1)
       {
         for(k=0;k<f[i].rcount;k++)
          

{
            found=0;
            for(j=0;j<closcount;j++)
             

{
               if(closure[j]==f[i].right[k])
                found=1;
               }
    if(found==0)
             

{
     closure[closcount]=f[i].right

[k];
             

closcount++;
               }
            }
         }
  }
   l++;
 }while(l<attrcount);
}


void get_nolnor()
 {
   int i,found,j,k,l=0;
   for(i=0;i<attrcount;i++)//take an attribute
    {
      found=0;
      for(j=0;j<=fdcount;j++) //take an fd
          {
          for(k=0;k<f[j].lcount;k++) //check in left
           

{
            if(i==f[j].left[k])
               {
             

found=1;
               break;
               }
            }
          if(found==1) //stop if found.
           

break;
          for(k=0;k<f[j].rcount;k++) //check in right
           

{
            if(i==f[j].right[k])
               {
             

found=1;
               break;
               }
            }
          if(found==1) //stop if found.
           

break;
          }
      if(found==0)
       {
         nolnor[l]=i;
         l++;
         }
      }
 nolnor[l]=222;
 }


void get_ronly()
 {
   int rpresent,lpresent,i,j,k,l=0;
   for(i=0;i<attrcount;i++)//take an atrribute
    {
      rpresent=0;
      for(j=0;j<=fdcount;j++)//take an fd
       {
         for(k=0;k<f[j].rcount;k++)
          

{
            if(i==f[j].right[k])
             

{
               rpresent=1;
               break;
               }
            }
         if(rpresent==1)
          

break;
         }
      lpresent=0;
      if(rpresent==1)
       {
         for(j=0;j<=fdcount;j++)//take an fd
        {
          

for(k=0;k<f[j].lcount;k++)
           

{
             

if(i==f[j].left[k])
             

 {
                lpresent=1;
                break;
                }
             

}
          

if(lpresent==1)
             

break;
          

}
         }
      if(lpresent==0&&rpresent==1)
       ronly[l++]=i;
  }
   ronly[l]=222;
   }

void get_lonly()
 {
   int rpresent,lpresent,i,j,k,l=0;
   for(i=0;i<attrcount;i++)//take an atrribute
    {
      lpresent=0;
      for(j=0;j<=fdcount;j++)//take an fd
       {
         for(k=0;k<f[j].lcount;k++) //looking in leftside
          

{
            if(i==f[j].left[k])
             

{
               lpresent=1;
               break;
               }
            }
         if(lpresent==1)
          

break;
         }
      rpresent=0;
      if(lpresent==1)
       {
         for(j=0;j<=fdcount;j++)//take an fd
        {
          

for(k=0;k<f[j].rcount;k++)//checking in right side
           

{
            

  if(i==f[j].right[k])
      {
                rpresent=1;
                break;
                }
             

}
          if

(rpresent==1)
             

break;
          

}
         }
      if(lpresent==1&&rpresent==0)
         lonly[l++]=i;
      }
   lonly[l]=222;
 }


void get_merg1n3()
 {
   /* combine lonly and nolnor */
   int i,j;
   for(i=0,j=0;lonly[j]!=222;i++,j++)
    merg1n3[i]=lonly[j];
   for(j=0;nolnor[j]!=222;i++,j++)
    merg1n3[i]=nolnor[j];

   merg1n3[i]=222;
   }

int compare(char temp[25])
 {
   int i;
   for(i=0;i<attrcount;i++)
    {
      if(strcmp(temp,attr[i])==0)
      return i;
      }
   return 0;
   }


int iscomplete()
 {
   if(closcount!=attrcount)
    return 0;
   else
    return 1;
   }

void main()
 {
   int i,j,k,attcode,found;
   char schema[100],temp[45],temp1[50];
   for(i=0;i<10;i++)
    {
      f[i].lcount=0;
      f[i].rcount=0;
      }
   printf("\nEnter the schema\n");
   scanf("%s",schema);
   attrcount=0;
   for(i=0;schema[i]!='(';i++);

   do
    {
    j=0;
      i++;
    while(schema[i]!

=','&&schema[i]!=')')
     {
       temp

[j]=schema[i];
       j++;
       i++;
       }
    temp[j]='\0';
    strcpy(attr

[attrcount],temp);
  attrcount++;
      }while(schema[i]==',');

   fdcount=-1;
   printf("\nEnter the functional dependancies\nEnter 0 to stop\n");
   for(i=0;i<10;i++)
    {
      scanf("%s",temp1);
      if(strcmp(temp1,"0")==0)
       break;
      fdcount++;
      j=0;
      if(temp1[0]=='{'||temp1[0]=='(')
       j++;
      do
       {
         if(temp1[j]==',')
             

j++;
         k=0;
         while(temp1[j]!=','&&temp1[j]!=')'&&temp1[j]!

='}'&&temp1[j]!='-')
           

{
            temp[k]=temp1[j];
            k++;
            j++;
            }
            temp[k]='\0';
            attcode=compare(temp);
            f[fdcount].left[f[fdcount].lcount]=attcode;
            f[fdcount].lcount++;
         }while(temp1[j]==',');
  if(temp1[j]==')'||temp1[j]=='}')
       j+=3;
      else if(temp1[j]=='-')
       j+=2;
      if(temp1[j]=='{'||temp1[j]=='(')
       j++;
      do
       {
         if(temp1[j]==',')
             

j++;
         k=0;
         while(temp1[j]!=','&&temp1[j]!=')'&&temp1[j]!

='}'&&temp1[j]!='\0')
           

{
            temp[k]=temp1[j];
            k++;
            j++;
            }
            temp[k]='\0';
            attcode=compare(temp);
            f[fdcount].right[f[fdcount].rcount]=attcode;
            f[fdcount].rcount++;
         }while(temp1[j]==',');

  }


/**************Step1**************
1. Find the attributes that are neither on the left and right side*/
 get_nolnor();

/**************Step2*************
2. Find attributes that are only on the right side*/
   get_ronly();

/**************Step3*************
3. Find attributes that are only on the left side*/
   get_lonly();

/**************Step4*************
4. Combine the attributes on step 1 and 3*/
 get_merg1n3();  //combine 

nolnor and lonly

/**************Step5*************
5. Test if the closures of attributes on step 4 are all the attributes*/
   closcount=0;
   for(i=0;merg1n3[i]!=222;i++)
    {
      closure[closcount++]=merg1n3[i];
      }
   getclosure();
 i=iscomplete();//check whether 

closure of merg1n3 is complete
   if(i==1)
    {
      printf("\nThe candidate key is:\n{");
      for(i=0;merg1n3[i]!=222;i++)
       {
         printf("%s,",attr[merg1n3[i]]);
         }
      printf("\b ");
      printf("}");
      }
   else
    {
/************** Step 6 **************
6. Find the relation exteriors, that is the attrbutes included not in 4 and not in 2
     included not in (ronly & merg1n3)
     */
      k=0;
      for(i=0;i<attrcount;i++)
       {
         found=0;
         for(j=0;ronly[j]!=222;j++)
          

{
            if(i==ronly[j])
             

{
               found=1;
               break;
               }
            }
         if(found==0)
          

{
            for(j=0;merg1n3[j]!=222;j++)
               {
             

if(i==merg1n3[j])
             

 {
                found=1;
                break;
                }
               }
            }
         if(found==0)
          

{
            exteriors[k++]=i;
            }
         }

      exteriors[k]=222;
      printf("Candidate Keys:");
/************** Step 6 **************
7. Now test the closures of attributes on step 4 + one attribute in step 6 one at a time.
*/
    for(k=0;exteriors

[k]!=222;k++)
     {
       closcount=0;
       for

(i=0;merg1n3[i]!=222;i++)
        {
        closure

[closcount++]=merg1n3[i];
          

}
       closure

[closcount++]=exteriors[k];
       getclosure();
   i=iscomplete();//check whether 

closure of this instance of this step is complete
     if(i==1)
      {
          

printf("\n{");
          

for(i=0;merg1n3[i]!=222;i++)
         {
           

printf("%s,",attr[merg1n3[i]]);
           

}
          

printf("%s}",attr[exteriors[k]]);
          

}
       }
      }
   getch();
   } 

Sorting Numbers based on Weights - Zoho Programming Test question

You are given a set of numbers like <10, 36, 54,89,12>. You should find sum of weights based on the following conditions:

1. 5 if a perfect square
2. 4 if multiple of 4 and divisible by 6
3. 3 if even number

And sort the numbers based on the weight and print it as follows:
<10,its_weight>,<36,its weight><89,its weight>
The program should display the numbers in increasing order of their their weights.

#include<stdio.h>
#include<math.h>

int getWeight(int n)
{
int w=0;
float root=sqrt(n);
if(root==ceil(root))
    w+=5;
if(n%4==0&&n%6==0)
    w+=4;
if(n%2==0)
    w+=3;
return w;
}

void main()
{
int nums[15];
int ws[15];
int i,j,t,n;
printf("Enter number of numbers");
scanf("%d",&n);
printf("\nEnter numbers");
for(i=0;i<n;i++)
    scanf("%d",&nums[i]);
for(i=0;i<n;i++)
    ws[i]=getWeight(nums[i]);
printf("\nBefore sorting:\n");
for(i=0;i<n;i++)
    printf("%d:%d\t",nums[i],ws[i]);
for(i=0;i<n;i++)
    for(j=0;j<n-i-1;j++)
        if(ws[j]>ws[j+1])
            {
            t=ws[j+1];
            ws[j+1]=ws[j];
            ws[j]=t;
            t=nums[j+1];
            nums[j+1]=nums[j];
            nums[j]=t;
            }
printf("\nSorted:\n");
for(i=0;i<n;i++)
    printf("%d:%d\t",nums[i],ws[i]);
}

C Program to Validate Sudoku - Checking Correctness of Sudoku

Here we shall see a c program to validate sudoku a sudoku. The c program i have written here checks the correctness of a sudoku. The programs can be used to check sudoku solution for 9x9 sudoku. First of all, we should know what are the constraints.

• Each row should contain all numbers from 1 to 9 (inclusive)
• Each column should contain all numbers from 1 to 9 (inclusive)
• The 3x3 squares should also contain all numbers from 1 to 9 (inclusive)

If all above conditions are satisfied, the sudoku is correct. The c program to check whether a solution for a sudoku is correct is as follows:

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

void report(char *s,int i,int j)
{
printf("\nThe sudoku is INCORRECT");
printf("\nin %s. Row:%d,Column:%d",s,i+1,j+1);
getch();
exit(0);
}

void main()
{
int i,j,a[9][9];
char c;
int si,sj,flag;
printf("\nEnter the sudoku");
/*
Going to read sudoku matrix (9x9).
Since numbers 1 to 9 are single digit,
it is enough to read them as char.
To convert them from their ascii to int,
subtract ascii of '0' from the character.
*/
for(i=0;i<9;i++)
    for(j=0;j<9;j++)
    {
    scanf("%c",&c);
    a[i][j]=c-'0';
    }
/*++++++++++++++++++
checking rows
+++++++++++++++++++
we check each cell in each row.
We start with a flag 0x0000.
if 1 is found zeroth bit of flag is set.
if 2 is found, first bit is set
and so on.
If all digits 1 to 9 are present, flag's value
will be 0x01FF.
If flag is 0x01FF after traversing a row,
the row has all numbers 1 to 9.
So, it is correct.
If the flag is not 0x01FF after traversing a row,
the row is incorrectly filled.
Then we call report() function
*/
for(i=0;i<9;i++)
    {
    flag=0x0000;
    for(j=0;j<9;j++)
        flag|=1<<(a[i][j]-1);
    if(flag!=0x01FF)
        report("row",i,j-1);
    }

/*++++++++++++++++++
checking columns
+++++++++++++++++++
Just like row checking.
The flag is for a column.
*/
for(j=0;j<9;j++)
    {
    flag=0x0000;
    for(i=0;i<9;i++)
        flag|=1<<(a[i][j]-1);
    if(flag!=0x01FF)
        report("col",i-1,j);
    }
/*++++++++++++++++++
checking Squares (3x3)
+++++++++++++++++++
Just like row checking.
The flag is for a square.
*/
for(si=0;si<3;si++)
    {
    for(sj=0;sj<3;sj++)
        {
        flag=0x0000;
        for(i=0;i<3;i++)
            {
            for(j=0;j<3;j++)
                flag|=1<<(a[si*3+i][sj*3+j]-1);

            }
        if(flag!=0x01FF)
                report("square",si*3+i-1,sj*3+j-1);
        }
    }
printf("\nThe sudoku is correct");
}

To test the program, you may try the following inputs. You may copy paste a line from below sudoku solutions to the program. (Each line is a correct solution)

123456789759183426648297315374915268896372154512864973931528647265749831487631592
123456789857923164964817235386241597275639841491578623538764912642195378719382456
123456789759283614486971253342768591891542367567319428935127846278694135614835972
123456789849173256765298431586941372291735648437862915352617894978524163614389527
123456789784913652569827134316598247845271963297634815652149378938765421471382596
123456789496817235587329461864275193359184627712693854631942578978561342245738916
123456789746198532859732146298314675374569821615287394967845213481623957532971468
123456789867239145954781362392567418416928573578143926745692831281375694639814257
123456789475981362869327541654813927791642853382795614938164275516279438247538196
123456789968137524457892136892374651716285493534619872685943217279561348341728965
123456789645987312897312645972863451536124897418579236364291578289735164751648923

Program to Find Number of Grandchildren - Zoho Programming Test Question

Here we will see a c program to find number of grandchildren, great grandchildren great-great grandchildren and so-on of a given person. In this program, the input is a table with two columns, 'Child' and 'Father'. Then we enter a name whose number grandchildren, great grandchildren  etc is to be calculated. We do not have to count children. An example is:
Given a two dimensional array of strings like

<”luke”, “shaw”>
<”wayne”, “rooney”>
<”rooney”, “ronaldo”>
<”shaw”, “rooney”> 

Where in each row, the first string is “child”, second string is “Father”. And given “ronaldo” we have to find his no of grandchildren. Here “ronaldo” has total 3 grandchildren (2 grandchildren: wayne and shaw ; a great grandchild luke). So our output should be 3.

#include<stdio.h>
#include<string.h>
int n;
char name[20];

struct reln{
char child[20];
char father[20];
}r[10];

int count=0;
void countChildren(char name[])
    {
    int j;
    for(j=0;j<n;j++)
        {
        if(strcmp(name,r[j].father)==0)
            {
            count++;
            countChildren(r[j].child);
            }
        }
    }

void main()
{
int i;
printf("\nEnter the number of inputs: ");
scanf("%d",&n);
for(i=0;i<n;i++)
    {
    scanf("%s",r[i].child);
    scanf("%s",r[i].father);
    }
printf("\nEnter name of the one whose no. of grandchildren is needed: ");
scanf("%s",name);
for(i=0;i<n;i++)
    {
    if(strcmp(r[i].father,name)==0)
        countChildren(r[i].child);
    }
printf("\nNo .of grandchildren of %s=%d",name,count);
}

Program to Display String with Odd Number of Letters in the shape of letter 'X' - Zoho Programming Test Question

One of the previous questions in the programming round of Zoho recruitment process was to write a C program to display any string with odd number of letters as follows, in the shape of letter 'X'.

Print the word with odd number of letters as

P         M
 R      A
   O  R
     G
  O    R
 R       A
P          M 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void main()
{
int n,i,j,k,l;
char str[20];
printf("Enter a string with odd number of letters.");
scanf("%s",str);
if((n=strlen(str))%2==0)
    {
    printf("\nNot odd");
    exit(0);
    }

for(i=0;i<n;i++)
    {
    printf("\n");
    for(j=0;j<n;j++)
        {
        if(i==j||j==n-1-i)
            printf("%c",str[j]);
        else
            printf(" ");
        }
    }
}

C Program to Burst Consecutively Repeated Numbers From Array - Zoho Programming Round Question

This was one of the programming round (hands on coding) questions in recruitment process of Zoho, an IT company. The question is to write a c program to remove all consecutive repetition of numbers in given array. We should also keep in mind that, if we remove one set of consecutive repeated number, this removal may cause another repetition as illustrated in following example.

example array: 2  3  5  3  8  8  8 3  3 5  3  1  2

Solving: 2  3  5  3  8  8  8  3  3  5  3  1  2   ->  2  3  5  3  3  3  5  3  1  2 -> 2  3  5  5  3  1  2 -> 2  3   3  1  2   ->  2  1  2

output:  2  1  2

I hope that you understood how the removal of consecutive appearance of numbers should be. I hope the program will explain you more.

#include<stdio.h>

void main()

{
int a[20],i,j,k,n;
printf("Enter Number of elements");
scanf("%d",&n);
printf("Enter elements");
for(i=0;i<n;i++)
 scanf("%d",&a[i]);
i=0;
for(;i<n-1;)
 {
 j=1;
 while(i+j<n&&a[i+j]==a[i])
  j++;
 if(j==1)
  {
  i++;
  continue;
  }

 for(k=0;k<n-(i+j);k++)
  a[i+k]=a[i+j+k];
 n-=j;
 if(i>0)
  i--;
 }

printf("Output:\n");
for(i=0;i<n;i++)
 printf("%d",a[i]);
getch();
}