01/10/2018, 08:25

CTDL&GT: Heap Sort

E đang học ctdl + gt. Hnay mới thử tìm hiểu cái heap sort vs viết thử cái chương trình. A chị nào rảnh thì giúp e kiểm tra xem nó đã đúng chưa vs ạ

#include <stdio.h>
#include <conio.h>
int swap(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
	return 0;
}
int main()
{
	int array[100], i, j, top, left, right, max;
	int n = 50;
	int m = 50;
	int x = 50;
	for(i = 0; i < n; i++) //Tạo mảng chưa được sắp xếp
	{
		array[i] = x;
		x--;
	}
	while(n > 1)
	{
		for(i = n/2 - 1; i >= 0; i-- )
		{
			left = i*2 + 1;
			max = i;
			top = i;
			max = array[max] > array[left] ? max : left;
			if(i*2 + 2 <= n - 1)
			{
				right = i*2 + 2;
				max = array[max] > array[right] ? max : right;
			}
			while(max != top)
			{
				swap(&array[max], &array[top]);
				top = max;
				if(top*2 + 1 <= n - 1) left = top*2 + 1;
				max = array[max] > array[left] ? max : left;
				if(top*2 + 2 <= n - 1)
				{
					right = top*2 + 2;
					max = array[max] > array[right] ? max : right;
				}
			}
		}
		swap(&array[0], &array[n - 1]); // Hoán vị 2 phần tử
		n--;
	}
	n = m;
	for(i = 0; i < m; i++)
	{
		i == m - 1 ? printf("%d.
") : printf("%d, ", array[i]);
	}
	getch();
	return 0;
}
Trần Huy viết 10:37 ngày 01/10/2018

Waw. Ý tưởng không dùng đệ quy để lan truyền thay đổi sau khi hiệu chỉnh Heap.

kiencon viết 10:39 ngày 01/10/2018

chia hàm ra để quản lý và còn sửa lỗi nếu gặp cho dễ bạn.

Bài liên quan
0