Announcement

Collapse
No announcement yet.

nhờ mọi người giúp tìm lỗi bài tập sắp xếp tăng dần bằng thuật toán Quick sort

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • [Ansi C] nhờ mọi người giúp tìm lỗi bài tập sắp xếp tăng dần bằng thuật toán Quick sort

    PS:nhầm cái tiêu đề: tiêu đề phải sửa Quick sort thành merge sort


    BÀi này nó không chạy theo đáp án yêu cầu của đề bài
    Code:
    #include<stdio.h>
    #include<conio.h>
    int b[100],c[100];
    void nhapmang( int a[], int n)
    {
      int i;
      for (i=0; i<n;i++)
       {
         printf("\nNhap ptu thu %d:", i);
         scanf("%d",&a[i]);
       }
    }
    // xuat mang
    void xuatmang( int a[], int n)
    {
      int i;
      for (i=0; i<n;i++) printf("%3d", a[i]);
      printf("\n");
    }
    int minhaiso(int a,int b)
    
    {
        if(a>b)
        return b;
        else 
        return a;
        }
    
        void merge(int a[],int nb,int nc,int b[],int c[],int k)
     
     {
          
          int pb=0,pc=0,p=0,ib=0,ic=0,kb,kc;
          while((0<nb)&&(0<nc))
          {
          kb=minhaiso(k,nb);
          kc=minhaiso(k,nc);
          if(b[pb+ib]<=c[pc+ic])
          {
                      a[p++]=b[pb+ib];
                      ib++;
                      if(ib==kb)
                      {
                                for(;ic<kc;ic++)
                                a[p++]=c[pc+ic];
                        nb-=kb;nc=-kc;
                        ib=0,ic=0 ; 
                        pb+=kb;
                        pc+=kc;      
                                
                       }
          }
          else
          {
              a[p++]=c[pc+ic];
              ic++;
              if(ic==kc)
              {
              for(;ib<kb;ib++)
              a[p++]=b[pb+ib];
              ib=0,ic=0;
              nb-=kb,nc-=kc;
              pb+=kb; pc+=kc;
              }
              }
          
          }
          
          }
           
        
    void mergesort(int a[],int n)
    {    
        
         int b[20],c[20];
         int p,pb,pc;
         int i,k=1;
         do
         {
             p=0,pb=0,pc=0;
         while(p<n)
         {
         for(i=0;(p<n)&&(i<k);i++)
         b[pb++]=a[p++];
         for(i=0;(p<n)&&(i<k);i++)
         c[pc++]=a[p++];
         }
       //  merge( a,pb,pc,b,c,k);
        merge(a,pc,pb,c,b,k);
         k=k*2;
         }while(k<n);
    
         }
     
          
          
         
          int main()
    {
          int b[100],c[100];
      int a[20];
      int n=10;
      nhapmang(a,n);
      xuatmang(a,n);
      mergesort(a,n);
      printf("\nDa sap xong:");
      xuatmang(a,n);
      getch();
    }
    lỗi: kết quả xuất ra màn hình không theo thứ tự tăng dần


    abc.png
    10520073
    Đoàn Xuân Cầu
    Last edited by 10520073; 15-04-2013, 17:28.

  • #2
    Code mergesort làm sao mà chạy giống yêu cầu quicksort được chứ

    Nếu code Quick sort thì tham khảo code của mình :
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #include<malloc.h>
    void nhap(int *a,int &n)
    {
    	for(int i=0;i<n;i++)
    		a[i]=rand();
    }
    void xuat(int *a, int n)
    {
    	for(int i=0;i<n;i++)
    		printf("%d\t",a[i]);
    }
    void hoanvi(int &x,int &y)
    {
    	int temp=x;
    	x=y;
    	y=temp;
    }
    int kiemtrathutu(int a[], int n)
    {
    	for(int i=0;i<n-1;i++)
    	{
    		if(a[i]>a[i+1])
    			return 0;
    	}
    	return 1;
    }
    void quick_sort(int a[], int l, int r )
    {
    	int i,j; //  1 5 3 9 
    	int x=a[(l+r)/2]; //x=5
    	i=l; j=r;// i=0 j=3
    	do{
    		while(a[i]<x) i++;// a[0]= 1 < 5 => i=1
    		while(a[j]>x) j--;// a[3]= 9 > 5 => j=2
    		if(i<=j)// 1<2
    		{
    			hoanvi(a[i],a[j]); // a[1]=3; a[2] =5
    			i++;j--;	// i= 2 j=1	
    		}
    	}while(i<j);
    	if(l<j) 
    		quick_sort(a,l,j);
    	if(i<r)
    		quick_sort(a,i,r);
    } 
    
    int main()
    {
    	srand(time(0));
    	int n;
    	int length = 100000;
    	int *a = (int*)malloc(sizeof(int)*length);
    	printf("Nhap n: ");
    	scanf("%d",&n);
    	nhap(a,n);
    	quick_sort(a,0,n-1);
    	xuat(a,n);
    	if(kiemtrathutu(a,n)==1) printf("Mang tang");
    	else printf("Mang khong tang");
    	return 0;
    }
    Merge Sort thì tham khảo link: http://www.personal.kent.edu/~rmuham.../mergeSort.htm
    12520018
    Đinh Nhật Băng
    Last edited by 12520018; 15-04-2013, 00:41.
    Lúc mới vào UIT :byebye:
    Học xong năm 1: :haha:
    Học xong năm 2: :sexy:
    Học xong năm 3: :baffle:

    Comment


    • #3
      Originally posted by 12520018 View Post
      Code mergesort làm sao mà chạy giống yêu cầu quicksort được chứ

      Nếu code Quick sort thì tham khảo code của mình :
      [CODE]
      #include<stdio.h>
      #include<stdlib.h>
      #include<time.h>
      #include<malloc.h>
      void nhap(int *a,int &n)
      {

      http://www.personal.kent.edu/~rmuham.../mergeSort.htm
      ông xem lại đi
      tôi đưa thuật toán của thầy cho ông xem.

      //Sap xep Tron hay Merge sort
      Code:
      #include "stdio.h"
      #include<conio.h>
      #define MAX = 20
      
      // ham doi cho
      
      // nhap mang
      void nhapmang( int a[], int n)
      {
        int i;
        for (i=0; i<n;i++)
         {
           printf("\nNhap ptu thu %d:", i);
           scanf("%d",&a[i]);
         }
      }
      // xuat mang
      void xuatmang( int a[], int n)
      {
        int i;
        for (i=0; i<n;i++) printf("%3d", a[i]);
        printf("\n");
      }
      
      // Mergce Sort
      
      void tronkphantu( int k, int B[], int Nb, int C[], int Nc, int A[])
      {
      	int i=0, vtb=0, vtc=0; // Vi tri cua A,B,C khi bat dau xet k fan tu tiep theo
      	int jb=0, jc=0; // dem so fan tu cua B, C da dua vao A
      	int kb, kc; // spt toi da cua B, C se dua vao A
      
      	while ((Nb>0) &&(Nc>0))
      	{
      		if (k<Nb) kb=k; else kb=Nb;
      		if (k<Nc) kc=k; else kc=Nc;
      		if (B[vtb+jb]<= C[vtc+jc])
      		{
      			A[i++]=B[vtb+jb];// dua B vao
      			jb++;
      			if (jb==kb) // dua het kb fan tu cua B vao A
      			{
      				//dua luon so con lai cua C vao A
      				for (;jc<kc; jc++) A[i++]=C[vtc+jc];
      				//Chuan bi dua k fan tu tiep theo vao A
      				vtb=vtb+kb;
      				vtc=vtc+kc;
      				Nb=Nb-kb;
      				Nc=Nc-kc;
      				jb=0;
      				jc=0;
      			}
      
      		}
      		else
      		{
      			A[i++]=C[vtc+jc];// dua C vao
      			jc++;
      			if (jc==kc) // dua het kc fan tu cua C vao A
      			{
      				//dua luon so con lai cua B vao A
      				for (;jb<kb; jb++) A[i++]=B[vtb+jb];
      				//Chuan bi dua k fan tu tiep theo vao A
      				vtb=vtb+kb;
      				vtc=vtc+kc;
      				Nb=Nb-kb;
      				Nc=Nc-kc;
      				jb=0;
      				jc=0;
      			}
      		}
      	}
      
      /*	while (Nb>0) // dua het so con lai cua B vao A
      		{
      			A[i++]=B[vtb+jb];
      			jb++;
      			Nb--;
      		}
      	while (Nc>0) // dua het so con lai cua C vao A
      		{
      			A[i++]=C[vtc+jc];
      			jc++;
      			Nc--;
      		}*/
      }
      
      
      void sapxeptron(int A[], int N)
      {
      
      	int B[20], C[20];
      	int j, Nb, Nc;
      	int i, k=1; // k la do dai day con B, C
      	do
      	{
      		// tach A ra B, C
      		j=Nb=Nc=0;
      		while (j<N)
      		{
      			for(i=0;(j<N)&&(i<k); i++) B[Nb++]=A[j++];
      			for(i=0;(j<N)&&(i<k); i++) C[Nc++]=A[j++];
      		}
      		//tronkphantu(k,B,Nb,C,Nc, A);//tron B, C vao A
      		tronkphantu(k,C,Nc,B,Nb, A);
      		k=k*2;
      	}
      	while (k<N);
      }
      //========
      int main()
      {
        int a[20];
        int n=10;
        nhapmang(a,n);
        xuatmang(a,n);
        sapxeptron(a,n);
        printf("\nDa sap xong:");
        xuatmang(a,n);
        getch();
      }
      mình thấy 2 vòng while của thầy ko cần thiết nên mình bỏ 2 dòng đó đi.cụ thể là 2 vòng while này
      *
      Code:
      while (Nb>0) // dua het so con lai cua B vao A
      		{
      			A[i++]=B[vtb+jb];
      			jb++;
      			Nb--;
      		}
      	while (Nc>0) // dua het so con lai cua C vao A
      		{
      			A[i++]=C[vtc+jc];
      			jc++;
      			Nc--;
      
      }
      mình thấy 2 vòng while này ko cần thiết vì :vì khi duyệt xong mảng b hoặc mảng c rồi và nó kiểm tra điều kiện while(nb>0)&&nc>0) thì nó thoát khỏi vòng lặp while còn các phần tử thừa lại của mảng b hoặc mảng c chưa xét thì nó lại là phần tử cuối cùng của mảng a khi chưa gọi hàm merge( ..........).trong giáo trình cấu trúc dữ liệu và giải thuật của tác giả TRẦN HẠNH NHI và Dương Anh Đức cũng bỏ 2 vòng while mà thầy Thắng cho vào
      10520073
      Đoàn Xuân Cầu
      Last edited by 10520073; 15-04-2013, 01:24.

      Comment


      • #4
        Nói thật thì code này bá đạo quá nên làm biếng test quá! nhìn vào rất là rối... ^^
        Lúc mới vào UIT :byebye:
        Học xong năm 1: :haha:
        Học xong năm 2: :sexy:
        Học xong năm 3: :baffle:

        Comment


        • #5
          Originally posted by 12520018 View Post
          Nói thật thì code này bá đạo quá nên làm biếng test quá! nhìn vào rất là rối... ^^
          hôm qua viết nhầm cái tiêu đề đã sửa lại và đã tìm được lỗi sai.Cái code này trong giáo trình của trường mình mà.tự đọc hiểu rồi tự code rồi tìm lỗi sai
          thuật toán em đưa nhìn mới rối mắt và khó hiểu nhưng chắc cái đó chạy nhanh hơn
          10520073
          Đoàn Xuân Cầu
          Last edited by 10520073; 15-04-2013, 17:46.

          Comment

          LHQC

          Collapse
          Working...
          X