[Thuật toán] Các thuật toán sắp xếp trong lập trình C - Heap Sort - Vun đống

1. Bubble sort. (Nổi bọt, nổi bong bóng)
2. Quick sort. (Sắp xếp nhanh)
3. Simple selection sort. (Sắp xếp chọn)
4. Heap sort. (Sắp xếp vun đống)
5. Simple insertion sort.(Sắp xếp chèn)
6. Shell sort.
7. Merge sort. (Sắp xếp hòa nhập)

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) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). 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). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).

Thuật toán sắp xếp vun đống

C++ Code:

1. #include < iostream.h >
2. #include < conio.h >
3. int heapSize = 10;
4. void print(int a[])
5. {
6.   for (int i = 0; i <= 9; i++)
7.  {
8.     cout << a[i] << "-";
9.   }
10.   cout << endl;
11. }
13. int parent(int i)
14. {
15. if(i==1)
16. return 0;
18. if(i%2==0)
19.     return ( (i / 2)-1);
20. else
21.     return ( (i / 2));
22. }
24. int left(int i)
25. {
26.   return (2 * i) + 1;
27. }
29. int right(int i)
30. {
31.   return (2 * i) + 2;
32. }
34. void heapify(int a[], int i)
35. {
36.   int l = left(i), great;
37.   int r = right(i);
38.   if ( (a[l] > a[i]) && (l < heapSize))
39.  {
40.     great = l;
41.   }
42.   else {
43.     great = i;
44.   }
45.   if ( (a[r] > a[great]) && (r < heapSize))
46.  {
47.     great = r;
48.   }
49.   if (great != i)
50.  {
51.     int temp = a[i];
52.     a[i] = a[great];
53.     a[great] = temp;
54.     heapify(a, great);
55.   }
56. }
58. void BuildMaxHeap(int a[])
59. {
60.  for (int i = (heapSize - 1) / 2; i >= 0; i--)
61.  {
62.     heapify(a, i);
63.     print(a);
64.   }
65. }
67. void HeapSort(int a[]) {
68.   BuildMaxHeap(a);
69.   for (int i = heapSize; i > 0; i--)
70.  {
71.     int temp = a[0];
72.     a[0] = a[heapSize - 1];
73.     a[heapSize - 1] = temp;
74.     heapSize = heapSize - 1;
75.     heapify(a, 0);
76.   }
78. }
80. void main()
81. {
82.   int arr[] = {2, 9, 3, 6, 1, 4, 5, 7, 0, 8};
83.   HeapSort(arr);
84.   print(arr);
85. }