Sắp xếp là việc sắp đặt các phần tử trong một cấu trúc theo thứ tự tăng dần hoặc giảm dần. Việc sắp xếp giúp chúng ta dễ dàng thao tác trên cấu trúc như tìm kiếm, trích xuất, duyệt cấu trúc... Trong bài viết này, chúng ta sẽ tìm hiểu về các thuật toán sắp xếp trong Java mà chúng ta chưa được giới thiệu trước đây, đó là "Quick Sort Algorithm" và "Heap Sort Algorithm".
Quick Sort Algorithm
Quick Sort, còn được gọi là sắp xếp nhanh, là một thuật toán sắp xếp tại chỗ phát triển bởi C.A.R. Hoare. Quick Sort là một thuật toán sắp xếp hiệu quả và thường thực hiện nhanh hơn so với Merge Sort hay Heap Sort.
Thuật toán Quick Sort áp dụng phương pháp chia để trị. Ban đầu, thuật toán chia mảng thành hai phần bằng cách so sánh từng phần tử với một phần tử được gọi là phần tử chốt. Một mảng bao gồm các phần tử nhỏ hơn hoặc bằng phần tử chốt và một mảng gồm các phần tử lớn hơn phần tử chốt. Quá trình chia mảng này được tiếp tục cho đến khi độ dài của các mảng con đạt đến 1. Từ đó, chúng ta có thể tiếp tục áp dụng đệ quy để sắp xếp các mảng con và kết hợp chúng để tạo ra một mảng đã sắp xếp hoàn chỉnh.
Độ phức tạp của Quick Sort trong trường hợp trung bình là Θ(n log(n)), và trong trường hợp xấu nhất là Θ(n^2).
Hình ảnh minh họa cho thuật toán sắp xếp trong Java
Cần lưu ý rằng quá trình chọn phần tử chốt và phân vùng có thể thực hiện theo nhiều cách khác nhau và sẽ ảnh hưởng đến hiệu suất của thuật toán.
Triển khai thuật toán Quick Sort
Heap Sort Algorithm
Thuật toán Heap Sort được đề xuất vào năm 1964 bởi J.W.J. Williams, và sau đó, R.W. Floyd đã đưa ra phiên bản cải tiến của thuật toán này, giúp nó trở thành thuật toán in-place với thời gian thực thi nhanh và độ phức tạp trong trường hợp xấu nhất là O(n log n).
Heap Sort còn được gọi là giải thuật vun đống (heapify), nó có thể được coi là phiên bản cải tiến của Selection Sort khi chia mảng thành hai phần: một phần đã được sắp xếp và một phần chưa được sắp xếp. Trong mảng chưa được sắp xếp, các phần tử lớn nhất sẽ được tách ra và đưa vào mảng đã sắp xếp. Điều cải tiến ở Heap Sort so với Selection Sort là sử dụng cấu trúc dữ liệu heap để tìm phần tử lớn nhất thay vì tìm kiếm tuyến tính.
Heap Sort là thuật toán in-place, nghĩa là không cần sử dụng cấu trúc dữ liệu phụ trợ. Tuy nhiên, thuật toán này không đảm bảo tính ổn định (stability).
Thuật toán Heap Sort được chia thành hai giai đoạn:
Giai đoạn 1: Sắp xếp mảng input thành một heap (cấu trúc cây nhị phân) - có thể là Min-heap (nút gốc có giá trị nhỏ nhất) hoặc Max-heap (nút gốc có giá trị lớn nhất).
Giai đoạn 2: Thực hiện các bước lặp để sắp xếp mảng dữ liệu.
Hình ảnh minh họa cho thuật toán Heap Sort
Triển khai thuật toán Heap Sort
Mặc dù tốc độ chạy của Heap Sort chậm hơn một chút so với Quick Sort, nhưng Heap Sort đảm bảo tính ổn định và độ phức tạp của nó là O(n log n) trong trường hợp xấu nhất. Thuật toán này cũng không cần sử dụng thêm cấu trúc dữ liệu phụ trợ, do đó tốc độ của nó nhanh và thường được sử dụng rộng rãi.
Tác giả: Vũ Hoàng Tuấn
Xem thêm các bài chia sẻ và hướng dẫn lập trình khác tại đây
