Thuật toán sắp xếp tuần tự

Bài toán đặt ra

Cho mảng A gồm n phần tử. Sắp xếp lại dãy A theo chiều giảm dần

Nhập vào: số nguyên dương n và dãy A.

8
9 7 6 15 16 5 10 11
Xuất ra: dãy A sau khi đã được sắp xếp
5 6 7 9 10 11 15 16

Ý tưởng

Tư duy đơn giản như cách chúng ta xếp bài

sap-xep-1-yeulaptrinhHình trên là thao tác xếp cây bài 7 bằng cách rút nó ra và đặt vào vị trí của phù hợp.

Giải sử bài trên tay đang là:

2 5 7 10 4

ta thấy dãy 2,5,7,10 đã tăng dần chỉ còn cây 4 đứng chưa đúng chỗ nên ta đẩy 4 lên trước 10, rồi lên trước 7 cứ như vậy đến khi gặp cây 2 đứng trước. 2 < 4 suy ra thì dừng. Dãy trở thành

2 4 5 7 10

Dãy đã được sắp xếp.

Ý tưởng: duyệt lần lượt từng cây bài, nếu cây bài nhỏ thì ta đẩy dần lên đầu đến khi nào không chuyển lên được nữa

Ví dụ khác:

sap-xep-yeulaptrinh.pwCode:

#include <bits/stdc++.h>

using namespace std;

int n, a[10000];

void doi_cho(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<i; j++)
            if (a[j] > a[i])
            {
                doi_cho(&a[i], &a[j]);
            }
    }
    for (int i=1; i<=n; i++) cout << a[i] << " ";
    return 0;
}
Ví dụ:

Với dãy A = {12, 11, 13, 5, 6}

Cho i chạy từ 1 đến 4

i=1. không làm gì cả

12, 11, 13, 5, 6

i = 2. Vì 11 nhỏ hơn 12 nên chuyển 11 lên trước 12
11, 12, 13, 5, 6

i = 3. 13 không cần chuyển lên đầu nữa
11, 12, 13, 5, 6

i = 4. 5 được chuyển chỗ với 13 rồi chuyển chố tiếp lần lượt với 12, 11.
5, 11, 12, 13, 6

i = 5. 6 cũng giông như 5 được chuyển dần lên đến khi gặp 5 nhỏ hơn thì dừng lại
5, 6, 11, 12, 13

Độ phức tạp:

  • O(n^2)

 

Quý bạn đọc có ý kiến, thắc mắc xin comment bên dưới <3

Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*