Sắp xếp

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về một trong những thuật toán cơ bản và phổ biến nhất trong lập trình: sắp xếp. Hãy cùng xem các thuật toán sắp xếp có gì thú vị nhé!

---

Nội dung

Để có thể tiếp thu bài học này một cách tốt nhất, các bạn nên có những kiến thức cơ bản về:

• Biến, kiểu dữ liệu, toán tử trong C++
• Câu điều kiện, vòng lặp, hàm trong C++
• Mảng trong C++
• Các kiến thức cần thiết để theo dõi khóa học   
• Đệ quy và quay lui

Trong bài học ngày hôm nay, chúng ta sẽ cùng nhau tìm hiểu về:

• Tổng quan về sắp xếp
• Một số thuật toán sắp xếp thông dụng
• Sử dụng sort trong C++

---

Tổng quan về sắp xếp

Giới thiệu

Sắp xếp là một khái niệm hiện diện xung quanh trong cuộc sống của chúng ta. Ứng dụng của nó có ở khắp mọi nơi như sắp xếp tên trong lớp học theo bảng chữ cái, sắp xếp điểm thi, …

Thuật toán sắp xếp có thể đứng độc lập hoặc dùng kết hợp với các thuật toán khác để giải quyết các bài toán như tìm kiếm nhị phân, tìm đường đi ngắn nhất, …

Hiện nay, đa phần các ngôn ngữ lập trình đều hỗ trợ sẵn hàm sắp xếp, vậy thì học về chúng có ích lợi gì không? Câu trả lời là có. Học về sắp xếp không phải chỉ là học về cách code mà còn là học về các ý tưởng được đưa ra cho cách sắp xếp đó – một thứ sẽ hữu ích cho quá trình học về sau.

---

Các vấn đề với sắp xếp

Hãy thử tưởng tượng bạn cần sắp xếp điểm thi của một trường học. Bạn sẽ làm gì? Có khá nhiều hướng đi mà các bạn có thể chọn:

• Tìm kiếm trong cả danh sách rồi lần lượt lấy ra điểm thấp nhất
• Sắp xếp các điểm trong nhóm 1 điểm, 2 điểm, … rồi gộp lại
• …

Đối với mỗi cách làm sẽ có thời gian thực hiện khác nhau. Các thuật toán sắp xếp cũng sẽ như vậy. Tuỳ từng thuật toán sẽ có điểm tối ưu và chưa tối ưu.

Một số vấn đề với các thuật toán sắp xếp mà ta cần quan tâm:

• Thời gian: Đối với dữ liệu lớn, các thuật toán không tốt sẽ chạy rất chậm
• Bộ nhớ: Một số thuật toán sẽ đòi hỏi việc gọi đệ quy gây ra việc tốn bộ nhớ hơn các thuật toán khác. Nếu bộ nhớ bị giới hạn quá chặt sẽ không thể thực hiện được

---

Một số thuật toán sắp xếp thông dụng

Trên thực tế, có rất nhiều các thuật toán sắp xếp. Tuy nhiên, trong bài học này, mình sẽ chỉ giới thiệu cho các bạn các thuật toán được sử dụng phổ biến hơn cả. Các bạn có thể tự tìm hiểu thêm về các thuật toán sắp xếp khác để mở rộng kiến thức.

Các thuật toán mình sắp giới thiệu dưới đây sẽ đều phục vụ việc sắp xếp tăng dần một dãy số nguyên. Từ ý tưởng và code của mình, các bạn có thể tuỳ chỉnh để phù hợp với mục đích của bản thân.

---

Sắp xếp nổi bọt (Bubble Sort)

Ý tưởng

Xét lần lượt các cặp 2 phần tử liên tiếp. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước, ta đổi chỗ 2 phần tử. Nói cách khác, phần tử nhỏ nhất sẽ “nổi” lên trên.

Ta lặp lại hành động trên cho đến khi không còn 2 phần tử nào thỏa mãn. Do một phần tử không thể bị đổi chỗ quá n – 1 lần nên số lần lặp không quá n – 1 lần.

---

Code

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, a[MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < n - 1 ; ++j)
    if(a[j] > a[j + 1]) swap(a[j], a[j + 1]);
    
    for(int i = 0 ; i < n ; ++i) cout << a[i] << " ";

    return 0;
}

Ưu điểm:

• Đơn giản, dễ nhớ
• Không phát sinh bộ nhớ tạm

Nhược điểm:

Độ phức tạp là O(n²), sẽ rất chậm nếu dữ liệu lớn.

---

Sắp xếp chèn (Insertion Sort)

Ý tưởng

Ý tưởng chính của thuật toán là ta sẽ sắp xếp lần lượt từng đoạn gồm 1 phần tử đầu tiên, 2 phần tử đầu tiên, …

Giả sử ta đã sắp xếp xong i phần tử của mảng. Để sắp xếp i + 1 phần tử đầu tiên, ta tìm vị trí phù hợp của phần tử thứ i + 1 và "chèn" nó vào đó.

---

Code

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, a[MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];

    for(int i = 0 ; i < n ; ++i){
        // Tìm vị trí của i
        int j = i;
        while(j > 0 && a[i] < a[j - 1]) j--;
        // Chèn a[i] vào vị trí đúng
        // Cơ chế chèn giống như cách làm đã nêu ở bài Linked List
        int temp = a[i];
        for(int k = i ; k > j ; --k) a[k] = a[k - 1];
        a[j] = temp;
    }

    for(int i = 0 ; i < n ; ++i) cout << a[i] << " ";

    return 0;
}

Ưu điểm

Nếu dữ liệu đầu vào được sắp xếp gần đúng thì thuật toán chạy sẽ rất nhanh.

Nhược điểm

Độ phức tạp là O(n²), sẽ rất chậm với dữ liệu lớn.

---

Sắp xếp nhanh (Quick Sort)

Ý tưởng

• Chia dãy làm hai đoạn “lớn” và “nhỏ”
  • Chọn 1 phần tử trung gian
  • Các phần tử nhỏ hơn phần tử trung gian chia vào đoạn “nhỏ”, các phần tử lớn hơn phần tử trung gian chia vào đoạn “lớn”
• Gọi đệ quy sắp xếp hai phần

---

Code

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int n, a[MaxN];

void quickSort(int a[], int left, int right){
    int i = left, j = right;
    int tg = a[(left + right) / 2];
    // Phân chia dãy 
    while(i <= j){
        while(a[i] < tg) i++;
        while(a[j] > tg) j--;
        if(i <= j){
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    // Gọi đệ quy sắp xếp hai đoạn nửa
    if(left < j) quickSort(a, left, j);
    if(i < right) quickSort(a, i, right);
}

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 0 ; i < n ; ++i) cin >> a[i];
    quickSort(a, 0, n - 1);
    for(int i = 0 ; i < n ; ++i) cout << a[i] << " ";

    return 0;
}

Ưu điểm

Chạy nhanh trong đa phần các trường hợp.

Nhược điểm

Nếu cách chia 2 phần không tốt có thể dẫn đến độ phức tạp trong trường hợp xấu nhất là O(n²). Nếu chọn phần tử trung gian ngẫu nhiên thì độ phức tạp trung bình sẽ giảm xuống O(n × logn) dù trường hợp xấu nhất vẫn là O(n²).

---

Sử dụng sort trong C++

Bản chất của hàm sort được sử dụng trong C++ là Intro Sort, một sự kết hợp giữa Quick Sort và Insertion Sort. Việc này giúp hàm sort trong C++ tận dụng được ưu điểm của cả 2 cách này.

---

Khai báo sort

Thông thường để thêm sort vào chương trình, chúng ta sẽ thêm thư viện như sau:

#include<algorithm>

Tuy nhiên, ở trong suốt khóa học này mình sẽ sử dụng header sau:

#include<bits/stdc++.h>

Header này sẽ giúp chúng ta thêm tất cả các thư viện về thuật toán mà chúng ta sẽ sử dụng trong khóa học này.

---

Sử dụng sort

Hàm sort trong C++ sẽ được dùng như sau

sort({first}, {last}, [comp]);

Trong đó:

• first, last lần lượt là 2 con trỏ trỏ đến vị trí xuất phát và kết thúc của dãy cần sắp xếp. Khoảng được sắp xếp là [first, last), tức là tất cả các phần tử giữa first và last và thêm phần tử được trỏ bởi first nhưng không có phần tử trỏ bởi last.
• comp là một hàm có thể có hoặc không, nhận vào hai phần tử trong đoạn cần sắp xếp và trả về giá trị bool. Nếu không có hàm comp, hàm sort sẽ tự động sắp xếp theo định nghĩa của toán tử < của kiểu dữ liệu đó. Nếu có hàm comp, hàm sort sẽ sắp xếp để đảm bảo khi ta có 2 giá trị i và j (i đứng trước j sau khi sắp xếp xong) thì comp(i, j) trả về true.

---

Demo

Để các bạn có thể hiểu hơn về cách hàm sort hoạt động, mình sẽ có một số demo sau:

Hàm sort dùng với các kiểu dữ liệu của C++

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

int main(){
    int a[] = {4, 6, 5, 3, 8, 1};
    sort(a, a + 6);
    for(int i = 0 ; i < 6 ; ++i) cout << a[i] << " ";
    // Kết quả in ra: 1 3 4 5 6 8

    return 0;
}

Hàm sort có sử dụng comp

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

// Điều kiện giảm dần
bool comp(int &i, int &j){
    return i > j;
}

int main(){
    int a[] = {4, 6, 5, 3, 8, 1};
    sort(a, a + 6, comp);
    for(int i = 0 ; i < 6 ; ++i) cout << a[i] << " ";
    // Kết quả in ra: 8 6 5 4 3 1 

    return 0;
}

Hàm sort với kiểu dữ liệu tự định nghĩa

Các bạn sẽ cần định nghĩa toán tử < trong struct hoặc class đó.

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

// Struct thể hiện cho phân số
struct Fraction{
    int x, y;
    // x là tử số, y là mẫu số
    Fraction(int _x, int _y){
        x = _x;
        y = _y;
    }

    // Định nghĩa toán tử <
    // Nếu hàm trả về true nghĩa là fraction đang xét nhỏ hơn fraction op
    bool operator < (const Fraction &op) const {
        return x * op.y < y * op.x;
    }
};

int main(){
    Fraction a[] = {Fraction(1, 2), Fraction(2, 3), Fraction(5, 2)};
    sort(a, a + 3);
    for(int i = 0 ; i < 3 ; ++i) cout << a[i].x << " " << a[i].y << endl;
    // Kết quả in ra: 
    // 1 2
    // 2 3
    // 5 2

    return 0;
}

Hoặc các bạn có thể viết hàm comp để so sánh như sau:

#include<bits/stdc++.h>
using namespace std;

const int MaxN = 1 + 1e5;

// Struct thể hiện cho phân số
struct Fraction{
    int x, y;
    // x là tử số, y là mẫu số
    Fraction(int _x, int _y){
        x = _x;
        y = _y;
    }
};

bool comp(Fraction &fi, Fraction &se){
    return fi.x * se.y < se.x * fi.y;
}

int main(){
    Fraction a[] = {Fraction(1, 2), Fraction(2, 3), Fraction(5, 2)};
    sort(a, a + 3, comp);
    for(int i = 0 ; i < 3 ; ++i) cout << a[i].x << " " << a[i].y << endl;
    // Kết quả in ra: 
    // 1 2
    // 2 3
    // 5 2

    return 0;
}

Dù cả hai cách đều đúng nhưng mình khuyến khích các bạn dùng cách viết lại toán tử < hơn vì nó sẽ làm code tường minh và dễ đọc hơn rất nhiều.

---

Độ phức tạp thời gian

Với hàm sort trong C++ thì độ phức tạp thời gian trung bình sẽ là O(n × logn).

---

Kết luận

Qua bài này chúng ta đã nắm được về Sắp xếp

Bài sau chúng ta sẽ bắt đầu tìm hiểu về Tìm kiếm nhị phân

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.