Thuật toán sắp xếp trong C++

Bài toán sắp xếp

Thuật toán sắp xếp là lời giải của bài toán sắp xếp, nhưng trước tiên hãy tìm hiểu xem bài toán sắp xếp là gì.

Bạn đang xem: Thuật toán sắp xếp trong C++

Bài toán sắp xếp là việc sắp xếp lại các phần tử trong danh sách theo thứ tự tăng hoặc giảm dần theo một tiêu chí nào đó của phần tử.

Ví dụ, bạn có thể sắp xếp danh sách lớp học theo điểm trung bình từ cao đến thấp, sắp xếp các quyển sách theo kích cỡ từ nhỏ đến lớn, hoặc sắp xếp các tờ tiền theo mệnh giá từ thấp đến cao.

Mục đích của việc sắp xếp là giúp ta có cái nhìn tổng quan hơn về dữ liệu mà ta có, dễ dàng tìm kiếm những phần tử đứng đầu với một tiêu chí nào đó. Ngoài ra, sắp xếp còn làm cơ sở cho các giải thuật nâng cao có hiệu suất cao hơn.

Ví dụ, khi thực hiện tìm kiếm, thuật toán tìm kiếm nhị phân yêu cầu dãy đã được sắp xếp. Do đó, bạn có thể thực hiện sắp xếp trước, sau đó áp dụng thuật toán tìm kiếm nhị phân.

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

Sắp xếp nổi bọt là thuật toán sắp xếp đầu tiên mà mình giới thiệu. Đây là thuật toán đơn giản nhất, ý tưởng của nó như sau:

1. Duyệt qua danh sách, làm cho các phần tử lớn nhất hoặc nhỏ nhất dịch chuyển về phía cuối danh sách.
2. Tiếp tục làm phần tử lớn nhất hoặc nhỏ nhất kế đó dịch chuyển về cuối danh sách, và tiếp tục như vậy cho đến hết danh sách.

Cụ thể các bước thực hiện của giải thuật này như sau:

Gán i = 0
Gán j = 0
Nếu A[j] > A[j + 1] thì đổi chỗ A[j] và A[j + 1]
Nếu j < n - i - 1:
  - Đúng thì j = j + 1 và quay lại bước 3
  - Sai thì sang bước 5
Nếu i < n - 1:
  - Đúng thì i = i + 1 và quay lại bước 2
  - Sai thì dừng lại

Xem thêm : Sơ Đồ Đấu Nối Mạch Điện Khởi Động Sao Tam Giác Chuẩn

Sắp xếp nổi bọt là một thuật toán sắp xếp ổn định. Về độ phức tạp, do dùng hai vòng lặp lồng vào nhau nên độ phức tạp thời gian trung bình của thuật toán này là O(n^2).

Sắp xếp chọn (Selection Sort)

Sắp xếp chọn là thuật toán thứ hai mình giới thiệu. Ý tưởng của thuật toán này như sau: duyệt từ đầu đến phần tử kề cuối danh sách, tìm phần tử nhỏ nhất từ vị trí kế phần tử đang duyệt đến cuối danh sách, sau đó đổi vị trí của phần tử nhỏ nhất đó với phần tử đang duyệt. Tiếp tục như vậy cho đến khi duyệt hết danh sách.

Cụ thể các bước thực hiện của thuật toán như sau:

Gán i = 0
Gán j = i + 1 và min = A[i]
Nếu j < n:
  - Nếu A[j] < A[min] thì min = j
  - j = j + 1
  - Quay lại bước 3
Đổi chỗ A[min] và A[i]
Nếu i < n - 1:
  - Đúng thì i = i + 1 và quay lại bước 2
  - Sai thì dừng lại

Thuật toán sắp xếp chọn cũng có độ phức tạp thời gian trung bình là O(n^2). Thuật toán sắp xếp chọn mình cài đặt là thuật toán sắp xếp không ổn định, nhưng nó cũng có phiên bản khác cải tiến là thuật toán sắp xếp chọn ổn định.

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

Sắp xếp chèn là thuật toán tiếp theo mình giới thiệu. Ý tưởng của thuật toán này như sau: ta có một mảng ban đầu gồm phần tử A[0] và xem như mảng này đã được sắp xếp. Duyệt từ phần tử 1 đến n – 1, tìm cách chèn những phần tử đó vào vị trí thích hợp trong mảng ban đầu đã được sắp xếp.

Các bước thực hiện của thuật toán như sau:

Gán i = 1
Gán x = A[i] và pos = i - 1
Nếu pos >= 0 và A[pos] > x:
  - A[pos + 1] = A[pos]
  - pos = pos - 1
  - Quay lại bước 3
A[pos + 1] = x
Nếu i < n:
  - Đúng thì i = i + 1 và quay lại bước 2
  - Sai thì dừng lại

Thuật toán sắp xếp chèn cũng có độ phức tạp thời gian trung bình là O(n^2) do có hai vòng lặp lồng vào nhau.

Sắp xếp trộn (Merge Sort)

Sắp xếp trộn (merge sort) là một thuật toán dựa trên kỹ thuật chia để trị. Ý tưởng của thuật toán này như sau: chia đôi mảng thành hai mảng con, sắp xếp hai mảng con đó và trộn lại theo đúng thứ tự, sau đó tiếp tục áp dụng cách sắp xếp này cho hai mảng con.

Xem thêm : Rơ le trung gian: Định nghĩa, chức năng và cách đấu

Độ phức tạp thời gian trung bình của thuật toán Merge Sort là O(nlog(n)), và sắp xếp trộn là thuật toán sắp xếp ổn định.

Sắp xếp nhanh (Quick Sort)

Sắp xếp nhanh (quick sort) hay sắp xếp phân đoạn là là thuật toán sắp xếp dựa trên kỹ thuật chia để trị. Ý tưởng của thuật toán này là chọn một điểm làm chốt (gọi là pivot), sắp xếp các phần tử bên trái chốt nhỏ hơn chốt và các phần tử bên phải lớn hơn chốt, sau đó áp dụng cách sắp xếp này cho hai dãy con bên trái và bên phải đến khi chỉ còn một phần tử trong dãy.

Thuật toán sắp xếp nhanh không phải là thuật toán sắp xếp ổn định. Độ phức tạp thời gian trung bình của thuật toán này là O(nlog(n)).

Một số thuật toán sắp xếp khác

Ngoài các thuật toán trên, bạn còn có thể tìm hiểu thêm một số thuật toán sắp xếp khác như:

• Binary Insersion Sort – Chèn nhị phân
• Interchange Sort – Đổi chỗ trực tiếp
• Shaker Sort
• Shell Sort
• Heap Sort – Sắp xếp vun đống
• Counting Sort – Sắp xếp đếm
• Radix Sort – Sắp xếp cơ số

Các thuật toán trên có thể tìm hiểu thêm tại trang GeeksforGeeks.

Lời kết

Qua bài viết này, mình đã giới thiệu đến các bạn các thuật toán sắp xếp phổ biến nhất. Nếu bạn có thắc mắc hoặc ý kiến gì, đừng ngại để lại bình luận bên dưới. Hãy chia sẻ bài viết này cho bạn bè của bạn và cảm ơn bạn đã theo dõi bài viết!

Bài viết gốc được đăng tải tại khiemle.dev

Nguồn: https://cite.edu.vn
Danh mục: Học tập