Replace the bubble sort and linear search by shell sort and

Replace the bubble sort and linear search by shell sort and binary search. The output should be as the following. Unsorted Seq: 25, 16, 92, 81, 65, 59, 48, 31, 67, 27, 14, 9.52, 38, 61, Sorted Seq: 9, 14, 16, 25, 27, 31, 38, 52, 59, 61, 65, 67, 81, 92, Input a number: 21 21 is not found Do nor ? y Input a number: 92 92 is found at position 15 Do more ? y Input a number: 45 45 is not found Do more ? y Input a number: 61 61 is found at position 11 Do more ? -

Solution

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

/*function for shell sort

This is generalization of insertion sort which allows exchange of elements that are far apart.
The idea is to arrange the list of elements so that, starting anywhere, considering every hth element gives a sorted list.
here we are taking h as 2 i.e every alternate elements in one group and other alternate elements in another group.
*/
void shell_sort(int arr[],int Size)
{
int i,skip,j,t;
for(skip = Size/2; skip>0; skip /= 2)
{
for(i=skip; i<Size; i++)
{
t = arr[i];
for(j=i; j>=skip && t<arr[j-skip]; j-=skip)
arr[j] = arr[j-skip];

arr[j] = t;
}
}
}
/* function for binary search
Important condition for binary search is \"array should always be sorted order\"

middle = (first+last)/2

first middle last
1 2 3 4 5 6 7
-- -- -- -- -- -- --

if(element ot be search < arr[middle]) range will be first and middle -1
else range will be middle+1 and last;
*/
void bin_search(int arr[],int num,int Size)
{
int first,last,middle;

first = 0;
last = Size - 1;
middle = (first + last)/2;

while(first <= last)
{
if(arr[middle] < num)
first = middle + 1;

else if(arr[middle] == num){
printf(\"\ %d is found at position %d \ \", num,middle+1);
break;
}

else
last = middle - 1;

middle = (first + last)/2;
}
if(first > last)
printf(\"\ %d is not found\ \", num);
}
int main()
{
int arr[15] = {25,16,92,81,65,59,48,31,67,27,14,9,52,38,61};
int i,num;
char ch;
printf(\"Unsorted Seq: \");
for(i=0;i<15;i++)
printf(\"%d,\",arr[i]);

shell_sort(arr,15);

printf(\"\ Sorted Seq: \");
for(i=0;i<15;i++)
printf(\"%d,\",arr[i]);

/*
In this we are using do while loop with choice(i.e. indefinite loop).
For this there will always be first execution irrespective of condition and after that condition will get checked.

here after entering choice as \'y\' we are using while to check condition.
If it matches we are executing do while() block else stopping and coming out from the loop.
*/
do{
printf(\"\ Input a number: \");
scanf(\"%d\", &num);

bin_search(arr,num,15);
printf(\"Do more <Y/N> ? \");
scanf(\"\ %c\", &ch);
}while(ch == \'y\');
return 0;
}