/*
Title: a) Sort the set of strings in ascending order using Bubble sort and descending order by using Selection sort.
 b) Search for particular string using binary search.
 */

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

int accept(char s[10][10])
{
int i,n;
printf("\nEnter no of Strings: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nEnter String[%d]: ",i+1);
scanf("%s",&s[i]);
}
return n;
}

void display(char s[10][10],int n)
{
int i;
for(i=0;i<n;i++)
printf("\t%s",s[i]);
}

void bubble(char s[10][10],int n)
{
int pass,i; //int f;
char temp[10];
for(i=1;i<n;i++) //for(pass=1;pass<n && f ;pass++)
{
//f=0;
for(j=0;j<n-i;j++)
{
if( strcmp(s[j],s[j+1]) >0 )
{
strcpy(temp,s[i]);
strcpy(s[i],s[i+1]);
strcpy(s[i+1],temp);
//f=1;
}
}
printf("\nPASS %d:: ",pass);
display(s,n);
}
// display(s,n);
}



void sel(char s[10][10],int n)
{
int i,j,max;
char temp[10];
for(i=0;i<n-1;i++)//passes
{
max=i;
for(j=i+1;j<n;j++)
{
if(strcmp(s[max],s[j])<0)
max=j;
}
if(i<max)
{
strcpy(temp,s[max]);
strcpy(s[max],s[i]);
strcpy(s[i],temp);
}
printf("\nPASS %d:: ",i+1);
display(s,n);
}
}

int b_search(char s[10][10],int n,char *x)
{
int l=0,h=n-1,m;
while(l<=h)
{
m=(l+h)/2;
if(strcmp(s[m],x)==0)
return m;
else if(strcmp(x,s[m])<0)
h=m-1;
else
l=m+1;
}
return -1;
}

int main()
{
int a[10],n=0,ch,i;
char s[10][10],x[10];
s[0][0]='\0';
while(1)
{
system("clear");
printf("\n***********MENU*************");
printf("\n1.Bubble sort\n2.Selection sort\n3.Binary Search");
printf("\n4.Exit\nEnter ur Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
n=accept(s);
system("clear");
printf("\n***BUBBLE SORT***");
printf("\nBefore Sort: ");
display(s,n);

printf("\n");
bubble(s,n);
printf("\n");

printf("\n\nAftre sort: ");
display(s,n);
getchar();
break;

case 2:
n=accept(s);
system("clear");
printf("\n***SELECTION SORT***");
printf("\nBefore Sort: ");
display(s,n);

printf("\n");
sel(s,n);
printf("\n");

printf("\nAftre sort: ");
display(s,n);
getchar();
break;
case 3:
n=accept(s);
bubble(s,n);
printf("\nStrings are: ");
display(s,n);

printf("\n\n\nEnter String to find: ");
scanf("%s",x);
i=b_search(s,n,x);
if(i==-1)
printf("\nString not found");
else
printf("\n%s is found at pos[%d]",x,i);
getchar();
break;
case 4:exit(0);
}
getchar();
}
return 0;
}


//END OF PROGRAM