C Zone

Problem : Quick sort as a divide and conquer sorting algorithm.

Quicksort is a fast sorting algorithm, which is used for sorting list of data in ascending or descending order. The average complexity of sorting for a quick sort technique is O(nlogn)
Quick sort uses a technique of divide and conquer. The process consist of following steps:

1. Choose a pivot element.
2. Partition the list in two parts.
3. Quick sort two parts.

The technique as divides the list into two pivots around the pivots so is a type of divide and conquer algorithm.

Code for quick sort algorithm.


void quick_sort(int arr[],int front,int rear)
{
System.out.println("This is function");
int index = 0;
if( (rear-front+1)/2 >=1)
{
index = this.partition(arr,front,rear );
this.quick_sort(arr,0,index-1);
this.quick_sort(arr,index+1,rear);
}
}

int partition(int arr[],int front,int rear)
{
int pivot = (rear-front+1)/2;
int val = arr[pivot];
while(front val)
{
rear--;
}
if(front< rear) { int temp = arr[front]; arr[front] = arr[rear]; arr[rear] = temp; } } return front; } PS: The algorithm will work when main method is added to the algorithm.

Problem : Travelling Salesman problem using backtracking algorithm.

Code:

#include 
int x[15],used[15];
int adj[15][15]={0};
int path[15][15],wght[15];
int c,min;
int path_ok(int k,int n)
{
if(used[x[k]])
return 0;
if(k‹n-1)
return(adj[x[k-1]][x[k]]);
else
return(adj[x[k-1]][x[k]] && adj[x[k]][x[0]]);
}
void TSP(int k,int n)
{
int i,sum;
for(x[k]=1;x[k]
_________________________________________________________________________




Problem : Program to tell number of bits set in integer number.
Code:
int main(int argc, char * argv[])
{
             int number, j;
             printf("Enter any number");
             scanf("%d",&number);
           /*  Setting j to same value as number*/  
             j = number;                 
           /* Continue till number is greater than 0*/
             while(number>0)            
            {
                 /* Right shift number by one bit*/
                    number=number >> 1; 
                 /* Decrease j by amount equal to new shited value of number*/
                    j -= number;        
            }
           printf("\n The number of bits set are:%d \n",j);
}
Program : Program to reverse a linear linked list.
Code:
typedef struct node
{
    int value;
    struct node * next;
}node;


typedef struct nodestart
{
    struct node * next;
}nodestart;


node * create_node();

int main(int argc, char *argv[])
{
  int val,i=1;
  nodestart *start=NULL,* newstart=NULL;
  node * current, *previous, *temp;
  while(i==1)
  {
        temp=create_node();
        
        if(start==NULL)
        {
            start=(nodestart*)malloc(sizeof(nodestart));
            start->next=temp;
        }
        else
        {    
        current = start->next;
        while(current!=NULL)
        {
            previous=current;
            current=current->next;
        }
        previous->next=temp;
        }
        printf("Enter choice to enter(1 to continue..)");
        scanf("%d",&i);
    }   
    temp=start->next;
  
    while(temp!=NULL)
    {
        printf("%d->",temp->value);
        temp=temp->next;
    }
    temp=start->next;
  
    while(temp->next!=NULL)
    {
        previous=temp->next;
        current=previous->next;
        previous->next=temp;
        temp=previous;
    }
  
    newstart=(nodestart*)malloc(sizeof(nodestart));
    newstart->next=temp;
    
    while(temp!=NULL)
    {
        printf("%d->",temp->value);
        temp=temp->next;
    }        
        
  system("PAUSE"); 
  return 0;
}

node * create_node()
{
    int value=0;
    printf("Enter a value");
    scanf("%d",&value);
    node * temp=(node*)malloc(sizeof(node));
    temp->value=value;
    temp->next=NULL;
    return temp;
}

Mouse initialisation using Turbo C:
Bored of programming in turbo c with the programs to take input in ugly text window, with no real visual effects. So, this is a short of freaky thing that really is interesting. Adding mouse pointer to your c program is very simple. Just follow the steps given below and bingo! You are done with it.
Step 1:
Create a new c program. Now start writing code. The foremost and vital thing you require is library function 
int86(int num,union REGS *in,union REGS *out)
Step 2:
Define two variables of union REGS as in and out.
Step 3:
Now set value of in.x.ax=1.
Step 4:
Call function int86() as given below:
int86(0x33,&in,&out);
Now you are done with it. Compile and run and enjoy.
Code for mouse initialisation:
/*start of function main()*/
int main()
{
union REGS in,out;
in.x.ax=1;/*setting the value for initialising and displayimg mouse*/
int86(0x33,&in,&out);
getch(); /*given for purpose to hold*/
return 0;/*returns 0 to OS on success*/
}
/*end of main*/