Sorting Algorithms

Sorting (sắp xếp) là việc sắp xếp dữ liệu theo thứ tự tăng dần hoặc giảm dần.

Có rất nhiều thứ trong cuộc sống hàng ngày của chúng ta mà cần phải tìm kiếm như một bản ghi cụ thể trong một cơ sở dữ liệu, một số điện thoại cụ thể trong danh bạ, một trang cụ thể trong một cuốn sách, v.v…Tất cả các công việc tìm kiếm này sẽ trở lên vô vàn khó khăn nếu như dữ liệu không được sắp xếp theo một trình tự.

Nhưng rất may mắn, khái niệm sorting tồn tại giúp chúng ta dễ dàng sắp xếp dữ liệu theo thứ tự, do đó giúp công việc tìm kiếm trở lên dễ dàng hơn.

Sorting (sắp xếp) dữ liệu theo một trình tự giúp searching (tìm kiếm) dễ dàng hơn.

Có nhiều giải thuật sắp xếp khác nhau. Chúng ta có 2 tiêu chí chính để đánh giá giải thuật nào tốt hơn giải thuật kia là:

  • Thời gian thực hiện sắp xếp một lượng dữ liệu nhất định (Time Complexity)
  • Không gian bộ nhớ cần thiết để thực thi việc sắp xếp (Space Complexity)

1. Danh sách các đề mục

Dưới đây là danh sách các thuật toán sắp xếp phổ biến nhất. 3 thuật toán đầu tiên có độ phức tạp tính toán là O(n2):

Sau đó ta sẽ cùng tìm hiểu các thuật toán sắp xếp hiệu quả hơn, có độ phức tạp tính toán là O(n log n):