sorting using quicksort method(divide and conqour method ).

THE NEED:
quicksort is the fastest sort in best average case of complexity O(n logn) in worst average case it is O(n²).
the method is to choose pivot, which in my program is the index such that all number in the left of array[pivot],should be less than array[pivot]. And all number in right should be greater than array[pivot].
Rest will be done by recursion.

CODE:
#include<stdio.h>
#define max 10
void quicksort(int a[],int ,int );
int choosepivot(int a[],int ,int );
int main()
{
int a[max],first=0,last,i,n;
printf("enter lenght of array you want to sort\n");
scanf("%d",&last);
printf("enter the array\n");
for(i=0;i<last;i++){
scanf("%d",&a[i]);
}
quicksort(a,first,last-1);
for(i=0;i<last;i++)
{
printf("%d ",a[i]);
}
}
void quicksort(int a[max],int first,int last)
{
int pivot;
if(first<last)
{
pivot=choosepivot(a,first,last);
quicksort(a,first,pivot-1);
quicksort(a,pivot+1,last);
}
}
int choosepivot(int a[max],int first,int last)
{
int j,temp;
int pivot=first;
j=last;
while(j>pivot)
{
if(a[pivot]<a[pivot+1]){
pivot++;
}
else if(a[j]<a[pivot]){
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
}
else
j--;
}
return pivot;
}

APPROACH:

the function quicksort() sorts the array by dividing them on the basis of index(pivot) that's why this is called as divide and conquer approach.

the function choose pivot ,takes the pivot as first element of the array that is being called.And then check  weather the next to it is greater than the number in a[pivot],if not pivot(index) will move to the next number else it will rotate the next number with the last and moves pivot to the next index.

at last the function returns the pivot .

Vector & Matrix Algebra

#include<iostream.h>  
#include<conio.h>
#include <cstdlib>
#include <math.h>  
class vector  
 {   
 public:  
 int x,y,z;  
 void read()  
 {  
 cout<<"\n\nEnter the magnitude of i : ";  
 cin>>x;  
 cout<<"\n\nEnter the magnitude of j : ";  
 cin>>y;  
 cout<<"\n\nEnter the magnitude of k : ";  
 cin>>z;  
 }  
 vector operator -()  
 {  
 x=-x;  
 y=-y;  
 z=-z;  
 }  
 vector operator +(vector b)  
 {  
 vector c;  
 c.x=x+b.x;  
 c.y=y+b.y;  
 c.z=z+b.z;  
 return c;  
 }  
 vector operator *(vector b)  
 {  
 int prod;  
 vector c;  
 c.x=x*b.x;  
 c.y=y*b.y;  
 c.z=z*b.z;  
 prod=c.x+c.y+c.z;
 cout<<"\nInner Product = ";  
 cout<<prod;
 vector d;  
 d.x=(y*b.z)-(z*b.y);  
 d.y=(x*b.z)-(z*b.x);  
 d.z=(x*b.y)-(y*b.x);  
 return d;  
 }  
 void display()  
 {  
 cout<<x<<"i"<<"+"<<y<<"j"<<"+"<<z<<"k";  
 }  
 }; 

using namespace std;

void vecmat_mult()
{
    int mat[10][10];
    int vec[3];
    int out[10];
    int c,d,m,n,i,j;
cout<<"Enter the number of rows and columns of matrix"<<endl;
  cin>>m;
  cin>>n;
  cout<<"Enter the elements of matrix"<<endl;
  for ( c = 0 ; c < m ; c++ )
    {
 for ( d = 0 ; d < n ; d++ )
  {
 cout<<"Enter elements mat"<<c+1<<d+1<<" ";
 cin>>mat[c][d];
  }
    }

    cout<<"Enter Vector Component"<<endl;
    
  for(i=0;i<3;i++)
{
cin>>vec[i];
}

 
    for (i = 0; i < m; i++ )
{
out[i] = 0;
      for ( int j = 0; j < n; j++ )
  {
 out[i] += mat[i][j] * vec[j];
  }
      }
cout<<"Result Product is\n\n";
    for (i=0;i<m;i++)
{
cout<<out[i]<<"  "<<endl;
    }
}

void matrixmult()
{
    int m1[10][10],i,j,k,m2[10][10],mult[10][10],r1,c1,r2,c2;
    cout<<"Enter number of rows and columns of first matrix\n";
    cin>>r1>>c1;
    cout<<"Enter number of rows and columns of second matrix\n";
    cin>>r2>>c2;
    if(r2==c1)
    {
        cout<<"Enter rows and columns of First matrix \n";
        for(i=0;i<r1;i++)
            for(j=0;j<c1;j++)
                cin>>m1[i][j];
        cout<<"First Matrix is :\n";
        for(i=0;i<r1;i++)
        {
            for(j=0;j<c1;j++)
                cout<<m1[i][j]<<"\t";
            cout<<"\n";
        }
        cout<<"Enter rows and columns of Second matrix \n";
        for(i=0;i<r2;i++)
            for(j=0;j<c2;j++)
                cin>>m2[i][j];
        cout<<"Second Matrix is:\n";
        for(i=0;i<r2;i++)
        {
            for(j=0;j<c2;j++)
                cout<<m2[i][j]<<"\t";
            cout<<"\n";
        }
        cout<<"Multiplication of the Matrices:\n";
        for(i=0;i<r1;i++)
        {
            for(j=0;j<c2;j++)
            {
                mult[i][j]=0;
                for(k=0;k<r1;k++)
                    mult[i][j]+=m1[i][k]*m2[k][j];
                cout<<mult[i][j]<<"\t";
            }
            cout<<"\n";
        }
    }
    else
    {
        cout<<"Matrix multiplication cannot be done";
    }
}
void matrixtranspose()
{
int a[10][10], trans[10][10], r, c, i, j;
cout<<"Enter rows and column of matrix: "<<endl;
cin>>r>>c;
cout<<"\nEnter elements of matrix:\n";
for(i=0; i<r; ++i)
{
 for(j=0; j<c; ++j)
  {
 cout<<"Enter elements a"<<i+1<<j+1<<" ";
 cin>>a[i][j]; 
}
}
 /*Displaying the matrix a[][] */
 cout<<"\nEntered Matrix: \n"; 
 for(i=0;i<r; ++i)
  {
 for(j=0; j<c; ++j)
      { 
 cout<<a[i][j]<<"\t";
 if(j==c-1)
 cout<<"\n\n"; 
    }
  }
 
/* Finding transpose of matrix a[]
[] and storing it in array trans[][]. */ 

for(i=0; i<r; ++i)
{
 for(j=0;j<c; ++j)
  { 
    trans[j][i]=a[i][j];
       }
    }
/* Displaying the transpose,i.e, Displaying array trans[][].*/ 

cout<<"\nTranspose of Matrix:\n"; 
for(i=0; i<c; ++i)
{
 for(j=0; j<r; ++j)
  {
 printf("%d ",trans[i][j]); if(j==r-1) printf("\n\n");
  }
}
}

int main()  
 {  
 vector v1,v2,v3;  
 int choice,cont;  
 do  
 {  
 cout<<"\n\tVECTORS & MaTRIX Algebra\n\n1.Vector Addition\n\n2.Vector Product\n\n3.Product Matrix-Vector\n\n4.Product Matrix-Matrix\n\n5.Transpose Matrix\n\n6.Exit";  
 cout<<"\n\nEnter your choice : ";  
 cin>>choice;  
 switch(choice)  
 {  

 case 1 : cout<<"\n\nEnter the First Vector : ";  
            v1.read();  
            cout<<"\n\nEnter the Second Vector : ";  
            v2.read();  
            v3=v1+v2;  
            cout<<"\n\nThe Sum of Vectors : ";  
            v3.display();  
            break;  
 case 2 : cout<<"\n\nEnter the First Vector : ";  
            v1.read();  
            cout<<"\n\nEnter the Second Vector : ";  
            v2.read();  
            v3=v1*v2;  
            cout<<"\n\nCross Product = ";  
            v3.display();
            break;  
 case 3 : vecmat_mult();
   break; 

 case 4 : matrixmult();
     break;

 case 5 : matrixtranspose();
     break;

 case 6 : exit(0);
 default : cout<<"\n\nInvalid Choice";  
 }  
 cout<<"\n\n\nDo you want to continue?(1-YES,0-NO)\n";  
 cin>>cont;  
 }while(cont==1);  
 return 0;
 }

Returning a structure in C

The need:

     This program is basically solution of a problem I found on internet. Problem statement is:
There is a purse filled with some coins of gold, silver ans copper. A person draws coins one by one and notes down the type of coin each time. He writes g for gold, s for silver and c for copper coin. Thus a character string is formed. You have to write a function countCoins() which takes that string as parameter and returns count each type of coin. As we know that a function can return only single value, we have 2 options left to return all three counts with one function:
    1. store 3 answers in some contiguous location and return a pointer to that location.
    2. If possible, club all three variables to make a single variable and return that single variable. Yes it is possible, we can make a structure variable containing all three counts and return that structure variable.

The code:

----------------------------------------------------------

#include<stdio.h>
typedef struct
{
    int silver;
    int copper;
    int gold;
}CoinPurse;
CoinPurse countCoin(char *);

int main()
{
    int i;
    CoinPurse a,*b;
    char *coins="gscgcc";
    a=countCoin(coins);
    printf("Coppper coins are %d\n",a.copper);
    printf("Gold coins are %d\n",a.gold);
    printf("Silver coins are %d\n",a.silver);
    return 0;
}

CoinPurse countCoin(char *coins)
{
    CoinPurse x;
    x.copper=0;
    x.gold=0;
    x.silver=0;
    while(*coins)
    {
        switch(*coins)
        {
        case 'c':    x.copper++;
                    break;
        case 'g':    x.gold++;
                    break;
        case 's':    x.silver++;
                    break;
        default:    break;
        }
        coins++;
    }
    return x;
}

----------------------------------------------------------

Approach:
    The approach is very simple. The structure CoinPurse contains counter for each type of coin. the function countCoin() takes a character string , examines each character and based on that increments the correct counter. after the string is finished, the structure containing the counts is returned by the function countCoin(). In this program i have given the character string *coins as "gscgcc" soit is clear that there are 2 gold, 1 silver and 3 copper coins which can be verified by the program output.

Counting total number of nodes in a tree

The need:

     This program counts the total number of nodes in a binary tree and prints that for the user. This count is also known as tree size.

The code:

----------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
struct tree_node
{
 int data;
 struct tree_node *left,*right,*parent;
};
typedef struct tree_node node;
node * new_node(int x);
node * insert_node(node *root, int x);
int count_nodes(node *root);

int main()
{
 node *root=NULL;
 int i,x,max;
 printf("how many numbers do you want to enter in tree?\n");
 scanf("%d",&max);
 printf("Enter %d numbers \n",max);
 for(i=0;i<max;i++)
 {
  scanf("%d",&x);
  root = insert_node(root, x);
 }
 printf("all numbers inserted into the tree\t press enter to count");
 fflush(stdin);
 getchar();
 printf("\nThere are total %d nodes in this tree\n",count_nodes(root));
    return 0;
}

node * insert_node(node *root, int x)
{
 if(!root)
 {
  root = new_node(x);
  return root;
 }
 if(root->data > x)
  root->left = insert_node(root->left,x);
 else
  root->right = insert_node(root->right,x);
 return root;
}

int count_nodes(node *root)
{
 if(!root)
 return 0;
 else
 return(count_nodes(root->left) + 1 + count_nodes(root->right));
}

node * new_node(int x)
{
 node *furnished;
 furnished = (node*)malloc(sizeof(node));
 furnished->data=x;
 furnished->left=NULL;
 furnished->right=NULL;
 furnished->parent=NULL;
 return furnished;
}

----------------------------------------------------------

Approach:     The approach is simple. We have to go by recursion. if the root is null(means there is no tree) then number of nodes are 0. Otherwise if root is not null(the tree exists), the total number of nodes will be
       (number of nodes in left subtree + number of nodes in right subtree + 1 ) 
Here recursive function count_nodes does the job very well.

Reversing order of words in a sentence using stack

The need:

     This is another way ( a layman's approach) to write previous program about this topic. I have written the approach there too.

The code:

----------------------------------------------------------

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

struct linked_list
{
    char *chr;
    struct linked_list *next;
};
typedef struct linked_list node;
void push(node **p,char *x);
char *pop(node **p);

int main()
{
    char a[50],*temp,*dup;
    strcpy(a,"I dont know why useless programs are asked");
    node * head=NULL;
    temp=strtok(a," ");
    while(temp != NULL)
    {
        dup=strdup(temp);
        temp=strtok(NULL," ");
        push(&head,dup);
    }
    strcpy(a,"");
    while((temp=pop(&head))!=NULL)
    {
        strcat(a,temp);
        strcat(a," ");
    }
    a[strlen(a)-1]='\0';
    printf("%s\n",a);
    return 0;
}

void push(node **p,char *x)
{
    node *new_node;
    new_node=(node *)malloc(sizeof(node));
    new_node->chr=x;
    new_node->next=*p;
    *p=new_node;
}

char *pop(node **p)
{
    char *temp=NULL;
    node *tmp;
    if(*p==NULL)
        return (NULL);
    else
    {
        temp=(*p)->chr;
        tmp=*p;
        (*p)=(*p)->next;
        free(tmp);
        return (temp);
    }
}

----------------------------------------------------------

Approach:
    In that case I have made use of my stack concepts and using almost no brain I have got it done. Have a look how simple is this. Steps are:
1. read word by word (strtok has been used to read words delimiter is space)
2. keep on pushing all words on a stack till last word.
3. Now pop each word and print. :-)
Remarks:
1. This is not the most efficient method to do this. For more efficient method have a look at previous program about this topic.
2. This program can also be used to reverse the order of words in a file. In that case steps are:

1. read word by word (using fscanf(FilePointer,"%s",&TempString)).
2. keep on pushing all words on a stack till last word.
3. Now pop each word and print to another file. :-)