[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

[10520073]

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

#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

[12520018]

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 :

#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

[10520073]

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

#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
*

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

[12520018]

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... ^^

[10520073]

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