/*AN IMPLEMENTATION OF DATA STRUCTURE SORTING IN DECENDING FORM USING INSERTION INTO NEW ARRRAY & DO BINARY SEARCH FROM THAT ARRAY*/
#include<stdio.h>
int main()
{
int arr[5]={2,1,3,5,4};//this is old array
int arr1[5]={0};//new array in which sorted element means elements in decending form are going to be put...
int i,j,x;
for(i=0;i<5;i++)//i will represent no. of elements in old array....& compare one by one to those elements to each & every element of new array....upto value of i....means upto no. of elements are already being put into new array...
//NO. OF ELEMENTS OF OLD ARRAY WILL BE SAME AS NO. OF ELEMENTS OF NEW ARRAY...
//WE ARE GOING TO CONVERT THESE MANY NO. OF ELEMENTS INTO DECENDING ORDER
{
for(j=0;j<=i;j++)//if at last time arr[6]={0},then then arr1[6]={0}always if arr1[j]={0},so j<=i will work completely,go inside loop,and by shifting value to next position ,it will place most small value to last pos. of arr1.for this array should be declared one more as required,so last pos of arr1 always be 1.
{
if(arr1[j]<arr[i])//1ST OF ALL IN THIS CONDITION..CHECK WEITHER EITHER ELEMENT IN NEW ARRAY IS SMALL THAN OLD ARRAY OR NOT...IF SMALL IN NEW ARRAY..MEANS ELEMENT OF OLD ARRAY IS GREATER ...THEN SHIFT ALL OTHER ELEMENTS OF NEW ARRAY & PUT THIS OLD ARRAY ELEMENT WHICH IS GREATER INTO NEW ARRAY AT ONE OF THE STARTING POSITIONS WHERE OLD ARRAY ELEMENT SEEMS GREATER BY ITSELF.....SO IN THIS WAY...AT 1ST POINTS..GREATER ELEMENTS OF OLD ARRAY TAKES PLACE BY SHIFTING SMALL ELEMENTS INTO RIGHT BY ONE...MAKING THIS NEW ARRAY INTO ASCENDING ORDER
{
x=i;//THIS IS HOW SHIFTING TAKES PLACE...PLACE i into x..which is no. of old elemENT
x--;//decrement x by 1 ...bcz elements in array starts from 0 ..not 1..
for(;j<=x;x--)//j<=x means ..j representing elements of new array..means at the point where old array element is grater than all new array elements,,then shift all those new array elements to right 1 by1
{
arr1[x+1]=arr1[x];//using this loop..place element 5 to 6th position..4 to 5th..3 to 4th..2 to 3rd..1 to 2nd..move the position of all the elements that are smaller than that element which is to be inserted ...to place elements in new array in decending order...
}
arr1[j]=arr[i]; //as all the smaller elements in new array are shifted to right ...put element which is greater than all of those elements that are shifted....into its exact position..which is j..where next element is new array is found to be smaller than i element which is compared to all elements of j...
printf("\narr1[%d]=%d",j,arr1[j]);
break;//whenever assignment takes place..break from this loop..into other loop..loop of i..
}
}
/*if(arr1[j] != arr[i])
{
arr1[j-1]=arr[i];
}*/
}
for(j=0;j<=4;j++)
{
printf("\tarr1[%d]=%d",j,arr1[j]);//print all the elements of new array which will be in decending order..hence sorted
for(proceed=0;i>1;proceed++)//inti then cond check ....back......1st it inc.then check cond.
{
i=i/2;//count no. of iterations which should take in next loop while binary searching
////proceed=0 i=10 ;proceed=1 10/2=5;proceed=2 5/2=2;proceed=3 2/2=1;i<1 failed out of loop//pro=3
}
printf("\nproceed=%d",proceed);////value of procceed calculated will tell us how many no. of max.iterations will required while searching a perticular elements ;it totally depends on no. of elements r present in array..
do
{
printf("\nenter the element to be searched:");
scanf("%d",&search);
mid=0;
hi=10;lw=0;///for 2nd,3rd or more no. of element searching hi should be start by 10 & lw should be 0
mid=(hi+lw)/2;////mid =5 or again & again started from 5
for(i=0;i<proceed;i++)//loop should operate at 0,1& 2 times.
{
if(arr1[mid]>search)///1st time arr[5]>search
{
hi=mid;//if mid element is greater then element to be searched ;it means element to be searched will found in lower half part of array;then lw=0 as it is & mid is to be *made hi
mid=(lw+hi)/2;////again mid is found by adding this (lw which has old mid value to hi)/2
//printf("\nmid in if=%d",mid);
}
else if(arr1[mid]<search)//
{
lw=mid;//now func will work in else for these initialised values.
////if arr[mid] is less than element to be searched ;it means element lies in upper half part//then mid will work as lower element
mid=(lw+hi)/2;//7th pos=14//again come back at 8th pos
//printf("\nmid in else if=%d",mid);
}
if(arr1[mid]==search)//by using else if here one loop will proceed extra again by proceed=3 value.
{
printf("\nsearched at %d pos",mid);////once element is found ;;it is printed ;;no extra loop will operate..
break;
}
}
}while(search != 0);////it will 1st search 0 element in array if found it will print its pos then it will go out of while looop
