Program of sorting using shell sort #include stdio.h #de.pdf

Program of sorting using shell sort #include stdio.h #de.pdf

• 1.
  /* Program ofsorting using shell sort */ #include #define MAX 20 main() { int arr[MAX], i,j,k,n,incr; printf("Enter the number of elements : "); scanf("%d",&n); for(i=0;i=1) { for(j=incr;j= 0 && k < arr[i]; i = i-incr) arr[i+incr]=arr[i]; arr[i+incr]=k; } printf("Increment=%d ",incr); for (i = 0; i < n; i++) printf("%d ", arr[i]); printf(" "); incr=incr-2; /*Decrease the increment*/ }/*End of while*/ printf("Sorted list is : "); for (i = 0; i < n; i++) printf("%d ", arr[i]); printf(" "); }/*End of main()*/ redix sort
• 2.
  /*Program of sortingusing radix sort*/ # include # include struct node { int info ; struct node *link; }*start=NULL; main() { struct node *tmp,*q; int i,n,item; printf("Enter the number of elements in the list : "); scanf("%d", &n); for(i=0;iinfo=item; tmp->link=NULL; if(start==NULL) /* Inserting first element */ start=tmp; else { q=start; while(q->link!=NULL) q=q->link; q->link=tmp; } }/*End of for*/ printf("Unsorted list is : "); display(); radix_sort(); printf("Sorted list is : ");
• 3.
  display (); }/*End ofmain()*/ display() { struct node *p=start; while( p !=NULL) { printf("%d ", p->info); p= p->link; } printf(" "); }/*End of display()*/ radix_sort() { int i,k,dig,maxdig,mindig,least_sig,most_sig; struct node *p, *rear[10], *front[10]; least_sig=1; most_sig=large_dig(start); for(k = least_sig; k <= most_sig ; k++) { printf("PASS %d : Examining %dth digit from right ",k,k); for(i = 0 ; i <= 9 ; i++) { rear[i] = NULL; front[i] = NULL ; } maxdig=0; mindig=9; p = start ; while( p != NULL) { /*Find kth digit in the number*/
• 4.
  dig = digit(p->info,k); if(dig>maxdig) maxdig=dig; if(diglink = p ; rear[dig] = p ; p=p->link;/*Go to next number in the list*/ }/*End while */ /* maxdig and mindig are the maximum amd minimum digits of the kth digits of all the numbers*/ printf("mindig=%d maxdig=%d ",mindig,maxdig); /*Join all the queues to form the new linked list*/ start=front[mindig]; for(i=mindig;ilink=front[i+1]; else rear[i+1]=rear[i]; } rear[maxdig]->link=NULL; printf("New list : "); display(); }/* End for */ }/*End of radix_sort*/ /* This function finds number of digits in the largest element of the list */ int large_dig() { struct node *p=start ; int large = 0,ndig = 0 ; while(p != NULL) { if(p ->info > large) large = p->info; p = p->link ; } printf("Largest Element is %d , ",large);
• 5.
  while(large != 0) { ndig++; large= large/10 ; } printf("Number of digits in it are %d ",ndig); return(ndig); } /*End of large_dig()*/ /*This function returns kth digit of a number*/ int digit(int number, int k) { int digit, i ; for(i = 1 ; i <=k ; i++) { digit = number % 10 ; number = number /10 ; } return(digit); }/*End of digit()*/ Solution /* Program of sorting using shell sort */ #include #define MAX 20 main() { int arr[MAX], i,j,k,n,incr; printf("Enter the number of elements : ");
• 6.
  scanf("%d",&n); for(i=0;i=1) { for(j=incr;j= 0 &&k < arr[i]; i = i-incr) arr[i+incr]=arr[i]; arr[i+incr]=k; } printf("Increment=%d ",incr); for (i = 0; i < n; i++) printf("%d ", arr[i]); printf(" "); incr=incr-2; /*Decrease the increment*/ }/*End of while*/ printf("Sorted list is : "); for (i = 0; i < n; i++) printf("%d ", arr[i]); printf(" "); }/*End of main()*/ redix sort /*Program of sorting using radix sort*/ # include # include struct node { int info ; struct node *link; }*start=NULL;
• 7.
  main() { struct node *tmp,*q; inti,n,item; printf("Enter the number of elements in the list : "); scanf("%d", &n); for(i=0;iinfo=item; tmp->link=NULL; if(start==NULL) /* Inserting first element */ start=tmp; else { q=start; while(q->link!=NULL) q=q->link; q->link=tmp; } }/*End of for*/ printf("Unsorted list is : "); display(); radix_sort(); printf("Sorted list is : "); display (); }/*End of main()*/ display() { struct node *p=start; while( p !=NULL) { printf("%d ", p->info); p= p->link;
• 8.
  } printf(" "); }/*End ofdisplay()*/ radix_sort() { int i,k,dig,maxdig,mindig,least_sig,most_sig; struct node *p, *rear[10], *front[10]; least_sig=1; most_sig=large_dig(start); for(k = least_sig; k <= most_sig ; k++) { printf("PASS %d : Examining %dth digit from right ",k,k); for(i = 0 ; i <= 9 ; i++) { rear[i] = NULL; front[i] = NULL ; } maxdig=0; mindig=9; p = start ; while( p != NULL) { /*Find kth digit in the number*/ dig = digit(p->info, k); if(dig>maxdig) maxdig=dig; if(diglink = p ; rear[dig] = p ; p=p->link;/*Go to next number in the list*/ }/*End while */ /* maxdig and mindig are the maximum amd minimum digits of the kth digits of all the numbers*/ printf("mindig=%d maxdig=%d ",mindig,maxdig);
• 9.
  /*Join all thequeues to form the new linked list*/ start=front[mindig]; for(i=mindig;ilink=front[i+1]; else rear[i+1]=rear[i]; } rear[maxdig]->link=NULL; printf("New list : "); display(); }/* End for */ }/*End of radix_sort*/ /* This function finds number of digits in the largest element of the list */ int large_dig() { struct node *p=start ; int large = 0,ndig = 0 ; while(p != NULL) { if(p ->info > large) large = p->info; p = p->link ; } printf("Largest Element is %d , ",large); while(large != 0) { ndig++; large = large/10 ; } printf("Number of digits in it are %d ",ndig); return(ndig); } /*End of large_dig()*/
• 10.
  /*This function returnskth digit of a number*/ int digit(int number, int k) { int digit, i ; for(i = 1 ; i <=k ; i++) { digit = number % 10 ; number = number /10 ; } return(digit); }/*End of digit()*/