Saturday, October 27, 2007

Thuật toán sắp xếp: Quick Sort (P.2)

Thuật toán Quick Sort
o Ý tưởng
Ta chọn một phần tử bất kỳ của mảng A giả sử đó là x
Lọc và chia mảng đó thành 3 mảng con:
- mảng A1: A1(i) <>
- mảng A2: A2(i) = x với mọi i
- mảng A3: A3(i) > x với mọi i
Sau đó ta lại tiếp tục các bước trên với mảng A1 và A3. Công việc này còn được gọi là phân hoạch nên Quick Sort còn được gọi là sắp xếp theo phương pháp phân hoạch
Giải thuật này sẽ được cài đặt theo phương pháp đệ qui

o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

function quickSort(A, lower, upper){
x = A[(lower + upper) / 2];
i = lower;
j = upper;
do{
while(A[i] <>
i ++;
while (A[j] > x)
j --;
if (i <= j){
swap(A[i], A[j]);
i ++;
j --;
}
}while(i <= j);
if (j > lower)
quickSort(A, lower, j);
if (i <>
quickSort(A, i, upper);
}


o Độ phức tạp tính toán: O(nlnn)

Thuật toán Quick Sort tốt nhất trong trường hợp dãy hầu như được sắp xếp và với n khá lớn. Vì vậy ta thường dung Quick Sort trong giai đoạn đầu để phân hoạch, khi đoạn con đủ nhỏ ta sẽ dùng các phương pháp khác để sắp xếp

Friday, October 26, 2007

Sắp xếp mảng (P.1)

Sắp xếp mảng số nguyên một chiều A theo thứ tự tăng dần (hoặc giảm dần)


1.Thuật toán sắp xếp kiểu chọn lựa
o Ý tưởng
Giả sử ta đã sắp xếp mảng cho đến phần tử thứ i – 1 theo thứ tự tăng dần.
Ở bước thứ i ta chọn phần tử có giá trị nhỏ nhất trong đoạn A[i..n], giả sử A(j), ta thực hiện đổi chỗ A(i) với A(j)

o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

function sort(A){
for(i = 1; i <>
j = i;
for(k = i + 1; k <= n; k ++)
if (A[k] <>
j = k;
swap(A[i], A[j]);
}
}



o Độ phức tạp tính toán: O(n2)

2. Thuật toán sắp xếp kiểu chèn
o Ý tưởng
Giả sử ta đã sắp xếp mảng cho đến phần tử thứ i -1 theo thứ tự tăng dần.
Ở bước thứ i sẽ thực hiện chèn giá trị A(i) vào dãy con A[1..i] sao cho dãy vẫn giữa được trật tự sắp xếp cũ (ý tưởng như vậy ta xếp các quân bài Tú – lơ – khơ từ 1 đến K)
Ta thực hiện như sau: Xuất phát từ j = i -1 xét trở về phía trước
- nếu A(j) <= x = A(i): ta đặt x vào vị trí j + 1
- nếu A(j) > x: ta gán A(j) vào cho A(j + 1), sau đó quay về phía trước 1 phần tử và tiếp tục lại quá trình này
Để bài toán thực hiện được theo ý tưởng này thì ở đầu mảng phải có 1 phần tử làm mốc A(0) không phải thuộc mảng gốc, nó chỉ đóng vai trò là giá trị ‘vô cực’ mà thôi

o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

function sort(A){
A[0] = VO_CUNG;
for(i = 2; i <= n; i++){
x = A[i];
j = i – 1;
while(x <>
A[j + 1] = A[j];
j --;
}
A[j] = x;
}
}


o Độ phức tạp tính toán: O(n2)

3. Thuật toán sắp xếp kiểu nổi bột hay đổi chỗ
o Ý tưởng
Giả sử ta đã sắp xếp được mảng đến phần tử i – 1
Tại bước i, ta sẽ duyệt đoạn A[i..n] từ n trở về i, nếu A(j – 1) > A(j) thì đổi chỗ, sau khi duyệt xong đoạn A[i..n] thì đoạn từ 1 đến i được sắp xếp

o Mô tả thuật toán
- Input: Mảng A[1..n]
- Output: Mảng A có thứ tự tăng dần
- Method:

function sort(A){
for(i = 2; i <= n; i++)
for(j = n; j > i; j--)
if (A[j] <>
swap(A[j], A[j - 1]);
}



Ta cũng có thể cải tiến một chút giải thuật trên, mặc dù độ phức tạp tình toán vẫn vậy. Đến khi nào không thấy có việc đổi chỗ nữa (đoạn sau đã có thứ tự sắp xếp thỏa mãn thì ta dừng luôn)

function sort(A){
i = 2;
do{
flag = true;
for (j = n; j > i; j--)
if (A[j] <>
swap(A[j], A[j - 1]);
flag = false;
}

i ++;
}while (flag = true);
}


o Độ phức tạp tính toán: O(n2)

Tìm kiếm trên mảng

1. Thuật toán tìm kiếm nhị phân
o Bài toán
Cho một mảng các số được sắp xếp tăng dần (giảm dần), cho một giá trị x, xác định xem x có thuộc mảng đó hay không

o Ý tưởng
Giả sử mảng sắp xếp tăng dần A, ta chia đôi mảng, so sánh x với phần tử ở giữa A[mid], nếu:
- x == A[mid] : return true
- x > A[mid]: tiếp tục tìm x trong nửa mảng bên phải
- x < A[mid]: tiếp tục tìm x trong nửa mảng bên trái

o Mô tả thuật toán
- Input: mảng A[1..n] giá trí x
- Output:
+ x thuộc A: true
+ else false
- Method :
function binarySearch(A, x, first, last){
if (first > last)

return false;
else{
mid = (first + last) / 2;
if (x == A[mid])
return true;
else if (x < A[mid])
return binarySearch (A, x, first, mid - 1);
else
return binarySearch (A, x, mid + 1, last);
}
}

o Độ phức tạp tính toán: O(lgn)

2. Thuật toán tìm Min Max
o Bài toán
Tìm giá trí Min và Max trong đoạn [left, right] của mảng A[1,n]

o Ý tưởng
Chia mảng đoạn [left, right] thành 2 phần, tìm Min và Max trong 2 phần đó sau đó so sánh 2 kết quả này với nhau. Tiếp tục việc chia 2 cho đến khi đoạn chia chỉ còn 1 phần tử thì Min = Max và bằng phần tử đó

o Mô tả thuật toán
- Input: Mảng A[1..n]
Left và Right
- Output:
Min và Max của đoạn [Left, Right]
- Method:

function minMax(A, left, right, Min, Max){
if (left == right)
Min = Max = A[left];
else{
minMax(A, left, (right + left) / 2, Min1, Max1);
minMax(A, (right + left) / 2 + 1, right, Min2, Max2);
if (Min1 > Min2)
Min = Min2;
else
Min = Min1;
if(Max1 > Max2)
Max = Max1;
else
Max = Max2;
}
}

o Độ phức tạp tính toán: O(n)