You cannot copy content of this page.

Daily Archive December 15, 2012

Search – Indexed Sequential Search


Indexed Sequential Search:

In this searching technique, first of all an index file is created that contains references to a group of records, once an index is obtained, the partial searching takes less time since it is to be located in the group/bucket specified by the index.  The program given below creates an index file for the employee records by grouping the records and then locates the required key by searching the index first and then returns the required record.  The program to implement indexed sequential search is given below:

/*Indexed Sequential Search*/

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

#define MAX 10

struct mainfile
{int empid;
char name[25];
float basic;
};

struct indexfile
{int index_id;
int kindex;
};

void main()
{
struct mainfile fobj[MAX];
struct indexfile index[MAX];
int i,num,low,high,ct=4;
float basicsal;
clrscr();
for(i=0;i<MAX;i++)
{
printf(“\nEnter employee id?”);
scanf(“%d”,&fobj[i].empid);
printf(“\nEnter name?”);
scanf(“%s”,fobj[i].name);
printf(“\nEnter basic?”);
scanf(“%f”,&basicsal);
fobj[i].basic=basicsal;
}
printf(“\nNow creating index file…!”);
for(i=0;i<(MAX/5);i++)
{index[i].index_id=fobj[ct].empid;
index[i].kindex = ct;
ct=ct+5;
}

printf(“\n\nEnter the empid to search?”);
scanf(“%d”,&num);
for(i=0;(i<MAX/5) && (index[i].index_id<=num);i++);
low=index[i-1].kindex;
high=index[i].kindex;
for(i=low;i<=high;i++)
{if(num==fobj[i].empid)
{
printf(“\nThe record is: \n\t”);
printf(“\nEmpid: %d”,fobj[i].empid);
printf(“\nName: %s”,fobj[i].name);
printf(“\nBasic: %f”,fobj[i].basic);
getch();
return;
}
}
printf(“\nNumber not found…!”);
return;
}

 

Tags,

Sorting on multiple keys

Sorting on multiple keys

The sorting algorithm may be applied on multiple keys such that if first field contains duplicate values, then sorting is done on a secondary field and so on. However, if the first field contains unique values, then sorting is not applied on secondary field.  Say for example:

The input for the combination {studentname, feeamt}

{ (xyz,3000), (abc,1000), (xyz, 1000), (abc,3000)}; will result in the following output:

{ (abc,1000), (abc,3000), (xyz,1000), (xyz,3000) }.

Program to implement sorting on student names entered by the user followed by feeamt, such that wherever name is same, sorting is applicable on feeamt field is given below:

/*Sorting on multiple keys*/

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

#define MAX 5

struct student
{char name[25];
int feeamt;
};

void sort_multiplekeys(struct student[]);

void main()
{
struct student s[MAX];
int i;
clrscr();
for(i=0;i<MAX;i++)
{printf(“\nEnter name?”);
scanf(“%s”,s[i].name);
printf(“Enter fee amount?”);
scanf(“%d”,&s[i].feeamt);
}
sort_multiplekeys(s);
printf(“\nOutput sorted on name followed by feeamt:\n\n”);
for(i=0;i<MAX;i++)
{printf(“\nName = %s”,s[i].name);
printf(“\nFeeamt = %d”,s[i].feeamt);
}
}
void sort_multiplekeys(struct student s[])
{
int i,j;
char temp[25];
float x;
clrscr();
/*loop to arrange names in ascending order*/
for(i=0;i<MAX-1;i++)
for(j=i+1;j<MAX;j++)
{if(strcmp(s[i].name,s[j].name)>0)
{
/*swapping names*/
strcpy(temp,s[i].name);
strcpy(s[i].name,s[j].name);
strcpy(s[j].name,temp);

/*swapping feeamt*/
x=s[i].feeamt;
s[i].feeamt = s[j].feeamt;
s[j].feeamt = x;
}
}
/*loop to arrange second field-feeamt in ascending order*/
for(i=0;i<MAX-1;i++)
for(j=i+1;j<MAX;j++)
{if(strcmp(s[i].name,s[j].name)==0)
{if(s[i].feeamt>s[j].feeamt)
{
/*swapping feeamt*/
x=s[i].feeamt;
s[i].feeamt=s[j].feeamt;
s[j].feeamt=x;
}
}
}
}

 

Tags,

Sorting – Address Calculation Sort (Hashing)

Sorting – Address Calculation Sort (Hashing)

  • In this method a function f is applied to each key.
  • The result of this function determines into which of the several subfiles the record is to be placed.
  • The function should have the property that: if x <= y ,  f (x) <= f (y), Such a function is called order preserving.
  • An item is placed into a subfile in correct sequence by placing sorting method – simple insertion is often used.

Example:

25         57         48         37         12         92         86         33

Let us create 10 subfiles.  Initially each of these subfiles is empty.  An array of pointer f(10) is declared, where f(i) refers to the first element in the file, whose first digit is i.  The number is passed to hash function, which returns its last digit (ten’s place digit), which is placed at that position only, in the array of pointers.

num=    25         –           f(25) gives 2
57         –           f(57) gives 5
48         –           f(48) gives 4
37         –           f(37) gives 3
12         –           f(12) gives 1
92         –           f(92) gives 9
86         –           f(86) gives 8
33         –           f(33) gives 3 which is repeated.

Thus it is inserted in 3rd subfile (4th)  only, but must be checked with the existing elements for its proper position in this subfile.

Address Calculation Sort

Arrangement of nodes in subfiles

Efficiency:  If all the elements (n) are uniformly distributed over m subfiles then n/m is approximately 1, time of the sort is near O(n).

On the other hand if maximum elements accommodate in one or two subfiles, then n/m is much larger significant work is required to insert its proper subfile at its proper position and efficiency is O(n2).

Program to implement Address Calculation Sort:

/*Address Calculation Sort*/
/*It uses a hash function that can sort only 2 digit nos.*/

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

#define MAX 5

struct list
{int info;
struct list *next;
}*node[10]={NULL};

struct list *create()
{
struct list *temp=(struct list *)malloc(sizeof(struct list));
if(temp==NULL)
{printf(“\nMemory Allocation Error!”);
exit(1);
}
return temp;
}

struct list *makenode(int num)
{
struct list *temp;
temp=create();
temp->info=num;
temp->next=NULL;
return temp;
}

struct list *insert(struct list *s,int num)
{
struct list *ptr,*temp;
ptr=s;
temp=makenode(num);
if(s==NULL)
s=temp;
else
{
/*code for placing new node at appropriate
position in the subfile*/
while((ptr->next->info<=num) && (ptr->next!=NULL))
{ptr=ptr->next;
}
if(temp->info<ptr->info)
{temp->next=ptr;
s=temp;
}
else
{temp->next=ptr->next;
ptr->next=temp;
}
}
return s;
}

/*A hash function that operates upon two digit
numbers only*/

int hashfun(int n)
{return (n/10);
}

void addr_calc(int arr[],int size)
{
int i,j=0,pos;
for(i=0;i<size;i++)
{pos=hashfun(arr[i]);
node[pos]=insert(node[pos],arr[i]);
}
for(i=0;i<10;i++)
{while(node[i]!=NULL)
{arr[j++]=node[i]->info;
node[i]=node[i]->next;
}
}
printf(“\nSorted output is: “);
for(i=0;i<size;i++)
printf(“%d\t”,arr[i]);
getch();
}

void main()
{
int arr[MAX],i,n;
clrscr();
printf(“Enter total numbers to sort?”);
scanf(“%d”,&n);
printf(“Enter numbers?”);
for(i=0;i<n;i++)
scanf(“%d”,&arr[i]);
addr_calc(arr,n);
}

 

Tags,

Sorting – Quick Sort (Partition Exchange Sort)

Sorting – Quick Sort (Partition Exchange Sort)

Suppose x be an array, n is the number of elements.  Choose an element from a specific position within the array.  Array x is partitioned so that y is placed into position j, and the following conditions hold:

1)      Each of the elements in position 0 through (j-1) is less than or equal to y.
2)      Each of the elements in position (j+1) through (n-1) is greater than or equal to y.

Example:

Let key element = lb = arr[0] = 14

Now i will move forward until arr[i] becomes greater than key value.  Finally i is positioned at 15.

Similarly j shifts backward until arr[j] becomes lower than key value.  Finally j is positioned at 11.

Now, swap(arr[i],arr[j]);

Now the same set of routines are again called with new values of i and j i.e. lb and ub.

Now i is positioned at 15, since 8 is less than 14.  Similarly j is positioned at 8.

Now i<=j condition is false i.e. upper bound is lower than lower bound which must be higher.

Now swap(arr[j],key);

Then all smaller values (for  key) are aligned to left and greater values to right.  Now partition it in two parts (8,7,3,11) and (15,16,25).  Repeat the same process again.  Finally combine all segments – (left, key, right) to obtain sorted array.

Program to implement Quicksort:

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

#define MAX 10

void quicksort(int arr[],int lb,int ub);
int partition(int arr[],int lb,int ub);

void main()
{
int arr[MAX],i,n,keyelement,lb,ub;
clrscr();
printf(“\nEnter total number of elements?”);
scanf(“%d”,&n);
printf(“\nEnter elements?”);
for(i=0;i<n;i++)
{scanf(“%d”,&arr[i]);
}
keyelement = arr[0];
lb=0;
ub=(n-1);
quicksort(arr,lb,ub);
printf(“\nSorted Array is: “);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}

void quicksort(int arr[],int lb,int ub)
{
int j;
if(lb>=ub)
return;
j=partition(arr,lb,ub);
quicksort(arr,lb,j-1);
quicksort(arr,j+1,ub);
return;
}

int partition(int arr[],int lb,int ub)
{
int a,down,temp;
a=arr[lb];
down=lb;
while(lb<ub)
{while((arr[lb]<=a) && (lb<ub))
lb++;
while(arr[ub]>a)
ub–;
if(lb<ub)
{temp=arr[lb];
arr[lb]=arr[ub];
arr[ub]=temp;
}
}
temp=arr[ub];
arr[ub]=a;
arr[down]=temp;
return ub;
}

 

Tags,

x Close

Like Us On Facebook