Search
Latest topics
Quick sort
Page 1 of 1
Quick sort
Đây là giả thuật sắp xếp nhanh, chỉ tốn O(nlogn). Cài đặt của giả thuật tương đối phức tạp. Chúng ta cần chú ý đến:
Pivot: ta gọi là chốt
Partition: Gọi là điểm phân hoạch
Đối với giải thuật này, chúng ta xem 1 mảng 1 phần tử hay mảng có tất cả phần tử giống nhau là một mảng có thứ tự. Ta sẽ chi mảng thành 2 mảng con: Trái và phải. Sắp xếp 2 mảng con, và cứ như thế cho đến khi mảng còn 1 phần tử. Nếu mảng Trái đã có thứ tự và mảng phải cũng có thứ tự thì mảng của chúng ta đã là mảng có thứ tự.
A = {59, 31, 12, 33, 27, 97, 91, 19, 18, 63 }
Bước 1: Tìm chốt: Chốt là phần tử lớn nhất trong 2 phần tử khác nhau đầu tiên của mảng. Nếu mảng có 1 phần tử tất cả phần tử bằng nhau sẽ không có chốt:
Chốt của mảng trên la 59 (vị trí 0).
VD:
+ 1, 1, 5, 3, 2 -> chốt sẽ là 5
+ 5, 5, 5, 3, 1, 2, 3 -> chốt là 5
+ 6 -> không có chốt
+ 7, 7, 7, 7 -> không có chốt
Bước 2: Tìm điểm phân hoạch:
+ Dùng 2 cờ: L (trái) và R (Phải)
+ L chạy từ trái qua, dừng lại khi gặp phần tử >= pivot
+ R chạy từ phải qua, dừng lại khi gặp phần tử < pivot
+ Tại điểm dùng: Nếu L < R : Chúng ta sẽ swap A[L] và A[R]
+ Dừng lại khi L > R
+ Partition sẽ là L. Đây sẽ là chỉ số đầu tiên của mảng bên phải
VD: với mảng A = {59, 31, 12, 33, 27, 97, 91, 19, 18, 63 }
PivotLey = 59
L = 0, R = 9:
b1. L dừng lại tại vị trí 0: vì A[L] >= pivot, R dừng lại tại vị trí 8, vì A[R] = 18 < pivot.
Swap: 18, 31, 12, 33, 27, 97, 91, 19, 59, 63
b2, tiếp tục cho đến khi L > R
Bước 3: Lặp lại như thế (Dùng đệ qui)
Pivot: ta gọi là chốt
Partition: Gọi là điểm phân hoạch
Đối với giải thuật này, chúng ta xem 1 mảng 1 phần tử hay mảng có tất cả phần tử giống nhau là một mảng có thứ tự. Ta sẽ chi mảng thành 2 mảng con: Trái và phải. Sắp xếp 2 mảng con, và cứ như thế cho đến khi mảng còn 1 phần tử. Nếu mảng Trái đã có thứ tự và mảng phải cũng có thứ tự thì mảng của chúng ta đã là mảng có thứ tự.
A = {59, 31, 12, 33, 27, 97, 91, 19, 18, 63 }
Bước 1: Tìm chốt: Chốt là phần tử lớn nhất trong 2 phần tử khác nhau đầu tiên của mảng. Nếu mảng có 1 phần tử tất cả phần tử bằng nhau sẽ không có chốt:
Chốt của mảng trên la 59 (vị trí 0).
VD:
+ 1, 1, 5, 3, 2 -> chốt sẽ là 5
+ 5, 5, 5, 3, 1, 2, 3 -> chốt là 5
+ 6 -> không có chốt
+ 7, 7, 7, 7 -> không có chốt
Bước 2: Tìm điểm phân hoạch:
+ Dùng 2 cờ: L (trái) và R (Phải)
+ L chạy từ trái qua, dừng lại khi gặp phần tử >= pivot
+ R chạy từ phải qua, dừng lại khi gặp phần tử < pivot
+ Tại điểm dùng: Nếu L < R : Chúng ta sẽ swap A[L] và A[R]
+ Dừng lại khi L > R
+ Partition sẽ là L. Đây sẽ là chỉ số đầu tiên của mảng bên phải
VD: với mảng A = {59, 31, 12, 33, 27, 97, 91, 19, 18, 63 }
PivotLey = 59
L = 0, R = 9:
b1. L dừng lại tại vị trí 0: vì A[L] >= pivot, R dừng lại tại vị trí 8, vì A[R] = 18 < pivot.
Swap: 18, 31, 12, 33, 27, 97, 91, 19, 59, 63
b2, tiếp tục cho đến khi L > R
Bước 3: Lặp lại như thế (Dùng đệ qui)
- Code:
// Tìm chốt
public int findPivot(int i, int j, int[] array) {
if (array.length == 1) {
return -1;
}
int k = i + 1;
int pivot = array[i];
while ((k <= j) && (array[k] == pivot)) {
k++;
}
if (k > j) {
return -1;
}
if (array[k] > pivot) {
return k;
} else {
return i;
}
}
// Tìm partition
public int pointPartition(int i, int j, int pivotKey, int[] array) {
int partition = -1;
int L = i;
int R = j;
while (L <= R) {
while (array[L] < pivotKey)
L++;
while (array[R] >= pivotKey)
R--;
if (L < R) {
int temp = array[L];
array[L] = array[R];
array[R] = temp;
}
}
partition = L;
return partition;
}
// Sắp xếp
public void quickSort(int i, int j, int[] array) {
int pivot = findPivot(i, j, array);
if (pivot == -1)
return;
int partition = pointPartition(i, j, array[pivot], array);
quickSort(i, partition - 1, array);
quickSort(partition, j, array);
}
// Test:
quickSort(0, array.length - 1, array);
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
Thu Aug 23, 2012 5:38 am by Admin
» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin
» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin
» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin
» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin
» Giá của món quà
Fri Apr 13, 2012 6:01 am by Admin
» Sẽ chỉ yêu ai?
Fri Apr 13, 2012 6:01 am by Admin
» Cách đọc bảng chữ cái!
Thu Apr 12, 2012 10:37 pm by Admin
» Gắn trojan, keylog, virus vào website, forum
Tue Apr 10, 2012 1:14 am by Admin