Heap_sort...

[giangnk]

chắc những ai đã từng học qua môn cấu trúc dữ liệu và giải thuật đều biết tới thuật toán sắp xếp này.
Vậy có thể xem hộ mình code này ko? Chẳng biết là có lỗi ở đâu nữa...

#include<stdio.h>
#define max 1000

void max_heapify(int a[],int i, int n);
void build_max_heap(int a[],int n);
void heap_sort(int a[],int n);

int main()
{
  int i,n,a[max];
  printf("nhap vao so phan tu: ");scanf("%d",&n);
  printf("nhap vao cac phan tu of mang:\n");
  for(i=1;i<=n;i++)  { printf("a[%d]=",i);scanf("%d",&a[i]); }
  heap_sort(a,n);
  printf("mang sau khi sap xep la: \n");
  for(i=1;i<=n;i++)  printf("%d  ",a[i]);
  return 0;
}

void max_heapify(int a[],int i, int n)
{
  int temp,t;
  if(2*i+1<n) t=(a[2*i+1]>a[2*i])?(2*i+1):(2*i);
  else t=2*i;
  if(a[i]<a[t]) {temp=a[i];a[i]=a[t];a[t]=temp;}
  max_heapify(a,t,n);
}
void build_max_heap(int a[],int n)
{
  int i;
  for(i=n/2;i>=1;i--)  max_heapify(a,i,n);
}
void heap_sort(int a[],int n)
{
  int temp,i;
  build_max_heap(a,n);
  for(i=n;i>=2;i--)
    {
	  temp=a[1];a[1]=a[i];a[i]=temp;
	  max_heapify(a,1,i-1);
	}
 
}

Cảm ơn mọi người nhiều nhé!!!

[huybka]

tớ nghĩ cậu sai cơ bản về mặt thuật toán ở hàm max heapify rồi,cậu đọc lại kỹ lý thuyết sẽ thấy ngay,hàm max heapify của cậu kô cần kiểm tra điều kiện đã gọi đệ qui-->gọi đệ qui liên tục cho đến khi segmentation fault,sửa xong hàm max heapify rồi thì mình debug vẫn thấy ra kết quả sai,có lẽ vẫn là do thuật toán sai thôi

[vtien_uit]

MÌnh chưa xem code của bạn nhưng mình có làm cái này rồi mình post lên bạn tham khảo nhé

void taoheap(int a[],int l,int r)
{
    int x,i,j;
    i=l;
    j=2*i+1;
    x=a[i];
    while(j<=r)
    {
        if(j<r)
             if(a[j]<a[j+1])
                j++;


        if(a[j]<=x) return;
        else
        {
            a[i]=a[j];
            a[j]=x;
            i=j;
            j=2*i+1;
            x=a[i];
         }

    }
}


void taoheapdau(int a[],int n)
{
     int l;
     l=n/2-1;
     while(l>=0)
     {
        taoheap(a,l,n-1);
        l=l-1;
     }
}
void HeapSort(int a[],int n)
{
    int r;
    taoheapdau(a,n);
    r=n-1;
    while(r>0)
    {
        hoanvi(a[0],a[r]);
        r--;
        xuatmang(a,n);
                printf("\n");
        if(r>0)
            taoheap(a,0,r);
    }
}

[huybka]

@vtien:ban kô để code vào trong tag khó đọc quá
@nkgiang

void max_heapify(int a[],int i, int n)
{
  int temp,t;
  if(2*i+1<=n && a[2*i+1]>a[n])t=2*i+1;
  	else t=i;
  if(2*i<=n && a[2*i]>a[t])t=2*i;
  if(a[i]<a[t])
	{ {temp=a[i];a[i]=a[t];a[t]=temp;}
  	  max_heapify(a,t,n);
	}
}

mình nghĩ hàm max_heapify bạn nên sủa lại như trên,mình đã test vài trường hợp và thấy có vẻ đúng

[giangnk]

Hóa ra làm theo "thầy" vẫn là an toàn hơn cả hi`hi`...

if(2*i+1<=n && a[2*i+1]>a[n])t=2*i+1;

sửa một tí sơ suất

if(2*i+1<=n && a[2*i+1]>a[i])t=2*i+1;

Thanks Huy nhé!

[huybka]

hihi kô phải là làm theo hay kô làm theo thầy,mà là cậu sai hẳn về thuật toán thôi,chứ heap sort thì có nhiều cách viết lắm,có đứa bạn tớ còn mở rộng để tăng tốc độ tính toán lên nữa cơ

[vtien_uit]

có đứa bạn tớ còn mở rộng để tăng tốc độ tính toán lên nữa cơ

Bạn có thể đưa lên đây cho anh em chiêm ngưỡng được không

[nguyentuandat]

/*
Chuong trinh: Thuc hanh phuong phap sap xep truc tiep
*/

#include<stdio.h>
#include<conio.h>
void HoanVi(int &a,int &b);
void Shift(int a[],int left,int right);// Ham hieu chinh mang ->Dang Heap;
void CreateHeap(int a[],int n);// Ham Tao
void HeapSort(int a[],int n);// Ham chinh;
void Xuat(int a[],int n);
void main()
{
	int m[]={2,5,1,6,3,8,4,9,7,0};
	int spt=9;
	clrscr();
	CreateHeap(m,spt);//hieu chinh day ban dau thanh heap
	HeapSort(m,spt);//sap xep bang heap sort
	Xuat(m,spt);
	getch();
}
void HoanVi(int &a,int &b)
{
	int tmp;
		tmp=a;
		a = b;
		b=tmp;
}
//hieu chinh day bat ki thanh heap
void Shift(int a[],int left,int right)
{
	int x,i,j;
	i=left;
	j=2*i;
	x=a[i];//phan tu cha
	while(j<=right)
	{
		if(j<right)
		if(a[j]<a[j+1])//xac dinh phan tu lien doi lon nhat
			j++;
			if(a[j]<=x)
				return;//thoa quan he lien doi dung
		else
		{
			a[i]=a[j];
			i=j;//xet tiep kha nang hieu chinh lan truyen
			j=2*i;//cap nhat phan tu lien doi moi
			a[i]=x;//cap nhat phan tu cha moi
		}
	}
}
//tao mot heap
void CreateHeap(int a[],int n)
{
	int left;
	left=(n-1)/2;
	while(left>=0)//
	{
		Shift(a,left,n-1);
			left--;//xet tu giua ve dau mang
	}
}
//sap sep bang heap sort
void HeapSort(int a[],int n)
{
	int right;
	CreateHeap(a,n);//tao heap truoc khi xep
	right=n-1;
	while(right>0)
	{
		HoanVi(a[0],a[right]);
			right--;//lui ve truoc dua phan tu lon nhat ra sau mang
		Shift(a,0,right);//hieu chinh day con lai thanh mot heap
	}
}
void Xuat(int a[],int n)
{
	printf("\nMang vua sap xep lai la: \n\n\n");
	for(int i=0;i<n;i++)
		printf(" %d\t",a[i]);
}

--------------------------------------------------------
Chú ý viết tiếng việt có dấu và đặt code vào tag