/* 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