Sắp xếp là sắp đặt các phần tử của một cấu trúc theo thứ tự tăng hoặc giảm. Với một cấu trúc được sắp xếp chúng ta sẽ thuận lợi khi thực hiện các tác vụ trên cấu trúc như tìm kiếm, trích lọc, duyệt cấu trúc..
Trong bài viết, mình sẽ giới thiệu về những thuật toán sắp xếp trong Java mà chúng ta chưa được giới thiệu trong khuôn khổ chương trình học “Quick Sort Algorithm & Heap Sort Algorithm”.
Nội dung
Quick Sort Algorithm
Sắp xếp nhanh (Quicksort), còn được gọi là sắp xếp kiểu phân chia (part sort) là một thuật toán sắp xếp phát triển bởi C.A.R. Hoarec sắp thành hai danh sách con. QuickSort là một thuật toán sắp xếp tại chỗ hiệu quả, và thường thực hiện nhanh hơn so với Merge Sort hay HeapSort.
Quick Sort là thuật toán theo hướng chia để trị, và giống như các thuật toán chia để trị. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng phần tử của mảng 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 phân chia này diễn ra cho đến khi độ dài của các mảng con đều bằng 1. Với phương pháp đệ quy ta có thể sắp xếp nhanh các mảng con sau khi kết thúc chương trình ta được một mảng đã sắp xếp hoàn chỉnh.
Độ phức tạp của sắp xếp nhanh trong trường hợp trung bình là Θ (n log (n)) và trong trường hợp xấu nhất là Θ (n2)
Nên lưu ý rằng các bước lựa chọn và phân vùng trục có thể được thực hiện nhiều các khác nhau và việc lựa chọn này cũng sẽ ảnh hưởng cụ thể đến hiệu suất của thuật toán
Triển khai thuật toán QuickSort
Heap Sort Algorithm
Giải thuật sắp xếp Heapsort được đề xuất vào năm 1964 bởi J. W. J. Williams. Cùng năm đó, 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).
Giải thuật Heapsort còn được gọi là giải thuật vun đống, nó có thể được xem như bản cải tiến của Selection sort khi chia các phần tử thành 2 mảng con, 1 mảng các phần tử đã được sắp xếp và mảng còn lại các phần tử 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 đã được sắp xếp. Điều cải tiến ở Heapsort so với Selection sort ở việc sử dụng cấu trúc dữ liệu heap thay vì tìm kiếm tuyến tính (linear-time search) như Selection sort để tìm ra phần tử lớn nhất.
Heapsort là thuật toán in-place, nghĩa là không cần thêm bất cứ cấu trúc dữ liệu phụ trợ trong quá trình chạy thuật toán. Tuy nhiên, giải thuật này không có độ ổn định (stability).
Thuật toán sắp xếp Heap Sort được chia thành hai giai đoạn:
Giai đoạn 1:
Từ dãy dữ liệu input, ta sẽ sắp xếp chúng thành một heap (dạng cấu trúc cây nhị phân). Heap này có thể là Min-heap (nút gốc có giá trị bé nhất) hoặc Max-heap (nút gốc có giá trị lớn nhất)
Giai đoạn 2:
Giai đoạn này gồm các thao tác được lặp đi lặp lại cho đến khi mảng dữ liệu được toàn tất sắp xếp.
Triển khai thuật toán Heap Sort
Dù tốc độ chạy của Heap Sort có đôi chút chậm hơn Quick Sort, nhưng bù lại Heapsort là giải thuật đảm bảo trong trường hợp xấu nhất, độ phức tạp giải thuật cũng là O (n log n). Giải thuật này cũng không cần thêm các cấu trúc dữ liệu phụ trợ trong quá trình thực thi, do đó sẽ có tốc độ nhanh và thường được sử dụng rộng rãi do không khó để hiện thực.
Author: Vũ Hoàng Tuấn
Xem thêm các bài chia sẻ, hướng dẫn học lập trình khác tại đây.
0 Lời bình