Thuật toán heap sort

#1

Mọi người có thể cho em xin mã nguồn thuật toán heapsort được không ạ ? Và cho em hỏi là số phần tử tối đa heapsort có thể chạy là bao nhiêu ? Em đã tham khảo trên mạng nhưng với 10000 phần tử trở lên thì thuật toán không chạy và bị đứng.
Em cảm ơn mọi người
hàm heapsort của em tham khảo :

void Array::CreateHeap()
{
	int offset, heapSize;
	heapSize = length - 1;

	for (offset = (length / 2); offset >= 0; offset--)
	{
		Heapify( offset, heapSize);
	}
}
void Array::Heapify(int _offset, int _heapSize)
{
	int leftNode, rightNode, largest, temp;
	leftNode = 2 * _offset;
	rightNode = 2 * _offset + 1;

	if (leftNode <= _heapSize && value[leftNode] > value[_offset])
	{
		largest = leftNode;
	}
	else
	{
		largest = _offset;
	}

	if (value[rightNode] > value[largest] && rightNode <= _heapSize)
	{
		largest = rightNode;
	}

	if (largest != _offset)
	{
		temp = value[_offset];
		value[_offset] = value[largest];
		value[largest] = temp;
		Heapify( largest, _heapSize);
	}
}
void Array::HeapSort()
{
	clock_t start = clock();
	CreateHeap();

	int heapSize, offset, temp;
	heapSize = length - 1;

	for (offset = heapSize; offset >= 0; offset--)
	{
		temp = value[0];
		value[0] = value[heapSize];
		value[heapSize] = temp;

		heapSize--;

		Heapify( 0, heapSize);
	}
	clock_t end = clock();
	this->time = double(end - start)*1.0 / CLOCKS_PER_SEC;
}
#2

Lưu ý hàm heapify có cấp O(nlogn) (viết chuẩn là O(n)) nên bạn cần xem lại, vì thật sự hiệu chỉnh khi đã heapify xong rất ít O(logn).

1 Like
#3

Em phải hiểu nó hoạt động như nào trước đã
Heapsort sử dụng cấu trúc dữ liệu heap
Cấu trúc dự liệu heap là gì?
Heapsort sử dụng heap như thế nào?

1 Like
#4

Chỗ left, right child có lỗi.
Left child = offset*2+1;
Right child= left child + 1;
Code bị lặp vô hạn khi bạn heapify offset = 0, largest = leftNode = 0

1 Like
#5

Dạ mấy anh thông cảm ạ :smile: vì bài tập này thầy chỉ cho tìm hiểu chứ không dạy, trong khi có tới 6 thuật toán sắp xếp em không tìm hiểu hết được, chỉ lên mạng copy y xì chứ tìm hiểu không kịp :smile:

#6

vậy mình phải sửa thế nào vậy anh ?

#7

Nếu môn này mà là CTDL & GT thì vái cả nón luôn ấy :v

Cứ vẽ heap nhị phân rồi đánh chỉ số là thấy ngay.

1 Like
#8

cho em xin code được không ?

#9
  • DNH không hoan nghênh việc xin code.
  • Nếu bạn vẫn muốn xin code, Google có đầy. Đây là 1 ví dụ:
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?