Quicksort là một thuật toán sắp xếp hiệu quả, được phát triển bởi nhà khoa học máy tính người Anh Tony Hoare vào năm 1959 và xuất bản năm 1961. Đây là một thuật toán dựa trên so sánh, có nghĩa là nó đo lường sự khác biệt giữa các phần tử cần được sắp xếp. Nó hoạt động bằng cách sử dụng phương pháp phân chia và chinh phục, chia các phần tử thành hai nhóm con, sau đó được sắp xếp đệ quy.
Quicksort sử dụng sự kết hợp giữa sắp xếp lựa chọn và phân vùng để sắp xếp một mảng. Trong sắp xếp lựa chọn, thuật toán tìm kiếm phần tử nhỏ nhất trong mảng và hoán đổi nó với phần tử đầu tiên trong mảng. Việc hoán đổi này đảm bảo rằng phần tử nhỏ nhất luôn ở đầu mảng. Sau đó, giai đoạn phân vùng sẽ di chuyển giá trị của phần tử hiện tại đến một vị trí giữa các phần tử có giá trị nhỏ hơn và lớn hơn nó. Điều này được thực hiện bằng cách trước tiên chọn một phần tử của mảng, được gọi là “trục”. Tất cả các phần tử nhỏ hơn trục được đặt trước trục và tất cả các phần tử lớn hơn trục được đặt sau trục. Quá trình này được lặp lại với hai nhóm con mới được tạo cho đến khi mảng được sắp xếp.
Độ phức tạp về thời gian của sắp xếp nhanh phụ thuộc vào trục được chọn, nhưng trong hầu hết các trường hợp, độ phức tạp về thời gian của sắp xếp nhanh là O(n log n). Điều này làm cho quicksort trở thành một thuật toán sắp xếp được ưa thích vì tốc độ tương đối nhanh của nó. Nó cũng được ưa thích vì yêu cầu bộ nhớ thấp.
Quicksort được sử dụng rộng rãi trong nhiều lĩnh vực khoa học máy tính, chẳng hạn như hệ điều hành, cơ sở dữ liệu và đồ họa. Nó cũng thường được sử dụng như một phần của thư viện chuẩn trong nhiều ngôn ngữ lập trình như C, Java và Python.
