Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Sunday, April 5, 2015

Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên việc phân hoạch dãy ban đầu thành 3 phần :

Phần 1: Gồm các phần tử  có giá trị bé hơn x
Phần 2: Gồm các phần tử  có giá trị bằng  x
Phần 3: Gồm các phần tử  có giá trị lớn hơn x
với x là giá trị của một phần tử  tùy ý trong dãy ban đầu.
Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn:
1. ak  ≤ x , với k = 1 .. j
2. ak  = x , với k =  j+1 .. i-1
3. ak   x , với k =  i..N

Đoạn thứ 2 đã có thứ tự.
Nếu các đoạn 1 và 3 chỉ có 1 phần tử  : đã có thứ tự
 khi đó dãy con ban đầu đã được sắp.
Đoạn thứ 2 đã có thứ tự.
Nếu các đoạn 1 và 3  có nhiều hơn 1 phần tử  thì dãy ban đầu chỉ có thứ tự khi các đoạn 1, 3 được sắp.
Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày …
Bước 1: Nếu left ≥ right //dãy có ít hơn 2 phần tử
Kết thúc; //dãy đã được sắp xếp
Bước 2: Phân hoạch dãy aleft … aright thành các đoạn: aleft.. aj, aj+1.. ai-1, ai.. aright
Đoạn 1  x
Đoạn 2: aj+1.. ai-1  = x
Đoạn 3: ai.. aright   x
Bước 3: Sắp xếp đoạn 1: aleft.. aj
Bước 4: Sắp xếp đoạn 3: ai.. aright


Bước 1 : Chọn tùy ý một phần tử  a[k] trong dãy là giá trị mốc ( l ≤ k ≤ r):  
x = a[k];   i = l;  j = r;
Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử
a[i], a[j] nằm sai chỗ :
Bước 2a : Trong khi (a[i]<x) i++;
Bước 2b : Trong khi (a[j]>x) j--;
Bước 2c : Nếu  i< j Swap(a[i],a[j]);
Bước 3 : Nếu  i < j: Lặp lại Bước 2.   Ngược lại: Dừng

void QuickSort(int a[], int left, int right)
{ int i, j, x;
x = a[(left+right)/2]; 
i = left; j = right;
  do
{
    while(a[i] < x) i++;
    while(a[j] > x) j--;
      if(i <= j)

Swap(a[i],a[j]);
        i++ ; j--;
}
} while(i <= j);

if(left<j)
QuickSort(a, left, j);
if(i<right)
QuickSort(a, i, right);
}

0 comments:

Post a Comment

Popular Posts