Skip to content

Commit 37e091a

Browse files
author
netcse
committed
first Commit
0 parents  commit 37e091a

82 files changed

Lines changed: 203479 additions & 0 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎Binary_search_merge_sort.c‎

Lines changed: 285 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,285 @@
1+
#include<stdio.h>
2+
#include<time.h>
3+
#include<math.h>
4+
#include<stdlib.h>
5+
#include<string.h>
6+
#include<ctype.h>
7+
#define MAX 50000
8+
#define max 50000
9+
10+
11+
12+
struct n
13+
{
14+
int st_index;
15+
int ed_index;
16+
int as_ds;
17+
} node[max];
18+
19+
int b[MAX],a[MAX],index1=0;
20+
21+
22+
void insert(int st_ind,int end_ind,int fl)
23+
{
24+
node[index1].st_index=st_ind;
25+
node[index1].ed_index=end_ind;
26+
node[index1++].as_ds=fl;
27+
}
28+
29+
30+
31+
void mergeAlgorithm(int Value,int index,int HighStartingIndex,int HighEndingIndx)
32+
{
33+
int lower,upper;
34+
int middle;
35+
if(Value<a[HighStartingIndex])
36+
b[index]=Value;
37+
else if(Value>a[HighEndingIndx])
38+
b[HighEndingIndx-HighStartingIndex+index+1]=Value;
39+
else
40+
{
41+
lower=0;
42+
upper=HighEndingIndx-HighStartingIndex;
43+
while(upper>lower)
44+
{
45+
middle=(upper+lower)/2;
46+
if(Value>a[middle+HighStartingIndex] && Value<a[HighStartingIndex+middle+1])
47+
break;
48+
else if(Value<a[HighStartingIndex+middle])
49+
upper=middle;
50+
else if(Value>a[middle+HighStartingIndex])
51+
lower=middle+1;
52+
}
53+
b[index+middle+1]=Value;
54+
}
55+
56+
}
57+
58+
void mergeAlgorithmDescending(int Value,int index,int HighStartingIndex,int HighEndingIndx)
59+
{
60+
int lower,upper;
61+
int middle;
62+
if(Value<a[HighEndingIndx])
63+
b[index]=Value;
64+
else if(Value>a[HighStartingIndex])
65+
b[HighEndingIndx-HighStartingIndex+index+1]=Value;
66+
else
67+
{
68+
lower=0;
69+
upper=HighEndingIndx-HighStartingIndex;
70+
while(upper>lower)
71+
{
72+
middle=(upper+lower)/2;
73+
if(Value>a[HighEndingIndx-middle] && Value<a[HighEndingIndx-middle-1])
74+
break;
75+
else if(Value<a[HighEndingIndx-middle])
76+
upper=middle;
77+
else if(Value>a[HighEndingIndx-middle])
78+
lower=middle+1;
79+
}
80+
b[index+middle+1]=Value;
81+
}
82+
83+
}
84+
int main()
85+
{
86+
87+
int i=0,n,k,j,tem,flag,first_ind,end_ind,numberOfItem=0,k1,m1;
88+
int h,p,q,r,low,high,g;
89+
double time_spent;
90+
time_t first,second;
91+
clock_t begin,end;
92+
index1=0;
93+
i=0;
94+
FILE* file = fopen ("data.txt", "r");
95+
int x = 0,count=0;
96+
fscanf (file, "%d", &x);
97+
while (!feof (file))
98+
{
99+
a[i]=x;
100+
i++;
101+
numberOfItem++;
102+
fscanf (file, "%d", &x);
103+
}
104+
printf("\nCount: %d\n",i);
105+
fclose(file);
106+
begin=clock();
107+
first_ind=0;
108+
end_ind=0;
109+
flag=0;
110+
tem=a[0];
111+
k=1;
112+
while(1)
113+
{
114+
while(1)
115+
{
116+
if(tem>=a[k]&&k<i)
117+
{
118+
end_ind=k;
119+
tem=a[k];
120+
k++;
121+
flag=1;
122+
continue;
123+
}
124+
break;
125+
}
126+
if(flag)
127+
{
128+
node[index1].st_index=first_ind;
129+
node[index1].ed_index=end_ind;
130+
node[index1++].as_ds=flag;
131+
first_ind=k;
132+
end_ind=k;
133+
tem=a[k++];
134+
}
135+
while(1)
136+
{
137+
if(tem<=a[k] && k<i)
138+
{
139+
tem=a[k];
140+
end_ind=k;
141+
flag=0;
142+
k++;
143+
continue;
144+
}
145+
break;
146+
}
147+
if(!flag)
148+
{
149+
insert(first_ind,end_ind,flag);
150+
first_ind=end_ind=k;
151+
tem=a[k++];
152+
}
153+
if(end_ind==i)
154+
break;
155+
}
156+
printf("\n");
157+
g=index1-1;
158+
h=0;
159+
while(g/2)
160+
{
161+
g/=2;
162+
h++;
163+
}
164+
printf("H=%d\n",h);
165+
h=(double)log((double)index1-1)/(double)log(2.0);
166+
printf("H=%d\n",h);
167+
p=1;
168+
for(q=0; q<=h; q++,p*=2)
169+
{
170+
for(r=0; r<index1; r++)
171+
{
172+
if(2*r*p+p>=index1)
173+
break;
174+
else
175+
{
176+
low=2*p*r;
177+
high=2*p*r+p;
178+
k=node[low].st_index;
179+
if(node[low].as_ds==0 && node[high].as_ds==0)
180+
{
181+
m1=0;
182+
for(k1=node[low].st_index; k1<=node[low].ed_index; k1++)
183+
{
184+
mergeAlgorithm(a[k1],m1++,node[high].st_index,node[high].ed_index);
185+
}
186+
m1=0;
187+
for(k1=node[high].st_index; k1<=node[high].ed_index; k1++)
188+
{
189+
mergeAlgorithm(a[k1],m1++,node[low].st_index,node[low].ed_index);
190+
}
191+
192+
}
193+
else if(node[low].as_ds==0 && node[high].as_ds==1)
194+
{
195+
196+
m1=0;
197+
for(k1=node[low].st_index; k1<=node[low].ed_index; k1++)
198+
{
199+
mergeAlgorithmDescending(a[k1],m1++,node[high].st_index,node[high].ed_index);
200+
}
201+
m1=0;
202+
for(k1=node[high].ed_index; k1>=node[high].st_index; k1--)
203+
{
204+
mergeAlgorithm(a[k1],m1++,node[low].st_index,node[low].ed_index);
205+
}
206+
207+
}
208+
209+
else if(node[low].as_ds==1 && node[high].as_ds==0)
210+
{
211+
m1=0;
212+
for(k1=node[low].ed_index; k1>=node[low].st_index; k1--)
213+
{
214+
mergeAlgorithm(a[k1],m1++,node[high].st_index,node[high].ed_index);
215+
}
216+
m1=0;
217+
for(k1=node[high].st_index; k1<=node[high].ed_index; k1++)
218+
{
219+
mergeAlgorithmDescending(a[k1],m1++,node[low].st_index,node[low].ed_index);
220+
}
221+
}
222+
223+
else if(node[low].as_ds==1 && node[high].as_ds==1)
224+
{
225+
m1=0;
226+
for(k1=node[low].ed_index; k1>=node[low].st_index; k1--)
227+
{
228+
mergeAlgorithmDescending(a[k1],m1++,node[high].st_index,node[high].ed_index);
229+
}
230+
m1=0;
231+
for(k1=node[high].ed_index; k1>=node[high].st_index; k1--)
232+
{
233+
mergeAlgorithmDescending(a[k1],m1++,node[low].st_index,node[low].ed_index);
234+
}
235+
236+
}
237+
238+
int n1=0;
239+
240+
for(k=node[low].st_index; k<=node[high].ed_index; k++)
241+
{
242+
a[k]=b[n1++];
243+
244+
}
245+
246+
node[low].ed_index=node[high].ed_index;
247+
node[high].st_index=node[low].st_index;
248+
node[low].as_ds=0;
249+
node[high].as_ds=0;
250+
memset(b,sizeof(b),0);
251+
}
252+
}
253+
}
254+
255+
end=clock();
256+
time_spent=(double)(end-begin)/CLOCKS_PER_SEC;
257+
printf("\nThe difference is: %f seconds\n",time_spent);
258+
259+
FILE *f;
260+
f = fopen("output_Binary_Search_merge_sort.txt", "w");
261+
for(k=0; k<numberOfItem; k++)
262+
{
263+
fprintf(f,"%d\n",a[k]);
264+
265+
}
266+
267+
printf("\n");
268+
269+
fclose(f);
270+
printf("output saved output_Binary_Search_merge_sort.txt");
271+
272+
end = clock();
273+
274+
275+
FILE *fp;
276+
fp = fopen("time_binary_search_merge_sort.txt", "w");
277+
fprintf(fp, "%f", time_spent);
278+
fclose(fp);
279+
280+
281+
getchar();
282+
283+
return 0;
284+
}
285+

‎Binary_search_merge_sort.exe‎

32.3 KB
Binary file not shown.

‎BubbleSort.c‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
#include <stdio.h>
2+
3+
void bubble_sort(long [], long);
4+
5+
int main()
6+
{
7+
long array[100], n, c, d, swap;
8+
9+
printf("Enter number of elements: \n");
10+
scanf("%ld", &n);
11+
12+
printf("Enter %ld integers: \n", n);
13+
14+
for (c = 0; c < n; c++)
15+
scanf("%ld", &array[c]);
16+
17+
bubble_sort(array, n);
18+
19+
printf("Sorted list in ascending order: \n");
20+
21+
for ( c = 0 ; c < n ; c++ )
22+
printf("%ld ", array[c]);
23+
24+
getchar();
25+
getchar();
26+
27+
return 0;
28+
}
29+
30+
void bubble_sort(long list[], long n)
31+
{
32+
long c, d, t;
33+
34+
for (c = 0 ; c < ( n - 1 ); c++)
35+
{
36+
for (d = 0 ; d < n - c - 1; d++)
37+
{
38+
if (list[d] > list[d+1])
39+
{
40+
/* Swapping */
41+
42+
t = list[d];
43+
list[d] = list[d+1];
44+
list[d+1] = t;
45+
}
46+
}
47+
}
48+
}

‎BubbleSort.exe‎

27.8 KB
Binary file not shown.

0 commit comments

Comments
 (0)