/* binary searching /*
/* binary.c */
#include
int binary_search(int array[], int value, int size)
{
int found = 0;
int high = size, low = 0, mid;
mid = (high + low) / 2;
printf("\n\nLooking for %d\n", value);
while ((! found) && (high >= low))
{
printf("Low %d Mid %d High %d\n", low, mid, high);
if (value == array[mid])
found = 1;
else if (value <>
high = mid - 1;
else
low = mid + 1;
mid = (high + low) / 2;
}
return((found) ? mid: -1);
}
void main(void)
{
int array[100], i;
for (i = 0; i <>
array[i] = i+20;
printf("Result of search %d\n", binary_search(array, 33, 100));
printf("Result of search %d\n", binary_search(array, 75, 100));
printf("Result of search %d\n", binary_search(array, 1, 100));
printf("Result of search %d\n", binary_search(array, 1001, 100));
}
/* BUBBLE SORT FOR SORTING STRINGS */
/* BUB_STR.C */
# include
# include
# include
# include
void bubble_sort(char *array[], int );
void display(char *list[], int);
void bubble_sort(char *array[], int size)
{
char *temp;
int i, j;
for (i = 0; i <>
for (j = 0; j <>
if (strcmp(array[i], array[j]) <>
{
temp =(char *) malloc(sizeof(array[i]));
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
void display(char *list[], int n)
{
int i;
for(i = 0 ; i <>
{
printf("\n %s", list[i]);
}
}
void main(void)
{
char *list[100] = {
"MONDAY", "TUESDAY", "WEDNESDAY", "FRIDAY", "SATARDAY" };
printf("\n Input list is as follows:");
display(list, 5);
bubble_sort(list, 5);
printf("\n Sorted list is as follows:\n");
display(list, 5);
}
/* bubble sorting */
/* bubble.c */
#include
#include
void bubble_sort(int array[], int size)
{
int temp, i, j;
for (i = 0; i <>
for (j = 0; j <>
if (array[i] <>
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
void main(void)
{
int values[30], i;
printf("\n Unsorted list is as follows\n");
for (i = 0; i <>
{
values[i] = rand() % 100;
printf(" %d", rand()%100);
}
bubble_sort(values, 10);
printf("\n Sorted list is as follows\n");
for (i = 0; i <>
printf("%d ", values[i]);
}
/* HEAP SORT */
/* HEAP.C */
# include
void heap_sort(int *, int );
void create_heap(int *, int);
void display(int *, int);
/* Definition of the function */
void create_heap(int list[], int n )
{
int k, j, i, temp;
for(k = 2 ; k <= n; ++k)
{
i = k ;
temp = list[k];
j = i / 2 ;
while((i > 1) && (temp > list[j]))
{
list[i] = list[j];
i = j ;
j = i / 2 ;
if ( j <>
j = 1 ;
}
list[i] = temp ;
}
}
/* End of heap creation function */
/* Definition of the function */
void heap_sort(int list[], int n)
{
int k, temp, value, j, i, p;
int step = 1;
for(k = n ; k >= 2; --k)
{
temp = list[1] ;
list[1] = list[k];
list[k] = temp ;
i = 1 ;
value = list[1];
j = 2 ;
if((j+1) <>
if(list[j+1] > list[j])
j ++;
while((j <= ( k-1)) && (list[j] > value))
{
list[i] = list[j];
i = j ;
j = 2*i ;
if((j+1) <>
if(list[j+1] > list[j])
j++;
else
if( j > n)
j = n ;
list[i] = value;
} /* end of while statement */
printf("\n Step = %d ", step);
step++;
for(p = 1; p <= n; p++)
printf(" %d", list[p]);
} /* end for loop */
}
/* Display function */
void display(int list[], int n)
{
int i;
for(i = 1 ; i <= n; ++ i)
{
printf(" %d", list[i]);
}
}
/* Function main */
void main()
{
int list[]={ 0,10,23,64,21,74,95,2,59,44,87,55};
int i, size = 11 ;
clrscr();
/* printf("\n Size of the list: %d", size);
for(i = 1 ; i <= size ; ++i)
{
list[i] = rand() % 100;
}*/
printf("\n Entered list is as follows:\n");
display(list, size);
create_heap(list, size);
printf("\n Heap\n");
display(list, size);
printf("\n\n");
heap_sort(list,size);
printf("\n\n Sorted list is as follows :\n\n");
display(list,size);
getch();
}
/* INSERTION SORT */
/* INSERS.C */
# include
# include
int key;
int insertion_sort(int *);
// prototype
void display(int *, int);
/* Definition of the insertion sort function */
int insertion_sort(int list[])
{
int i = 0;
int j, k ;
printf("\nElement to be inserted Break condition is -0 : ");
scanf("%d", &key);
printf("\n Selected Element is: %d", key);
while(key != -0 ) /* -0 is break condition */
{
k = i - 1;
while((key <>= 0))
{
list[k+1] = list[k];
--k;
}
list[k+1] = key ;
printf("\n List after inserting an element ");
for(j = 0 ; j<=i; j++)
printf(" %d", list[j]);
printf("\n Element to be inserted Break condition is -0: ");
scanf("%d", &key);
printf("\n Selected Element is: %d", key);
i ++;
}
return i;
}
/* End of the insertion sort function */
/* Definition of the function */
void display(int list[], int n)
{
int j;
printf("\n Final sorted list is as follows:\n");
for(j = 0 ; j <>
printf(" %d", list[j]);
}
/* End of the display function */
void main()
{
int list[200];
int n ;
n = insertion_sort(list);
display(list,n);
}
/* insert sort */
# include
# include
void insertion_sort(int *, int);
void display(int*, int);
void insertion_sort(int l[], int n)
{
int pointer, temp;
int i, k;
l[0] = -0;
for(i = 1 ; i <= n; i++)
{
pointer = i -1;
temp = l[i];
while(temp <>
{
l[pointer+1] = l[pointer];
pointer --;
}
l[pointer+1] = temp;
printf("Step = %d", i);
for(k = 0; k <= n; k++)
printf(" %d", l[k]);
printf("\n");
}
}
void display(int l[], int n)
{
int i;
printf("\n Sorted list is as follows\n");
for(i = 1; i <= n; i++)
printf(" %d", l[i]);
}
void main()
{
int number;
int list[100];
int i;
printf("How msny numbers you want in sortlist:");
scanf("%d",number);
printf("\n Number of elements in the list: %i", number);
printf("\n Unsorted list is as follows \n");
for(i = 1; i <= number; i++)
{
list[i] = rand() %100;
printf(" %d", rand() %100);
}
printf("\n");
printf("\n Step wise result is as follows \n\n");
insertion_sort(list,number);
display(list, number);
}
/* MERGE SORT */
/* merge.c */
# include
# include
void merge_sort(float *, int , int , int );
void merge_pass(float *, int , int );
/* Definition of the function */
void merge_sort(float l[], int top, int size, int bottom)
{
float temp[1000];
int f = top;
int s = size +1 ;
int t = top ;
int upper;
while(( f <= size)&&(s <=bottom))
{
if(l[f] <= l[s])
{
temp[t] = l[f] ;
f ++;
}
else
{
temp[t] = l[s] ;
s ++;
}
t ++;
}
if(f <=size)
{
for(f = f ; f<=size; f++)
{
temp[t] = l[f];
t++;
}
}
else
{
for(s = s ; s<= bottom ; s++)
{
temp[t]=l[s];
t++;
}
}
for(upper = top; upper <= bottom ; upper++)
{
l[upper]=temp[upper];
}
}
/* Definition of the function */
void merge_pass( float append[], int m, int n )
{
if( m!= n)
{
int mid = (m+n)/2;
merge_pass( append, m, mid );
merge_pass( append, mid+1, n );
merge_sort( append, m, mid, n );
}
}
/* main function */
void main()
{
float list[1000];
int i, n = 30;
printf("\n Size of the list: %d", n);
for(i = 0 ; i <>
{
list[i] = (float) (rand() %100);
}
printf("\n Entered list as follows:\n");
for( i = 0 ; i
printf(" %d ", (int) list[i]);
i = 0 ;
merge_pass(list, i, n-1);
printf("\n Merge sorted list is as follows:\n");
for( i = 0 ; i
printf(" %d", (int) list[i]);
}
/* SIMPLE MERGE SORT */
/* MERGES.C */
# include
int merge_sort( int , int *, int , int *, int * );
int bubble_sort(int , int *);
/* Definition of function */
bubble_sort(int n, int l[])
{
int flag = 1 ;
int i, j, k, temp;
for(j = 0 ; j<>
{
for(k = 0 ; k< n - j - 1 ; k++)
{
if(l[k] > l[k+1])
{
temp = l[k];
l[k] = l[k+1];
l[k+1] = temp ;
flag = 0;
}
}
if(flag)
break ;
else
flag = 1;
}
printf("\n Entered list as follows in");
printf("\n Ascending order: ");
for(i = 0 ; i <>
printf(" %d", l[i]);
return 0 ;
}
/* Definition of function */
merge_sort( int n, int list_a[], int m ,
int list_b[], int result_list[] )
{
int i = 0;
int j = 0;
int k = 0;
int ch, l;
/* Repeat the process until the elements of list_a and list_b are exhausted */
while((i <>
{
if(list_a[i] <>
{
result_list[k] = list_a[i];
i++;
k++;
} /* end of if statement */
else
if(list_a[i] > list_b[j])
{
result_list[k] = list_b[j];
j++;
k++;
} /* end of if statement */
else
{
result_list[k] = list_a[i];
i++;
j++;
k++;
} /* end of else statement */
printf("\n");
for(ch = 0; ch <>
printf(" %d", result_list[ch]);
} /* end of while statement */
/* checks if size of list_a larger than list_b
copy rest of the elements of list_a into result_list */
if(i
{
for(l = i ; l
{
result_list[k] = list_a[i];
i++;
k++;
printf("\n");
for(ch = 0; ch <>
printf(" %d", result_list[ch]);
}
}
else
/* checks if size of list_b larger than list_a
copy rest of the elements of list_b into result_list */
if(j <>
{
for(l = j; l
{
result_list[k] = list_b[j];
j++;
k++;
printf("\n");
for(ch = 0; ch <>
printf(" %d", result_list[ch]);
}
}
return (k);
}
/* function main */
void main()
{
int list_a[100],list_b[100];
int result[200];
int n, m, k, i;
printf("\n Input the number of elements of list_a: ");
scanf("%d", &n);
for(i = 0; i
{
printf("\n Input the element: %d: ", i+1);
scanf("%d", &list_a[i]);
}
/* Sort the elements of list_a */
bubble_sort(n, list_a);
/* End of sorting */
printf("\n Input the number of elements of list_b:");
scanf("%d", &m);
for(i = 0 ; i<>
{
printf("\n Input the element: %d: ", i+1);
scanf("%d", &list_b[i]);
}
/* Sort the elements of list_b */
bubble_sort(m, list_b);
/* End of sorting */
k = merge_sort( n, list_a, m , list_b, result);
printf("\n Duplicates are : %d", m+n-k);
printf("\n");
printf("\n Sorted list is as follows:\n");
for(i = 0 ; i<>
{
printf(" %d", result[i]);
}
}
/* quick sort */
/* quick.c */
#include
#include
void quick_sort(int array[], int first, int last)
{
int temp, low, high, list_separator,i;
low = first;
high = last;
list_separator = array[(first + last) / 2];
do {
while (array[low] <>
low++;
while (array[high] > list_separator)
high--;
if (low <= high)
{
temp = array[low];
array[low++] = array[high];
array[high--] = temp;
}
} while (low <= high);
for (i = 0; i <>
printf("%d ", array[i]);
printf("\n");
getch();
if (first <>
quick_sort(array, first, high);
if (low <>
quick_sort(array, low, last);
}
void main(void)
{
int values[]={10,23,64,21,74,95,2,59,44,87,55}, i;
clrscr();
for (i = 0; i <>
printf("%d ", values[i]);
printf("\n");
/* printf("\n Unsorted list is as follows \n");
for (i = 0; i <>
{
values[i] = rand() % 100;
printf(" %d", rand() %100);
}*/
quick_sort(values, 0, 10);
printf("\n Sorted list as follows\n");
for (i = 0; i <>
printf("%d ", values[i]);
getch();
}
/* RADIX SORT */
/* RADIX.C*/
# include
# include
# include
struct node
{
int data ;
struct node *next;
};
typedef struct node node1;
node1 *first;
node1 *pocket[100], *pocket1[100];
void create_node(node1 *, int);
void display(node1 *);
node1 *radix_sort(node1 *);
int large(node1 * );
int numdig(int );
int digit(int , int);
void update(int, node1 *);
node1 *Make_link(int, node1 *);
/* This function create nodes and take input data */
void create_node(node1 *rec, int n)
{
int i, j, k;
for(i = 0 ; i<>
{
rec->next = (node1 *) malloc(sizeof(node1));
printf("\n First node value: %d: ", i);
scanf("%d", &rec->data);
rec = rec->next;
}
rec->data = NULL;
rec->next = NULL;
}
/* Output Function */
void display(node1 *rec)
{
while(rec != NULL)
{
printf(" %d", rec->data);
rec= rec->next;
}
}
/* This radix sort function */
node1 *radix_sort(node1 *rec)
{
node1 *r, *nex;
int poc = 0 ;
int i, j, k;
int larg = large(rec);
int m = numdig(larg);
/* These statements create pockets */
for(k = 0 ; k <>
{
pocket[k] = (node1 *)malloc(sizeof(node1));
pocket1[k] = (node1 *)malloc(9*sizeof(node1));
}
/* These statements initialize pockets */
for(j = 1; j <= m ; j++)
{
for(i = 0 ; i <>
{
pocket[i] = NULL;
pocket1[i] = NULL ;
}
r = rec ;
while(r != NULL)
{
int dig = digit(r->data, j);
nex = r->next ;
update(dig,r);
r = nex;
}
if(r!= NULL)
{
int dig = digit(r->data,j);
update(dig,r);
}
while(pocket1[poc] == NULL)
poc ++;
rec = Make_link(poc, rec);
}
return(rec);
}
/* This function finds largest number in the list */
int large(node1 *rec)
{
node1 *save ;
int p = 0;
save = rec ;
while(save != NULL)
{
if(save ->data > p)
{
p = save->data;
}
save = save->next ;
}
printf("\n Largest element: %d", p);
return(p);
}
/* This Function finds number digits in a number */
int numdig(int large)
{
int temp = large ;
int num = 0 ;
while(temp != 0)
{
++num ;
temp = temp/10 ;
}
printf("\n Number of digits of the number %d is %d\n", large, num);
return(num);
}
/* This function scarve a number into digits */
int digit(int num, int j)
{
int dig, i, k;
int temp = num ;
for(i = 0 ; i <>
{
dig = temp % 10 ;
temp = temp / 10 ;
}
printf("\n %d digit of number %d is %d", j, num, dig);
return(dig);
}
/* This function updates the pockets value */
void update(int dig, node1 *r)
{
if(pocket[dig] == NULL)
{
pocket[dig] = r ;
pocket1[dig] = r ;
}
else
{
pocket[dig]->next = r ;
pocket[dig] = r ;
}
r->next = NULL;
}
/* This function create links between the nodes */
node1* Make_link(int poc , node1 *rec)
{
int i, j, k;
node1 *pointer;
rec = pocket1[poc];
for(i = poc +1 ; i<>
{
pointer = pocket[i-1];
if(pocket[i] != NULL)
pointer->next= pocket1[i];
else
pocket[i] = pointer ;
}
return(rec);
}
/* Main function */
void main()
{
node1 *start, *pointer;
int number;
printf("\n Input the number of elements in the list:");
scanf("%d", &number);
start = (node1 *)malloc(sizeof(node1));
create_node(start, number);
printf("\n Given list is as follows \n");
display(start);
start = radix_sort(start);
printf("\n Sorted list is as follows:\n");
display (start);
}
/* select.c */
/* selection sort */
#include
#include
void selection_sort(int array[], int size)
{
int temp, current, j;
for (current = 0; current <>
for (j = current + 1; j <>
if (array[current] > array[j])
{
temp = array[current];
array[current] = array[j];
array[j] = temp;
}
}
void main(void)
{
int values[30], i;
clrscr();
printf("\n Unsorted list is as follows \n");
for (i = 0; i <>
{
values[i] = rand() % 100;
printf(" %d", rand() %100);
}
selection_sort(values, 30);
printf("\n Sorted list is as follows \n");
for (i = 0; i <>
printf("%d ", values[i]);
getch();
}
/* SELECTION SORT */
/* selects.c */
# include
int selection_sort(int , int *); /* Prototype */
void main()
{
int number, list[200];
int i;
clrscr();
printf("Input the number of elements in the list:");
scanf("%d", &number);
printf("\n Number of elements in the list is: %d", number);
printf("\nInput the elements of the list\n");
for(i = 0 ; i <>
scanf("%d", &list[i]);
selection_sort( number, list);
}
/* Definition of function */
int selection_sort(int n, int l[])
{
int min ;
int k, index;
for(index = 0; index<>
{
min = index ;
for(k = index + 1; k <>
{
if(l[min] > l[k])
min = k ;
}
if( min != index)
{
int temp = l [index];
l[index] = l[min];
l[min] = temp ;
}
}
printf("\n Entered list is as follows:\n");
for( index = 0 ; index <>
printf(" %d", l[index]);
getch();
return 0;
}
/* shell.c */
/* shell sort */
#include
#include
void shell_sort(int array[], int size)
{
int temp, gap, i, exchange_occurred;
gap = size / 2;
do {
do {
exchange_occurred = 0;
for (i = 0; i <>
if (array[i] > array[i + gap])
{
temp = array[i];
array[i] = array[i + gap];
array[i + gap] = temp;
exchange_occurred = 1;
}
} while (exchange_occurred);
} while (gap == gap / 2);
}
void main(void)
{
int values[50], i;
printf("\n Unsorted list is as follows \n");
for (i = 0; i <>
{
values[i] = rand() % 100;
printf(" %d", rand() %100);
}
shell_sort(values, 50);
printf("\n Sorted list is as follows \n");
for (i = 0; i <>
printf("%d ", values[i]);
}
No comments:
Post a Comment