Câu 2:
Viết chương trình làm các công việc sau:
a. Tạo dữ liệu:
Sinh ngẫu nhiên 50 số nguyên trong khoảng (-100, 100) và lưu các số đó vào tệp DULIEU.TXT gồm 1 dòng và 50 cột, mỗi số cách nhau một ký tự trống
b. Sắp xếp:
Đọc 50 số từ tệp DULIEU.TXT sắp xếp chúng theo thứ tự không giảm bằng các kỹ thuật:
Sắp xếp chọn (Selection Sort), sắp xếp chèn (Insertion Sort), sắp xếp nổi bọt (Bubble Sort) và sắp xếp nhanh (Quick Sort). Lưu kết quả sắp xếp của mỗi kỹ thuật vào các tệp tương ứng là SXCHON.TXT, SXCHEN.TXT, SXNOIBOT.TXT và SXNHANH.TXT. Mặt khác trong dòng cuối của mỗi tệp sau khi sắp ghi thời gian đã sử dụng để sắp xếp dãy số trên.
Code bài 2: file *.txt lưu ở nền ổ C cả
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <ctime>
#include <stdlib.h>
using namespace std;
int n=50;
void sinhdl()// tao ngau nhien va ghi du lieu vao tep C:\\DULIEU.txt
{
inti,k;
FILE *u;
u=fopen("C:\\DULIEU.txt","wt");
for(i=0;i<n;i++)
{
k = rand() %(200)-100;// tao ngau nhien phan tu k trong khoanf -100
den 100
fprintf(u,"%d ",k);
}
fclose(u);
printf("\n 0k DULIEU.txt");
}
void docdl(int a[])
{
inti;
FILE *v;
v=fopen("C:\\DULIEU.txt","rt");
for(i=0;i<n;i++)
fscanf(v,"%d",&a[i]);
}
void xemmang(int a[])
{
inti;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void ghidl(int a[],FILE *l)
{
inti;
for(i=0;i<n;i++)
fprintf(l,"%d ",a[i]);
}
void copymang(int a[],int b[])
{
inti;
for(i=0;i<n;i++)
b[i]=a[i];
}
void swap(int &a,int&b)
{
inttg=a;
a=b;
b=tg;
}
void SapXepChon(int a[])
{
inti,imin,j,tg;
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
for(i=0; i<=n-2; i++)
{
imin = i; //Tìm imin
for(j=i+1; j<=n-1; j++)
if (a[j] < a[imin])
{
imin = j;
}
//Hoán đổi a[i] và a[imin]
swap(a[i],a[imin]);
}
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
FILE *u;
u=fopen("c:\\SXCHON.txt","wt");
ghidl(a,u);
fprintf(u,"\nTime : %d",ms);
fclose(u);
printf("\n 0k SXCHON.txt");
std::cout << " Time : " << ms << " ms" << std::endl;
}
void SapXepChen(int a[])
{
inti,tg,x;
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
for(i=1;i<n;i++)
{
tg=a[i];
x=i-1;
while((x>=0)&&(a[x]>tg))
{
a[x+1] = a[x];
x--;
}
a[x+1] =tg;
}
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
FILE *u;
u=fopen("c:\\SXCHEN.txt","wt");
ghidl(a,u);
fprintf(u,"\nTime : %d",ms);
fclose(u);
printf("\n\n 0k SXCHEN.txt");
std::cout << " Time : " << ms << " ms" << std::endl;
}
void bubblesort(int a[]) //Bubble Sort
{
inti,j,tg;
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
for(i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
if (a[i]>a[j])
//Hoán đổi a[i] và a[j]
swap(a[i],a[j]);
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
FILE *u;
u=fopen("c:\\SXNOIBOT.txt","wt");
ghidl(a,u);
fprintf(u,"\nTime : %d",ms);
fclose(u);
printf("\n 0k SXNOIBOT.txt");
std::cout << " Time : " << ms << " ms" << std::endl;
}
void quicksort2(int A[],int l,int r)
{
if(l>=r) return;
inti=l;
intj=r;
intx=A[(l+r)/2];
while(i<=j)
{
while(A[i]<x) i++;
while(A[j]>x) j--;
if(i<=j)
{// doi cho A[i] A[j]
swap(A[i],A[j]);
i++;j--;
}
}
quicksort2(A,l,j);
quicksort2(A,i,r);
}
void quicksort1(int a[])
{
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
quicksort2(a,0,n-1);//sapxep
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
FILE *u;
u=fopen("c:\\SXNHANH.txt","wt");
ghidl(a,u);
fprintf(u,"\nTime : %d",ms);
fclose(u);
printf("\n 0k SXNHANH.txt");
std::cout << " Time : " << ms << " ms" << std::endl;
}
void main()
{
inta[50],b[50];
sinhdl();
docdl(a);
//xemmang(a);
copymang(a,b);
SapXepChon(b);
copymang(a,b);
SapXepChen(b);
copymang(a,b);
bubblesort(b);
copymang(a,b);
quicksort1(b);
getch();
}
===============================================
===============================================
===============================================
============code hiện rõ time xét 15000 số sinh ra rồi sắp xếp ========
Thay đổi phần bôi vàng
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <ctime>
#include <stdlib.h>
using namespace std;
int n=15000;
void sinhdl()// tao ngau nhien va ghi du lieu vao tep C:\\DULIEU.txt
{
inti,k;
FILE *u;
u=fopen("C:\\DULIEU.txt","wt");
for(i=0;i<n;i++)
{
k = rand() %(200)-100;// tao ngau nhien phan tu k trong khoanf -100 den 100
fprintf(u,"%d ",k);
}
fclose(u);
printf("\n 0k DULIEU.txt");
}
void docdl(int a[])
{
inti;
FILE *v;
v=fopen("C:\\DULIEU.txt","rt");
for(i=0;i<n;i++)
fscanf(v,"%d",&a[i]);
}
void xemmang(int a[])
{
inti;
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
void ghidl(int a[],FILE *l)
{
inti;
for(i=0;i<n;i++)
fprintf(l,"%d ",a[i]);
}
void copymang(int a[],int b[])
{
inti;
for(i=0;i<n;i++)
b[i]=a[i];
}
void swap(int &a,int&b)
{
inttg=a;
a=b;
b=tg;
}
void SapXepChon(int a[])
{
inti,imin,j,tg;
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
for (i=0; i<=n-2; i++)
{
imin = i; //Tìm imin
for(j=i+1; j<=n-1; j++)
if (a[j] < a[imin])
{
imin = j;
}
//Hoán đổi a[i] và a[imin]
swap(a[i],a[imin]);
}
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
FILE *u;
u=fopen("c:\\SXCHON.txt","wt");
ghidl(a,u);
fprintf(u,"\nTime : %d",ms);
fclose(u);
printf("\n 0k SXCHON.txt");
std::cout << " Time : " << ms << " ms" << std::endl;
}
void SapXepChen(int a[])
{
inti,tg,x;
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
for(i=1;i<n;i++)
{
tg=a[i];
x=i-1;
while((x>=0)&&(a[x]>tg))
{
a[x+1] = a[x];
x--;
}
a[x+1] =tg;
}
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
FILE *u;
u=fopen("c:\\SXCHEN.txt","wt");
ghidl(a,u);
fprintf(u,"\nTime : %d",ms);
fclose(u);
printf("\n\n 0k SXCHEN.txt");
std::cout << " Time : " << ms << " ms" << std::endl;
}
void bubblesort(int a[]) //Bubble Sort
{
inti,j,tg;
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
for(i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
if (a[i]>a[j])
//Hoán đổi a[i] và a[j]
swap(a[i],a[j]);
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
FILE *u;
u=fopen("c:\\SXNOIBOT.txt","wt");
ghidl(a,u);
fprintf(u,"\nTime : %d",ms);
fclose(u);
printf("\n 0k SXNOIBOT.txt");
std::cout << " Time : " << ms << " ms" << std::endl;
}
void quicksort2(int A[],int l,int r)
{
if(l>=r) return;
inti=l;
intj=r;
intx=A[(l+r)/2];
while(i<=j)
{
while(A[i]<x) i++;
while(A[j]>x) j--;
if(i<=j)
{// doi cho A[i] A[j]
swap(A[i],A[j]);
i++;j--;
}
}
quicksort2(A,l,j);
quicksort2(A,i,r);
}
void quicksort1(int a[])
{
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
quicksort2(a,0,n-1);//sapxep
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
FILE *u;
u=fopen("c:\\SXNHANH.txt","wt");
ghidl(a,u);
fprintf(u,"\nTime : %d",ms);
fclose(u);
printf("\n 0k SXNHANH.txt");
std::cout << " Time : " << ms << " ms" << std::endl;
}
void main()
{
int a[15000],b[15000];
///////Time/////////
intms;
std::clock_t start;
start = std::clock();
//////start time ////
sinhdl();
docdl(a);
//xemmang(a);
copymang(a,b);
SapXepChon(b);
copymang(a,b);
SapXepChen(b);
copymang(a,b);
bubblesort(b);
copymang(a,b);
quicksort1(b);
//////end time ////
ms = (std::clock() - start)/(double)(CLOCKS_PER_SEC / 1000);
///////////////////
std::cout << " \n tong Time : " << ms << " ms" << std::endl;
getch();
}
No comments:
Post a Comment