Sắp xếp mảng

Go down

Sắp xếp mảng

Bài gửi by ASSASSiN on Thu Nov 22, 2007 5:09 pm

Sắp xếp mảng



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:
Code:
function sort(A){
        for(i = 1; i < n; i++){
                j = i;
                for(k = i + 1; k <= n; k ++)
                        if (A[k] < A[j])
                                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:
Code:
function sort(A){
        A[0] = VO_CUNG;
        for(i = 2; i <= n; i++){
                x = A[i];
                j = i – 1;
                while(x < A[j]){
                        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:
Code:
function sort(A){
        for(i = 2; i <= n; i++)
                for(j = n; j > i; j--)
                        if (A[j] < A[j - 1])
                                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)
Code:
function sort(A){
        i = 2;
        do{
                flag = true;
                for (j = n; j > i; j--)
                        if (A[j] < A[j - 1]){
                                swap(A[j], A[j - 1]);
                                flag = false;
                        }

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

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

_________________
Hãy REPLY để ủng hộ BOTAY nhé!
avatar
ASSASSiN
♥ Strong Chicken ♥
♥ Strong Chicken ♥

Tổng số bài gửi : 329
Age : 31
Location : Việt Nam
Registration date : 05/10/2007

Xem lý lịch thành viên http://botay.1talk.net

Về Đầu Trang Go down

Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết