Ứng dụng thuật toán sắp xếp trong việc dạy BD HSG

Nguyễn Hoàng Trọng Lộc

Trường THPT chuyên Thoại Ngọc Hầu

​

​

Cuộc sống luôn chứa đựng quá nhiều vấn đề khiến chúng ta mệt mỏi.

Dẹp hết đi hoặc sắp xếp lại mọi thứ, biết đâu bạn sẽ cảm thấy ổn hơn.

​

1

I. Các thuật toán sắp xếp thông dụng

• Sắp xếp đổi chỗ trực tiếp (interchange sort)
• Sắp xếp nổi bọt (buble sort)
• Sắp xếp chèn (insertion sort)
• Sắp xếp chọn (selection sort)
• Sắp xếp nhanh (quick sort)
• Sắp xếp bằng đếm phân phối (counting sort)

2

1. Sắp xếp nhanh

3

1. Sắp xếp nhanh

4

void QuickSort(int a[], int L, int R)

{

int i, j, mid;

i = L, j = R;

mid = a[(L+R)/2];

while(i <= j)

{

while(a[i] < mid) i++;

while(a[j] > mid) j--;

if(i <= j)

{

Swap(a[i], a[j]);

i++, j--;

}

}

if(i < R) QuickSort(a, i, R);

if(L < j) QuickSort(a, L, j);

}

2. Sắp xếp bằng đếm phân phối

5

2. Sắp xếp bằng đếm phân phối

6

Dãy sau khi sắp xếp: 0, 0, 1, 2, 2, 2, 3, 5

2. Sắp xếp bằng đếm phân phối

7

#include <bits/stdc++.h>

#define N 1005

using namespace std;

int a[N], n, c[1000001];

int main() {

cin >> n;

for (int i = 0; i < 1000001; i++)

c[i] = 0;

for (int i = 0; i < n; i++) {

cin >> a[i];

c[a[i]]++;

}

for (int i = 0; i < 1000001; i++)

if (c[i] != 0)

for (int j = 1; j <= c[i]; j++)

cout << i << " ";

return 0;

}

II. Hàm sort trong thư viện C++

8

II. Hàm sort trong thư viện C++

9

II. Hàm sort trong thư viện C++

• Ví dụ: Ta có kiểu dữ liệu phân số có cấu trúc như sau:

struct PhanSo

{

long long ts;

long long ms;

};

• Để sắp xếp mảng phân số không giảm, ta viết hàm cmp như sau:

bool cmp(PhanSo x, PhanSo y)

{

return (double)x.ts/x.ms < (double)y.ts/y.ms;

}

​

10

#include <bits/stdc++.h>

using namespace std;

struct PhanSo

{

long long ts;

long long ms;

};

PhanSo a[100005];

long long n;

bool cmp(PhanSo x, PhanSo y)

{

return (double)x.ts/x.ms < (double)y.ts/y.ms;

}

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

{

cin >> a[i].ts;

cin >> a[i].ms;

}

sort(a+1, a+1+n, cmp);

for(int i = 1; i <= n; i++)

cout << a[i].ts << "/" << a[i].ms << " ";

}

11

III. Bài tập vận dụng thuật toán sắp xếp

1. Sắp xếp dãy số
2. Sắp xếp ký tự H, O, A
3. Số nhỏ nhất
4. Dãy liên tục
5. Cặp đôi hoàn hảo
6. Đội văn nghệ
7. Xếp hình chữ nhật
8. Cặp số bằng nhau
9. Đội tình nguyện viên
10. Sắp xếp trị tuyệt đối
11. Sắp xếp sinh viên

12

1. Sắp xếp dãy số

• Ý tưởng:
• Do đề bài n nhỏ (tối đa là 1000) nên ta có thể dùng các thuật toán sắp xếp thông thường là có thể full điểm bài này.
• Ở đây mình sẽ dùng 2 cách: đếm phân phối và dùng hàm sort có sẵn trong C++.

​

1. Sắp xếp dãy số

#include <bits/stdc++.h>

#define N 1005

using namespace std;

int n;

int c[1000005] = {}; // Cac phan tu cua mang c la 0

int main()

{

cin >> n;

int mx = INT_MIN, mi = INT_MAX;

for(int i = 1; i <= n; i++)

{

int x;

cin >> x;

c[x]++;

if(x > mx) mx = x;

if(x < mi) mi = x;

}

for(int i = mi; i <= mx; i++)

if (c[i] != 0)

cout << i << " ";

return 0;

}

#include <bits/stdc++.h>

#define N 1005

using namespace std;

int a[N], n;

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

cin >> a[i];

sort(a + 1, a + n + 1);

for(int i = 1; i <= n; i++)

cout << a[i] << " ";

return 0;

}

​

2. Sắp xếp ký tự H, O, A

• Ý tưởng:

+ Lưu dữ liệu đọc được vào mảng c theo quy ước:

c[1] dùng để đếm tần suất xuất hiện của ký tự ‘H’

c[2] dùng để đếm tần suất xuất hiện của ký tự ‘O’

c[3] dùng để đếm tần suất xuất hiện của ký tự ‘A’

+ Sử dụng đếm phân phối vào mảng c với min là 1, max là 3.

​

2. Sắp xếp ký tự H, O, A

#include <bits/stdc++.h>

#define N 5

using namespace std;

int c[N] = {}, n;

char kytu[4] = {' ','H','O','A'};

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

{

char x;

cin >> x;

if(x == 'H') c[1]++;

if(x == 'O') c[2]++;

if(x == 'A') c[3]++;

}

for(int i = 1; i <= 3; i++)

for(int j = 1; j <= c[i]; j++)

cout << kytu[i] << " ";

return 0;

}

3. Số nhỏ nhất

• Ý tưởng: Đếm phân phối
• Dùng các chỉ số từ 0 đến 200: phần tử c[0] dùng để đếm số -100, c[1] dùng để đếm số -99, …

=> Khi đọc vào giá trị x, thì ta đếm cho c[x+100].

- Khi xuất giá trị thì ta trừ lại 100

3. Số nhỏ nhất

#include <bits/stdc++.h>

#define N 103

using namespace std;

int n;

int c[203] = {};

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

{

int x;

cin >> x;

c[x+100]++;

}

for(int i = 0; i <= 200; i++)

if(c[i] == 1)

{

cout << i-100;

return 0;

}

cout << "khong";

return 0;

}

4. Dãy liên tục

4. Dãy liên tục

#include <bits/stdc++.h>

#define N 1000005

using namespace std;

int c[N] = {}, n, cnt = 0;

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

{

int x;

cin >> x;

if(c[x] == 0 && x <= n)

{

c[x]++;

cnt++;

}

}

cout << n-cnt;

return 0;

}

5. Cặp đôi hoàn hảo

• Ý tưởng:
• Sắp xếp dãy số tăng dần
• Xét chênh lệch giữa 2 số gần nhau để tìm ra chênh lệch nhỏ nhất.

5. Cặp đôi hoàn hảo

#include <bits/stdc++.h>

#define N 100005

using namespace std;

int a[N], n;

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

cin >> a[i];

sort(a+1, a+n+1);

int res = a[2] - a[1];

for(int i = 3; i <= n; i++)

if(a[i] - a[i-1] < res)

res = a[i] - a[i-1];

cout << res;

return 0;

}

6. Đội văn nghệ

• Ý tưởng:
• Sắp xếp dãy số.
• Ứng với mỗi 5 phần tử liên tiếp, ta xét độ chênh lệch giữa phần tử nhỏ nhất và phần tử lớn nhất để tìm ra được độ chênh lệch thấp nhất.

6. Đội văn nghệ

#include <bits/stdc++.h>

#define N 100005

using namespace std;

int a[N], n;

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

{

cin >> a[i];

}

sort(a+1, a+n+1);

int res = a[5] - a[1];

for(int i = 6; i <= n; i++)

if(a[i] - a[i-4] < res)

res = a[i] - a[i-4];

cout << res;

return 0;

}

7. Xếp hình chữ nhật

7. Xếp hình chữ nhật

#include <bits/stdc++.h>

#define N 200005

using namespace std;

int a[N], n;

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

cin >> a[i];

sort(a+1, a+n+1, greater<int>());

int i = 1, x = 0, y = 0;

while((i < n) && (x == 0))

if (a[i] == a[i+1])

x = a[i];

else i++;

i = i + 2;

while((i < n) && (y == 0))

if (a[i] == a[i+1])

y = a[i];

else i++;

cout << (long long)x*y;

return 0;

}

8. Cặp số bằng nhau

8. Cặp số bằng nhau

#include <bits/stdc++.h>

#define N 100005

#define ll long long

using namespace std;

int a[N], n;

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

cin >> a[i];

sort(a+1, a+n+1);

int i = 1;

ll res = 0;

while(i < n)

{

int csd = i;

ll x;

while(i < n && a[i] == a[i+1])

i++;

x = i - csd + 1;

res = res + (x*(x-1) / 2);

i++;

}

cout << res << endl;

return 0;

}

9. Đội tình nguyện viên

• Ý tưởng:
• Sắp xếp dãy số.
• Ứng với mỗi giá trị số, ta tìm số lượng số giống nhau nhiều nhất trong dãy.

9. Đội tình nguyện viên

#include <bits/stdc++.h>

#define N 100005

using namespace std;

int a[N], n;

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

cin >> a[i];

sort(a+1, a+n+1);

int res_h = a[1], res_sl = 1, i = 1;

while(i <= n)

{

int csd = i, sl;

while((i < n) && (a[i] == a[i+1]))

i++;

sl = i - csd + 1;

if(sl >= res_sl)

{

res_sl = sl;

res_h = a[i];

}

i++;

}

cout << res_h << " " << res_sl;

return 0;

}

10. Sắp xếp giá trị tuyệt đối

• Ý tưởng:
• Bài này đơn giản là ta sắp xếp dãy số, nhưng sắp xếp theo quy ước của đề bài (viết thêm hàm cmp để so sánh 2 giá trị).

10. Sắp xếp giá trị tuyệt đối

#include <bits/stdc++.h>

#define N 1000006

using namespace std;

int a[N], n;

bool cmp(int a, int b)

{

return abs(a) < abs(b);

}

int main()

{

cin >> n;

for(int i = 1; i <= n; i++)

cin >> a[i];

sort(a + 1, a + n + 1, cmp);

for(int i = 1; i <= n; i++)

cout << a[i] << " ";

return 0;

}

11. Sắp xếp sinh viên

• Ý tưởng:
• Bài này đơn giản là ta sắp xếp dãy số, nhưng sắp xếp theo quy ước của đề bài (viết thêm hàm cmp để thể hiện cách so sánh giữa 2 sinh viên).

11. Sắp xếp sinh viên

#include <bits/stdc++.h>

#define N 1005

using namespace std;

struct sinhvien {

int id;

string hoten;

int cao;

};

sinhvien a[N];

int n;

bool cmp(sinhvien x, sinhvien y) {

if (x.cao == y.cao && x.hoten == y.hoten)

return x.id < y.id;

else if (x.cao == y.cao)

return (x.hoten < y.hoten);

else

return x.cao < y.cao;

}

int main() {

cin >> n;

for (int i = 1; i <= n; i++) {

a[i].id = i;

cin >> a[i].hoten >> a[i].cao;

}

sort(a + 1, a + n + 1, cmp);

for (int i = 1; i <= n; i++) cout << a[i].id << " ";

return 0;

}