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.

Tuesday, August 26, 2014
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
{
      int i,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[])
{
      int i;
      FILE *v;
      v=fopen("C:\\DULIEU.txt","rt");
      for(i=0;i<n;i++)
            fscanf(v,"%d",&a[i]);
}
void xemmang(int a[])
{
      int i;
      for (i=0;i<n;i++)
            printf("%d   ",a[i]);
      printf("\n");
}
void ghidl(int a[],FILE *l)
{
      int i;
      for (i=0;i<n;i++)
            fprintf(l,"%d   ",a[i]);
}
void copymang(int a[],int b[])
{
      int i;
      for (i=0;i<n;i++)
            b[i]=a[i];
}
void swap(int &a,int &b)
{
      int tg=a;
      a=b;
      b=tg;
}
void SapXepChon(int a[])
{
    int i,imin,j,tg;
       ///////Time/////////
      int ms;
      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[])
{
     int i,tg,x;
       ///////Time/////////
      int ms;
      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
{
      int i,j,tg;
      ///////Time/////////
      int ms;
      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;
     int i=l;
     int j=r;
     int x=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/////////
      int ms;
      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[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
{
      int i,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[])
{
      int i;
      FILE *v;
      v=fopen("C:\\DULIEU.txt","rt");
      for(i=0;i<n;i++)
            fscanf(v,"%d",&a[i]);
}
void xemmang(int a[])
{
      int i;
      for (i=0;i<n;i++)
            printf("%d   ",a[i]);
      printf("\n");
}
void ghidl(int a[],FILE *l)
{
      int i;
      for (i=0;i<n;i++)
            fprintf(l,"%d   ",a[i]);
}
void copymang(int a[],int b[])
{
      int i;
      for (i=0;i<n;i++)
            b[i]=a[i];
}
void swap(int &a,int &b)
{
      int tg=a;
      a=b;
      b=tg;
}
void SapXepChon(int a[])
{
    int i,imin,j,tg;
       ///////Time/////////
      int ms;
      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[])
{
     int i,tg,x;
       ///////Time/////////
      int ms;
      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
{
      int i,j,tg;
      ///////Time/////////
      int ms;
      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;
     int i=l;
     int j=r;
     int x=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/////////
      int ms;
      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/////////
      int ms;
      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();
}


Chia sẻ bài viết ^^
Other post

All comments [ 0 ]


Your comments