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)