Tìm kiếm quick sort và heap sort

Quick Sort

Quick sort là phương pháp đổi chỗ từng phần (partition exchange), đây là phương pháp rất hiệu quả, rất thông dụng..
Nội dung của phương pháp này như sau:
Chọn một nút bất kỳ trong danh sách(Giả sử là nút đầu tiên) gọi là nút làm trục (pivot node), xác định vị trí hợp lệ của nút này trong danh sách (gọi là vị trí pivot).
Tiếp theo chúng ta phân hoạch các nút còn lại trong danh sách cần sắp xếp sao cho từ vị trí 0 đến vị trí pivot-1 đều có nội dung nhỏ hơn hoặc bằng nút làm trục, các nút từ vị trí pivot+1 đến n-1 đều có nội dung lớn hơn nút làm trục.
Quá trình lại tiếp tục như thế với hai danh sahs con từ trị trí 0 đến vị trí pivot-1 và từ vị trí pivot+1 đến vị trí n-1, ... Sau cùng chúng ta sẽ được danh sách có thứ tự.

Mô tả giải thuật Quick sort

Giai thuat: QuickSort(nodes[], low, up)
Mo Ta; Giair thuat QuickSort, dung phuong phap de qui sawp xep va cac nut trong danh sach giua hai vi tri
  low va up
Du Lieu nhap:
 - Danh sach cac nut chua sap xep (giua hai vi tri low va up)
       - low va up
Du Lieu Xuat:
 Danh sach cac nut (giua hai vi tri low va up) da duoc sap xep

Hanh dong
 if(low >= up) // dieu kien dung
   ket thuc giai thuat
  if(low < up)
   - Phan hoach: partition(nodes[], low, up, pivot)
      + partition phan danh sach thanh ba phan:
           * nut lam truc: nodes[low] tro thanh nodes[pivot]
           * danh sach con 1: nodes[i] <= nodes[pivot]
            (voi i < pivot)
           * danh sach con 2: nodes[i] > nodes[pivot]
            (voi i > pivot)
     - Goi de qui: QuickSort(nodes[], low, pivot-1)
     - Goi de qui: QuickSort(nodes[], pivot+1, up)
Ket Thuc

Giải thuật Partion
vấn đề tiếp theo là giải thuật partition giúp phân danh sách làm ba phần:

• Nút đầu (nút làm trục) đặt ở vị trí pivot
• Danh sách con 1 từ vị trí low đến pivot-1 có nội dung nhỏ hơn hay bằng nút làm trục.
• Danh sách con 2 từ vị trí low đến pivot+1 có nội dung lớn hơn hay bằng nút làm trục.

Người ta xử lý giải thuật partition theo mô tả như sau:
1. Chọn nodes[low] (nút đầu tiền) là nút làm trục.
2. Quét danh sách theo hai hướng để đổi chỗ các cặp nút "sai" vị trí, nơi gặp nhau của hai hướng quét chính là vị trí pivot:
Quét từ low lên: con trỏ l xuất phát từ vị trí low và tăng dần lên, dừng lại khi gặp nút có nội dung lớn hơn nút làm trục, ghi nhận vị trí l lúc này.

• Quét từ up xuống: con trỏ u xuất phát từ vị trí up và giảm dần xuống, dừng lại khi gặp nút có nội dung nhỏ hơn hay bằng nút làm trục, ghi nhận vị trí u lúc này.
• Đổi chỗ hai nút tại vi trí l và u.
• Cứ tiếp tục quét theo hai hướng và đổi chỗ các cặp nút "sai" vị trí, quá trình này dừng lại khi l = u (hai hướng quét gặp nhau), nợi gặp nhau chính là vị trí pivot (pivot = u = l).

3. Đổi chỗ hai nút tại vị trí low (nút làm trục) và nút tại vị trí pivot.

Sau đây là giải thuật partition

Giai Thuat: partition(nodes[], low, up, pivot)
Mo Ta: Giai thuat partition, phan danh sach thanh 3 phan ...
Du Lieu Nhap:
 Danh sach cac nut trong khoang vi tri tu low den up.
Du Lieu Xuat:
 Dua nut lam truc ve vi tri pivot, doi cho cac nut trong danh sach
  sao cho cac nut co noi dung nho hon hay bang nut lam truc duoc
  bo tri truoc nut lam truc, cac nut co noi dung lon hon nut lam
  truc duoc bo tri sau nut lam truc.
Hanh Dong
 1. Chon nodes[low] la nut lam truc
  Gan: l = low;
        u = up;
  2. while(l < u) // vong lap xu ly hai huong quet
   {
          Quet huong tu low len, dung lai khi gap nut lon hon nut lam truc,
          ghi nhan vi tri l luc nay

          Quet huong tu up xuong, dung lai khi gap nut nho hon hay bang
          nut lam truc, ghi nhan vi tri u luc nay

          Doi cho hai nut tai hai vi tri l va u
     }

  3. Doi cho hai nut tai hai vi tri low va u (luc nay pivot = u)
Ket Thuc

Cài đặt giải thuật QuickSort
Sau đây là hàm QuickSort() dùng phương pháp đệ qui, hàm này có gọi hàm partition() để phân hoạch danh sách con thành 3 phần.
Hàm QuickSort()

void QuickSort(int nodes[], int low, int up)
{
int pivot;
if(low >= up) // dieu kien dung
return;

if(low < up)
{
partition(nodes, low, up, &pivot);
QuickSort(nodes, low, pivot - 1);
QuickSort(nodes, pivot + 1, up);
}
}

Hàm partition():

void partition(int nodes [], int low, int up, int *pivot)
{
int nuttruc, l, u, temp;
nuttruc = nodes[low]; // Chon nut dau lam nut truoc
l = low;
u = up;
while(l < u)
{
while(nodes[l] <= nuttruc && l < up)
l++;
while(nodes[u] > nuttruc)
u--;
if(l < u)
{
// doi cho cap nut sai vi tri
temp = nodes[l];
nodes[l] = nodes[u];
nodes[u] = temp;
}
}
// doi cho hia nut tai low va u (luc nay u la vi tri nut truc)
nodes[low] = nodes[u];
nodes[u] = nuttruc;
*pivot = u;
}

Nhận xét, so sánh

• Quick Sort phức tạp hơn Bubble Sort nhưng hiệu quả hơn.
• Quick Sort thích hợp cho danh sách ban đầu chưa có thứ tự.
• Quick Sort kém hiệu quả khi danh sách ban đầu gần có thứ tự. Đặc biệt với danh sách dã có thứ tự (lớn dần hoặc nhở dần) lại là trường hợp xấu nhất của giải thuật Quick Sort.

Chương trình minh họa sắp xếp một mảng kiểu int

#include
#include
void partition(int nodes [], int low, int up, int *pivot);
void QuickSort(int nodes[], int low, int up)
{
int pivot;
if(low >= up) // dieu kien dung
return;
if(low < up)
{
partition(nodes, low, up, &pivot);
QuickSort(nodes, low, pivot - 1);
QuickSort(nodes, pivot + 1, up);
}
}

void partition(int nodes [], int low, int up, int *pivot)
{
int nuttruc, l, u, temp;
nuttruc = nodes[low]; // Chon nut dau lam nut truoc
l = low;
u = up;
while(l < u)
{
while(nodes[l] <= nuttruc && l < up)
l++;
while(nodes[u] > nuttruc)
u--;
if(l < u)
{
// doi cho cap nut sai vi tri
temp = nodes[l];
nodes[l] = nodes[u];
nodes[u] = temp;
}
}
// doi cho hia nut tai low va u (luc nay u la vi tri nut truc)
nodes[low] = nodes[u];
nodes[u] = nuttruc;
*pivot = u;
}


void main()
{
int mang[7];
for(int i = 0;i < 7;i++)
{
cout<<"Nhap vao phan tu thu "<<(i+1)<<": ";
cin>>mang[i];
}
cout<<endl;
for(int i = 0;i < 7;i++)
{
cout<<mang[i]<<" ";
}
QuickSort(mang, 0, 7);
cout<<endl<<endl<<"danh sach sau khi da sap xep: ";
for(int i = 0;i < 7;i++)
{
cout<<mang[i]<<" ";
}
getch();
}

Heap Sort

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).
Xem thêm chi tiết tại đây.
http://www.uit.edu.vn/data/gtrinh/TH103/Htm/Bai04.htm

#include <>
#include <>
int heapSize = 10;
void print(int a[])
{
for (int i = 0; i <= 9; i++)
{
cout << a[i] << "-";
}
cout << endl;
}

int parent(int i)
{
if(i==1)
return 0;

if(i%2==0)
return ( (i / 2)-1);
else
return ( (i / 2));
}

int left(int i)
{
return (2 * i) + 1;
}

int right(int i)
{
return (2 * i) + 2;
}

void heapify(int a[], int i)
{
int l = left(i), great;
int r = right(i);
if ( (a[l] > a[i]) && (l < heapSize))
{
great = l;
}
else {
great = i;
}
if ( (a[r] > a[great]) && (r < heapSize))
{
great = r;
}
if (great != i)
{
int temp = a[i];
a[i] = a[great];
a[great] = temp;
heapify(a, great);
}
}

void BuildMaxHeap(int a[])
{
for (int i = (heapSize - 1) / 2; i >= 0; i--)
{
heapify(a, i);
print(a);
}
}

void HeapSort(int a[]) {
BuildMaxHeap(a);
for (int i = heapSize; i > 0; i--)
{
int temp = a[0];
a[0] = a[heapSize - 1];
a[heapSize - 1] = temp;
heapSize = heapSize - 1;
heapify(a, 0);
}

}

void main()
{
int arr[] = {2, 9, 3, 6, 1, 4, 5, 7, 0, 8};
HeapSort(arr);
print(arr);
}