Kỹ năng tự viết hàm so sánh khi sử dụng hàm sắp xếp trong thư viện C++/Python

Đỗ Thị Hồng Ngát 13/07/2024
13
Th7

Kỹ năng tự viết hàm so sánh khi sử dụng hàm sắp xếp trong thư viện C++

Hàm so sánh là một khái niệm quan trọng trong lập trình và thuật toán, được sử dụng để xác định thứ tự giữa hai đối tượng. Hàm này trả về một giá trị để chỉ ra mối quan hệ giữa hai đối tượng. Trong các ngôn ngữ lập trình khác nhau, hàm so sánh thường được định nghĩa và sử dụng theo nhiều cách khác nhau.
Bài viết này sẽ giới thiệu về cách viết hàm so sánh khi sử dụng hàm sắp xếp có sẵn trong thư viện trong hai ngôn ngữ C++ và Python.

1. Các giá trị trả về của hàm so sánh

Hàm so sánh thường trả về:

  • Một giá trị âm nếu đối tượng thứ nhất nhỏ hơn đối tượng thứ hai.
  • Một giá trị dương nếu đối tượng thứ nhất lớn hơn đối tượng thứ hai.
  • Giá trị bằng 0 nếu hai đối tượng bằng nhau.

Hoặc

  • Một giá trị True nếu đối tượng thứ nhất đứng trước đối tượng thứ hai trong thứ tự sắp xếp.
  • Một giá trị False nếu đối tượng thứ nhất đứng sau đối tượng thứ hai trong thứ tự sắp xếp.

2. Hàm so sánh mặc định của Pair trong C++

Trong C++, kiểu dữ liệu std::pair cung cấp các phương thức so sánh mặc định để so sánh các cặp giá trị. Các phương thức này bao gồm các toán tử so sánh như <, >, <=, >=, ==, và !=. Các thứ tự so sánh này dựa trên thứ tự từ điển (lexicographical order), nghĩa là so sánh phần tử đầu tiên trước, nếu phần tử đầu tiên bằng nhau thì so sánh phần tử thứ hai.

Khi sử dụng hàm sort, ta chỉ cần viết so sánh như bình thường:

  • sort(a.begin(), a.end())
  • sort(a,a+n)

Các phương thức so sánh mặc định của std::pair trong C++

Toán tử == và !=

  • std::pair được coi là bằng nhau nếu cả hai phần tử của cặp đều bằng nhau.
  • std::pair được coi là không bằng nhau nếu ít nhất một trong hai phần tử không bằng nhau.

Toán tử < và <=

  • std::pair được coi là nhỏ hơn nếu phần tử đầu tiên nhỏ hơn phần tử đầu tiên của cặp so sánh, hoặc nếu phần tử đầu tiên bằng nhau và phần tử thứ hai nhỏ hơn phần tử thứ hai của cặp so sánh.
  • std::pair được coi là nhỏ hơn hoặc bằng nếu nó nhỏ hơn hoặc bằng theo các tiêu chí trên.

Toán tử > và >=

  • std::pair được coi là lớn hơn nếu phần tử đầu tiên lớn hơn phần tử đầu tiên của cặp so sánh, hoặc nếu phần tử đầu tiên bằng nhau và phần tử thứ hai lớn hơn phần tử thứ hai của cặp so sánh.
  • std::pair được coi là lớn hơn hoặc bằng nếu nó lớn hơn hoặc bằng theo các tiêu chí trên.

Ví dụ

#include <iostream>
#include <utility> // for std::pair

int main() {
    std::pair<int, int> pair1 = {1, 2};
    std::pair<int, int> pair2 = {1, 3};
    std::pair<int, int> pair3 = {2, 2};

    // Toán tử ==
    if (pair1 == pair2) {
        std::cout << "pair1 == pair2" << std::endl;
    } else {
        std::cout << "pair1 != pair2" << std::endl;
    }
    // Kết quả: pair1 != pair2

    // Toán tử <
    if (pair1 < pair2) {
        std::cout << "pair1 < pair2" << std::endl;
    } else {
        std::cout << "pair1 >= pair2" << std::endl;
    }
    //Kết quả: pair1 < pair2

    // Toán tử >
    if (pair1 > pair3) {
        std::cout << "pair1 > pair3" << std::endl;
    } else {
        std::cout << "pair1 <= pair3" << std::endl;
    }
    //Kết quả: pair1 <= pair3

    //So sánh với pair lồng nhau
    std::pair<int, pair<int, int>> pair4 = {2, {5 10}};
    std::pair<int, pair<int, int>> pair5 = {3, {1, 2}};
    //Kết quả: pair4 < pair5

    std::pair<pair<int, int>, int> pair6 = {{2,2}, 3};
    std::pair<pair<int, int>, int> pair7 = {{2,1}, 5};
    //Kết quả: pair6 > pair7
    return 0;
}

3. Cách tự viết hàm so sánh trong C++

Để tự viết hàm so sánh cho một struct trong C++ và sử dụng nó để sắp xếp lại một mảng (hoặc vector) các đối tượng của struct, bạn có thể định nghĩa một hàm so sánh tùy chỉnh và truyền nó cho sort. Dưới đây là một ví dụ minh họa chi tiết về cách thực hiện điều này.

Ví dụ
Giả sử bạn có một struct tên là Person với các thuộc tính name và age. Bạn muốn sắp xếp một vector các đối tượng Person theo tuổi (age) hoặc tên (name) từ nhỏ đến lớn.

Code ví dụ C++ 

#include <bits/stdc++.h>

using namespace std;

// Định nghĩa struct Person có thuộc tính name và age
struct Person {
    string name;
    int age;
};

// Hàm so sánh tùy chỉnh để sắp xếp theo tuổi
bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age; // Sắp xếp tăng dần theo tuổi
}
// Hàm so sánh tùy chỉnh để sắp xếp theo tên
bool compareByName(const Person& a, const Person& b) {
    return a.name < b.name; // Sắp xếp tăng dần theo tên
}
// Hàm so sánh tùy chỉnh để sắp xếp theo tên
bool compareByNameByAge(const Person& a, const Person& b) {
	if (a.name < b.name) return true;
	if (a.name > b.name) return false;
    return a.age < b.age; 
}
int main() {
    // Khởi tạo vector people với các đối tượng Person
    vector<Person> people = {
        {"Alice", 30},
        {"Alice", 25},
        {"Bob", 25},
        {"Charlie", 35},
        {"David", 20}
    };

    // Sắp xếp mảng sử dụng hàm so sánh tùy chỉnh compareByAge
    sort(people.begin(), people.end(), compareByAge);

    // Kết quả: David: 20 Alice: 25 Bob: 25 Alice: 30 Charlie: 35
    for (const auto& person : people) {
        cout << person.name << ": " << person.age << " ";
    }
    cout<<"\n";
    // Sắp xếp mảng sử dụng hàm so sánh tùy chỉnh compareByName
    sort(people.begin(), people.end(), compareByName);

    // Kết quả: Alice: 25 Alice: 30 Bob: 25 Charlie: 35 David: 20 
    for (const auto& person : people) {
        cout << person.name << ": " << person.age << " ";
    }
    cout<<"\n";
    // Sắp xếp mảng sử dụng hàm so sánh tùy chỉnh compareByNameByAge
    sort(people.begin(), people.end(), compareByNameByAge);

    // Kết quả: Alice: 25 Alice: 30 Bob: 25 Charlie: 35 David: 20
    for (const auto& person : people) {
        cout << person.name << ": " << person.age << " ";
    }
    cout<<"\n";
    return 0;
}

4. Cách tự viết hàm so sánh trong Python

Trong Python, bạn có thể tự viết hàm so sánh để sắp xếp các đối tượng của một lớp hoặc một cấu trúc dữ liệu như danh sách. Có nhiều cách để thực hiện việc này, bao gồm việc sử dụng các hàm và phương thức có sẵn trong thư viện tiêu chuẩn của Python.

Cách 1: Sử dụng key trong hàm sorted() và sort()

Hàm sorted() và phương thức sort() của danh sách (list) trong Python đều chấp nhận tham số key, cho phép bạn truyền vào một hàm để lấy giá trị sắp xếp.

Ví dụ với danh sách các từ điển
Giả sử bạn có một danh sách các từ điển và bạn muốn sắp xếp theo giá trị của một khóa cụ thể

Code ví dụ Python 

# Danh sách các từ điển
people = [
    {"name": "Alice", "age": 30},
    {"name": "Alice", "age": 25},
    {"name": "Bob", "age": 25},
    {"name": "Charlie", "age": 35},
    {"name": "David", "age": 20}
]

# Sắp xếp theo tuổi (age)
sorted_people = sorted(people, key=lambda x: x['age'])

# Kết quả: {'name': 'David', 'age': 20} {'name': 'Alice', 'age': 25} {'name': 'Bob', 'age': 25} {'name': 'Alice', 'age': 30} {'name': 'Charlie', 'age': 35}  
for person in sorted_people:
    print(person, end=" ")
print()

# Sắp xếp theo tên (name)
sorted_people = sorted(people, key=lambda x: x['name'])

# Kết quả: {'name': 'Alice', 'age': 30} {'name': 'Alice', 'age': 25} {'name': 'Bob', 'age': 25} {'name': 'Charlie', 'age': 35} {'name': 'David', 'age': 20} 
for person in sorted_people:
    print(person, end=" ")

Cách 2: Sử dụng hàm so sánh tùy chỉnh với cmp_to_key

Trong một số trường hợp phức tạp hơn, bạn có thể cần sử dụng hàm so sánh tùy chỉnh. Python cung cấp hàm cmp_to_key trong module functools để chuyển đổi hàm so sánh thành hàm key.

Ví dụ với lớp tự định nghĩa
Giả sử bạn có một lớp Person và bạn muốn sắp xếp các đối tượng của lớp này theo nhiều tiêu chí:

Code ví dụ Python 

from functools import cmp_to_key

# Định nghĩa lớp Person
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __repr__(self):
        return f"{self.name}: {self.age}"

# Hàm so sánh theo Age
def compareByAge(person1, person2):
    if person1.age < person2.age:
        return -1
    elif person1.age > person2.age:
        return 1
    else:
        return 0
# Hàm so sánh theo Name
def compareByName(person1, person2):
    if person1.name < person2.name:
        return -1
    elif person1.name > person2.name:
        return 1
    else:
        return 0    
# Hàm so sánh theo Age, rồi sau đó so sánh theo Name
def compareByAgeByName(person1, person2):
    if person1.age < person2.age:
        return -1
    elif person1.age > person2.age:
        return 1
    else:
        if person1.name < person2.name:
            return -1
        elif person1.name > person2.name:
            return 1
        else:
            return 0    
# Danh sách các đối tượng Person
people = [
    Person("Alice", 30),
    Person("Alice", 25),
    Person("Bob", 25),
    Person("Charlie", 35),
    Person("David", 20)
]

# Sắp xếp sử dụng hàm so sánh compareByAge
sorted_people = sorted(people, key=cmp_to_key(compareByAge))

# Kết quả: David: 20 Alice: 25 Bob: 25 Alice: 30 Charlie: 35 
for person in sorted_people:
    print(person, end = " ")
print()

# Sắp xếp sử dụng hàm so sánh compareByName
sorted_people = sorted(people, key=cmp_to_key(compareByName))

# Kết quả: Alice: 30 Alice: 25 Bob: 25 Charlie: 35 David: 20 
for person in sorted_people:
    print(person, end = " ")
print()

# Sắp xếp sử dụng hàm so sánh compareByAgeByName
sorted_people = sorted(people, key=cmp_to_key(compareByAgeByName))

# Kết quả: David: 20 Alice: 25 Bob: 25 Alice: 30 Charlie: 35 
for person in sorted_people:
    print(person, end = " ")

Cách 3: Sử dụng phương thức đặc biệt __lt__

Bạn có thể định nghĩa phương thức đặc biệt __lt__ (less than) trong lớp của mình để cho phép sắp xếp các đối tượng một cách tự nhiên.

Code ví dụ Python 

# Định nghĩa lớp Person với phương thức __lt__
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __repr__(self):
        return f"{self.name}: {self.age}"

    # Định nghĩa phương thức __lt__ để sắp xếp theo tuổi
    def __lt__(self, other):
        return self.age < other.age

# Danh sách các đối tượng Person
people = [
    Person("Alice", 30),
    Person("Bob", 25),
    Person("Charlie", 35),
    Person("David", 20)
]

# Sắp xếp danh sách trực tiếp
people.sort()

# In kết quả đã sắp xếp
for person in people:
    print(person)

5. Bài tập áp dụng

PHÂN SỐ (CPBFRAC)
Đây là một bài tập luyện tập trong sách Competitive Programming Basic 2024 của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn
Đề bài
Xét tập \(F(N)\) tất cả các số hữu tỉ trong đoạn \([0,1]\) với mẫu số không quá \(N\).
Ví dụ, tập \(F(5)= {\frac{0}{1},\frac{1}{5},\frac{1}{4} ,\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{1}{1} }\)
Yêu cầu: Sắp xếp các phân số trong tập \(F(N)\) theo thứ tự tăng dần, đưa ra phân số thứ \(K\).
INPUT

Một dòng duy nhất chứa hai số \(N\) và \(K\) \( 1 \< N \le 1000 \).

OUTPUT
Ghi ra phân số thứ \(K\) tìm được theo định dạng trong ví dụ. Dữ liệu đảm bảo tồn tại phân số thứ \(K\).

INPUT

5 3

OUTPUT

1/4

Phân tích bài toán

Ở bài này, ta cần tạo ra các phân số tối giản từ các cặp số từ \(1\) đến \(N\), nhưng nếu lưu các phân số dưới dạng số thực thì ta sẽ gặp vấn đề là dễ bị sai số. Vậy ý tưởng là ta sẽ sử dụng một kiểu dữ liệu có thể lưu được hai giá trị: tử số, mẫu số có thể sử dụng pair trong C++ hoặc tự định nghĩa.
Khi đó ta sẽ tự định nghĩa một hàm so sánh hai phần tử theo dạng phân số, sử dụng phép so sánh phân số trong toán học thông qua quy đồng mẫu: so sánh a.tử số*b.mẫu số và a.mẫu số * b.tử số
Sau khi đã sắp xếp được các phân số, tiến hành loại bỏ những phân số trùng lặp và tìm ra kết quả.

Code mẫu C++

#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>>a;
vector<pair<int, int>>b;

//Sử dụng pair để lưu tử số và mẫu số
//So sánh phân số theo cách quy đồng mẫu
bool cmp (pair<int,int> a, pair<int,int> b) {
    return a.first * b.second < a.second * b.first;
}
int main () {
    int n, k, x, y;
    cin >> n >> k;
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            x = i / __gcd (i, j);
            y = j / __gcd (i, j);
            a.push_back (make_pair (x, y));
        }   
    }
    a.push_back (make_pair (1, 1));
    sort (a.begin (), a.end (), cmp);
    b.push_back (make_pair (0, 1));
    for (int i = 1; i < a.size (); i++) {
        if (a[i].first != a[i - 1].first ||  a[i].second != a[i - 1].second) {
            b.push_back (make_pair (a[i].first, a[i].second));
        }
    }
    cout << b[k - 1].first << "/" << b[k - 1].second;
}

Code mẫu Python

from math import gcd
from functools import cmp_to_key

# So sánh phân số theo cách quy đồng mẫu
def cmp(a, b):
    return a[0] * b[1] - a[1] * b[0]

def main():
    n,k = [int(x) for x in input().split()]

    a = []
    b = []

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            x = i // gcd(i, j)
            y = j // gcd(i, j)
            a.append((x, y))

    a.append((1, 1))
    a.sort(key=cmp_to_key(cmp))

    b.append((0, 1))
    for i in range(1, len(a)):
        if a[i][0] != a[i - 1][0] or a[i][1] != a[i - 1][1]:
            b.append((a[i][0], a[i][1]))

    print(f"{b[k - 1][0]}/{b[k - 1][1]}")

if __name__ == "__main__":
    main()

6. Kết luận

Cả C++ và Python đều cung cấp các công cụ mạnh mẽ và linh hoạt để tự viết hàm so sánh và sắp xếp các đối tượng. C++ phù hợp với các tình huống yêu cầu hiệu suất cao và kiểm soát chặt chẽ, trong khi Python mang lại sự đơn giản và dễ sử dụng, giúp tăng năng suất lập trình. Việc hiểu và áp dụng các kỹ thuật này trong từng ngôn ngữ sẽ giúp bạn xử lý hiệu quả các bài toán sắp xếp phức tạp trong lập trình.

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *