Sắp xếp vun đống

Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) mảng, sau đó tiếp tục với phần còn lại của mảng.

Thông thường sắp xếp chọn chạy trong thời gian O(n²). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Thuật toán tốn thời gian là O(n*log(n)).

Thuật toán

Đầu tiên là vun đống của mảng dữ liệu. Tiếp theo là lấy phần tử lớn nhất rồi đưa phần tử đó vào cuối mảng. Sau khi lấy được phần tử lớn nhất đầu tiên, ta sắp xếp đống còn lại. Rồi tiếp tục lấy phần tử lớn nhất tiếp theo. Tiếp tục đến hết mảng.

Hàm insertHeap() và hàm deleteMaxHeap() đã đề cập ở cấu trúc dữ liệu heap.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/**
 * @param arr là danh sách các phần tử của mảng cần sắp xếp
 * @param heap là mảng kết quả
 * @param length là số lượng phần tử trong arr
 */
void heapSort(int* arr, int* heap, int length) {
  for (int i = 0; i < length; i++) {
    insertHeap(heap, i, arr[i]);
  }
  for (int i = 0; i < length ; i++) {
    deleteMaxHeap(heap, length - i);
  }
}

Cấu trúc dữ liệu

Thuật toán sắp xếp