Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include <windows.h>
- #include <time.h>
- struct tdien
- {
- char en[30];
- };
- void Hoanvi(tdien &a,tdien &b)
- {
- tdien t;
- t=a;a=b;b=t;
- }
- void LocTA(tdien *td, int &x)
- {
- char str[300];
- char* str1,*str2;
- FILE *ds;
- ds = fopen("va.dd","rt");
- while (fgets(str,300,ds)>0)
- {
- str1 = strstr(str,"##");
- if (str1!=NULL)
- {
- str2 = strstr(str1,"|-");
- if (str2!=NULL && strlen(str2)<=17 && strlen(str2)>4)
- {
- strcpy(td[x].en,str2+3);
- x++;
- }
- }
- }
- fclose(ds);
- }
- void TuDientxt(tdien td[], int x)
- {
- FILE *tudien;
- LocTA(td,x);
- tudien = fopen("tudien.txt","w");
- for(int i=0;i<x;i++)
- {
- fputs(td[i].en,tudien);
- fflush (tudien);
- }
- fclose(tudien);
- }
- void writetofile2 (FILE *f, tdien b[], int n)
- {
- for (int i=0; i<n;i++)
- {
- fputs (b[i].en,f);
- fflush (f);
- }
- }
- void QuickSort (tdien a[], int left, int right)
- {
- int i,j;
- char x[30];
- strcpy (x,a[(left+right)/2].en);
- i=left;
- j=right;
- while (i<j)
- {
- while ( strcmp(a[i].en,x) <0 ) i++;
- while (strcmp (a[j].en,x) >0 ) j--;
- if (i<=j)
- {
- Hoanvi(a[i],a[j]);
- i++;
- j--;
- }
- }
- if (left <j)
- QuickSort(a,left,j);
- if (i < right)
- QuickSort(a,i,right);
- }
- void BubbleSort (tdien a[], int n)
- {
- int i,j;
- for( i=0; i<n-1;i++)
- for (j=n-1;j>i;j--)
- {
- if ( strcmp (a[j].en,a[j-1].en) < 0 )
- Hoanvi(a[j],a[j-1]);
- }
- }
- void ShakerSort (tdien a[],int n)
- {
- int j;
- int left, right,k;
- left =0;
- right = n-1;
- k=n-1;
- while (left < right)
- {
- for (j=right; j>left; j--)
- if ( strcmp (a[j].en,a[j-1].en) < 0)
- {
- Hoanvi(a[j],a[j-1]);
- k=j;
- }
- left =k;
- for (j=left; j < right; j++)
- if (strcmp (a[j].en, a[j+1].en) > 0 )
- {
- Hoanvi(a[j],a[j+1]);
- k=j;
- }
- right = k;
- }
- }
- void InterchangeSort (tdien a[], int n)
- {
- int i,j;
- for (i=0;i<n;i++)
- for (j=i+1; j<n; j++)
- if ( strcmp (a[j].en,a[i].en) < 0)
- Hoanvi(a[j],a[i]);
- }
- void Heapify(tdien a[], int n, int i)
- {
- int Left = 2 * (i + 1) - 1;
- int Right = 2 * (i + 1);
- int Largest;
- if (Left<n && (strcmp(a[Left].en, a[i].en ) > 0))
- Largest = Left;
- else
- Largest = i;
- if (Right<n && (strcmp(a[Right].en, a[Largest].en) > 0))
- Largest = Right;
- if (i != Largest)
- {
- Hoanvi(a[i], a[Largest]);
- Heapify(a, n, Largest);
- }
- }
- void BuildHeap(tdien a[], int n)
- {
- for (int i = n / 2 - 1; i >= 0; i--)
- Heapify(a, n, i);
- }
- void HeapSort(tdien a[], int n)
- {
- BuildHeap(a, n);
- for (int i = n - 1; i > 0; i--)
- {
- Hoanvi(a[0], a[i]);
- Heapify(a, i, 0);
- }
- }
- void BinsertionSort(tdien a[], int n)
- {
- int l, r, m, i;
- char s[30];
- for (int i = 1; i < n; i++)
- {
- strcpy(s, a[i].en);
- l = 0;
- r = i - 1;
- while (l <= r)
- {
- m = (l + r) / 2;
- if (strcmp(s, a[m].en) < 0)
- {
- r = m - 1;
- }
- else
- {
- l = m + 1;
- }
- }
- for (int j = i - 1; j >= l; j--)
- {
- strcpy(a[j + 1].en, a[j].en);
- }
- strcpy(a[l].en, s);
- }
- }
- void InsertionSort(tdien a[], int n)
- {
- int pos;
- char s[30];
- for (int i = 0; i < n; i++)
- {
- strcpy(s, a[i].en);
- pos = i - 1;
- while ((pos >= 0) && (strcmp(a[pos].en, s) > 0))
- {
- strcpy(a[pos + 1].en, a[pos].en);
- pos--;
- }
- strcpy(a[pos + 1].en, s);
- }
- }
- void SelectionSort(tdien b[], int n)
- {
- int min,i,j;
- for (i=0;i< n-1; i++)
- {
- min =i;
- for (j=i+1; j<n; j++)
- {
- if ( strcmp (b[j].en,b[min].en) < 0)
- min =j;
- }
- Hoanvi(b[i],b[min]);
- }
- }
- void ShellSort(tdien a[], int n)
- {
- int h[6] = { 13, 8, 5, 3, 2, 1 };
- int k=6;
- int step, i, j, len;
- char s[30];
- for ( step = 0; step < k; step++)
- {
- len = h[step];
- for ( i = len; i < n; i++)
- {
- strcpy(s, a[i].en);
- j = i - len;
- while ( j >= 0 && (strcmp(a[j].en, s) > 0) )
- {
- strcpy(a[j + len].en, a[j].en);
- j = j - len;
- }
- strcpy(a[j + len].en, s);
- }
- }
- }
- void xuat(tdien a[], int n)
- {
- for (int i=0;i<n;i++)
- puts (a[i].en);
- }
- void luachon (tdien a[],int n)
- {
- int s;
- FILE *Sort;
- time_t t;
- printf("\n Nhap so thu tu thuat toan muon thuc hien: \n 1.InterchangeSort \n 2.BubbleSort \n 3.ShakerSort \n 4.InsertionSort \n 5.BinsertionSort \n 6.ShellSort \n 7.SelectionSort \n 8.QuickSort \n 9.HeapSort \n");
- printf("\n Luu chon: ");
- scanf("%d",&s);
- switch (s)
- {
- case 1:
- t=clock();
- InterchangeSort(a,n);
- t=clock() - t;
- Sort = fopen("TuDien_InterchangeSort.txt","w");
- writetofile2(Sort,a,n);
- break;
- case 2:
- t=clock();
- BubbleSort (a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_BubbleSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 3:
- t=clock();
- ShakerSort (a,n);
- t=clock() - t;
- Sort = fopen("TuDien_ShakerSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 4:
- t=clock();
- InsertionSort (a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_InsertionSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 5:
- t=clock();
- BinsertionSort (a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_BinsertionSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 6:
- t=clock();
- ShellSort(a,n);
- t=clock() - t;
- Sort = fopen("TuDien_ShellSort.txt","w");
- writetofile2(Sort,a,n);
- break;
- case 7:
- t=clock();
- SelectionSort(a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_SelectionSort.txt","w");
- writetofile2(Sort,a,n);
- break;
- case 8:
- t=clock();
- QuickSort (a,0,n-1);
- t=clock() - t;
- Sort = fopen ("TuDien_QuickSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 9:
- t=clock();
- HeapSort (a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_HeapSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- // case 10:
- // t=clock();
- // MergeSort (a,b,0,n-1);
- // t=clock() - t;
- // Sort = fopen ("TuDien_MergeSort.txt","w");
- // writetofile2 (Sort,a,n);
- // break;
- }
- fputs ("Thuat toan chay mat:",Sort);
- fprintf(Sort,"%10.5f seconds",((float) t / CLOCKS_PER_SEC ) );
- fclose (Sort);
- }
- void main()
- {
- FILE *f;
- int x=0, t=0;
- char a[300];
- tdien *dsta, *td;
- td=new struct tdien[100000];
- TuDientxt(td,x);
- f=fopen("tudien.txt","rt");
- dsta=new struct tdien[100000];
- while (fgets(a,300,f)>0)
- {
- strcpy(dsta[t].en,a);
- t++;
- }
- luachon(dsta,t);
- printf("%d\n",t);
- fclose(f);
- }
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include <windows.h>
- #include <time.h>
- struct tdien
- {
- char en[30];
- };
- void Hoanvi(tdien &a,tdien &b)
- {
- tdien t;
- t=a;a=b;b=t;
- }
- void LocTA(tdien *td, int &x)
- {
- char str[300];
- char* str1,*str2;
- FILE *ds;
- ds = fopen("va.dd","rt");
- while (fgets(str,300,ds)>0)
- {
- str1 = strstr(str,"##");
- if (str1!=NULL)
- {
- str2 = strstr(str1,"|-");
- if (str2!=NULL && strlen(str2)<=17 && strlen(str2)>4)
- {
- strcpy(td[x].en,str2+3);
- x++;
- }
- }
- }
- fclose(ds);
- }
- void TuDientxt(tdien td[], int x)
- {
- FILE *tudien;
- LocTA(td,x);
- tudien = fopen("tudien.txt","w");
- for(int i=0;i<x;i++)
- {
- fputs(td[i].en,tudien);
- fflush (tudien);
- }
- fclose(tudien);
- }
- void writetofile2 (FILE *f, tdien b[], int n)
- {
- for (int i=0; i<n;i++)
- {
- fputs (b[i].en,f);
- fflush (f);
- }
- }
- void QuickSort (tdien a[], int left, int right)
- {
- int i,j;
- char x[30];
- strcpy (x,a[(left+right)/2].en);
- i=left;
- j=right;
- while (i<j)
- {
- while ( strcmp(a[i].en,x) <0 ) i++;
- while (strcmp (a[j].en,x) >0 ) j--;
- if (i<=j)
- {
- Hoanvi(a[i],a[j]);
- i++;
- j--;
- }
- }
- if (left <j)
- QuickSort(a,left,j);
- if (i < right)
- QuickSort(a,i,right);
- }
- void BubbleSort (tdien a[], int n)
- {
- int i,j;
- for( i=0; i<n-1;i++)
- for (j=n-1;j>i;j--)
- {
- if ( strcmp (a[j].en,a[j-1].en) < 0 )
- Hoanvi(a[j],a[j-1]);
- }
- }
- void ShakerSort (tdien a[],int n)
- {
- int j;
- int left, right,k;
- left =0;
- right = n-1;
- k=n-1;
- while (left < right)
- {
- for (j=right; j>left; j--)
- if ( strcmp (a[j].en,a[j-1].en) < 0)
- {
- Hoanvi(a[j],a[j-1]);
- k=j;
- }
- left =k;
- for (j=left; j < right; j++)
- if (strcmp (a[j].en, a[j+1].en) > 0 )
- {
- Hoanvi(a[j],a[j+1]);
- k=j;
- }
- right = k;
- }
- }
- void InterchangeSort (tdien a[], int n)
- {
- int i,j;
- for (i=0;i<n;i++)
- for (j=i+1; j<n; j++)
- if ( strcmp (a[j].en,a[i].en) < 0)
- Hoanvi(a[j],a[i]);
- }
- void Heapify(tdien a[], int n, int i)
- {
- int Left = 2 * (i + 1) - 1;
- int Right = 2 * (i + 1);
- int Largest;
- if (Left<n && (strcmp(a[Left].en, a[i].en ) > 0))
- Largest = Left;
- else
- Largest = i;
- if (Right<n && (strcmp(a[Right].en, a[Largest].en) > 0))
- Largest = Right;
- if (i != Largest)
- {
- Hoanvi(a[i], a[Largest]);
- Heapify(a, n, Largest);
- }
- }
- void BuildHeap(tdien a[], int n)
- {
- for (int i = n / 2 - 1; i >= 0; i--)
- Heapify(a, n, i);
- }
- void HeapSort(tdien a[], int n)
- {
- BuildHeap(a, n);
- for (int i = n - 1; i > 0; i--)
- {
- Hoanvi(a[0], a[i]);
- Heapify(a, i, 0);
- }
- }
- void BinsertionSort(tdien a[], int n)
- {
- int l, r, m, i;
- char s[30];
- for (int i = 1; i < n; i++)
- {
- strcpy(s, a[i].en);
- l = 0;
- r = i - 1;
- while (l <= r)
- {
- m = (l + r) / 2;
- if (strcmp(s, a[m].en) < 0)
- {
- r = m - 1;
- }
- else
- {
- l = m + 1;
- }
- }
- for (int j = i - 1; j >= l; j--)
- {
- strcpy(a[j + 1].en, a[j].en);
- }
- strcpy(a[l].en, s);
- }
- }
- void InsertionSort(tdien a[], int n)
- {
- int pos;
- char s[30];
- for (int i = 0; i < n; i++)
- {
- strcpy(s, a[i].en);
- pos = i - 1;
- while ((pos >= 0) && (strcmp(a[pos].en, s) > 0))
- {
- strcpy(a[pos + 1].en, a[pos].en);
- pos--;
- }
- strcpy(a[pos + 1].en, s);
- }
- }
- void SelectionSort(tdien b[], int n)
- {
- int min,i,j;
- for (i=0;i< n-1; i++)
- {
- min =i;
- for (j=i+1; j<n; j++)
- {
- if ( strcmp (b[j].en,b[min].en) < 0)
- min =j;
- }
- Hoanvi(b[i],b[min]);
- }
- }
- void ShellSort(tdien a[], int n)
- {
- int h[6] = { 13, 8, 5, 3, 2, 1 };
- int k=6;
- int step, i, j, len;
- char s[30];
- for ( step = 0; step < k; step++)
- {
- len = h[step];
- for ( i = len; i < n; i++)
- {
- strcpy(s, a[i].en);
- j = i - len;
- while ( j >= 0 && (strcmp(a[j].en, s) > 0) )
- {
- strcpy(a[j + len].en, a[j].en);
- j = j - len;
- }
- strcpy(a[j + len].en, s);
- }
- }
- }
- void xuat(tdien a[], int n)
- {
- for (int i=0;i<n;i++)
- puts (a[i].en);
- }
- void luachon (tdien a[],int n)
- {
- int s;
- FILE *Sort;
- time_t t;
- printf("\n Nhap so thu tu thuat toan muon thuc hien: \n 1.InterchangeSort \n 2.BubbleSort \n 3.ShakerSort \n 4.InsertionSort \n 5.BinsertionSort \n 6.ShellSort \n 7.SelectionSort \n 8.QuickSort \n 9.HeapSort \n");
- printf("\n Luu chon: ");
- scanf("%d",&s);
- switch (s)
- {
- case 1:
- t=clock();
- InterchangeSort(a,n);
- t=clock() - t;
- Sort = fopen("TuDien_InterchangeSort.txt","w");
- writetofile2(Sort,a,n);
- break;
- case 2:
- t=clock();
- BubbleSort (a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_BubbleSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 3:
- t=clock();
- ShakerSort (a,n);
- t=clock() - t;
- Sort = fopen("TuDien_ShakerSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 4:
- t=clock();
- InsertionSort (a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_InsertionSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 5:
- t=clock();
- BinsertionSort (a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_BinsertionSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 6:
- t=clock();
- ShellSort(a,n);
- t=clock() - t;
- Sort = fopen("TuDien_ShellSort.txt","w");
- writetofile2(Sort,a,n);
- break;
- case 7:
- t=clock();
- SelectionSort(a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_SelectionSort.txt","w");
- writetofile2(Sort,a,n);
- break;
- case 8:
- t=clock();
- QuickSort (a,0,n-1);
- t=clock() - t;
- Sort = fopen ("TuDien_QuickSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- case 9:
- t=clock();
- HeapSort (a,n);
- t=clock() - t;
- Sort = fopen ("TuDien_HeapSort.txt","w");
- writetofile2 (Sort,a,n);
- break;
- // case 10:
- // t=clock();
- // MergeSort (a,b,0,n-1);
- // t=clock() - t;
- // Sort = fopen ("TuDien_MergeSort.txt","w");
- // writetofile2 (Sort,a,n);
- // break;
- }
- fputs ("Thuat toan chay mat:",Sort);
- fprintf(Sort,"%10.5f seconds",((float) t / CLOCKS_PER_SEC ) );
- fclose (Sort);
- }
- void main()
- {
- FILE *f;
- int x=0, t=0;
- char a[300];
- tdien *dsta, *td;
- td=new struct tdien[100000];
- TuDientxt(td,x);
- f=fopen("tudien.txt","rt");
- dsta=new struct tdien[100000];
- while (fgets(a,300,f)>0)
- {
- strcpy(dsta[t].en,a);
- t++;
- }
- luachon(dsta,t);
- printf("%d\n",t);
- fclose(f);
- }
Advertisement
Add Comment
Please, Sign In to add comment