Chương 3: Các Thuật Toán Sắp Xếp

Sắp xếp là quá trình sắp xếp lại một dãy các đối tượng để đưa chúng vào một trật tự logic nhất định. Ví dụ, hóa đơn thẻ tín dụng của bạn trình bày các giao dịch theo thứ tự ngày tháng, và bạn sắp xếp sách của mình trên kệ sách theo thứ tự bảng chữ cái của tác giả và tiêu đề. Sắp xếp là một thao tác cơ bản trong khoa học máy tính và đóng vai trò quan trọng trong nhiều ứng dụng. Có nhiều thuật toán sắp xếp cổ điển khác nhau, mỗi thuật toán thể hiện một cách tiếp cận khác nhau đối với vấn đề này.

Trong chương này, chúng ta sẽ xem xét một số phương pháp sắp xếp cổ điển và một cấu trúc dữ liệu quan trọng được gọi là hàng đợi ưu tiên. Chúng ta bắt đầu bằng việc thảo luận về một số phương pháp sắp xếp cơ bản, bao gồm sắp xếp chọn, sắp xếp chèn và shellsort. Các phương pháp này thích hợp để sử dụng trong nhiều ứng dụng, nhưng đối với các bài toán lớn, chúng ta sẽ chuyển sang sử dụng mergesort và quicksort, hai thuật toán sắp xếp đệ quy có thể được sử dụng để sắp xếp số lượng lớn các mục. Cuối cùng, chúng ta sẽ thảo luận về hàng đợi ưu tiên và cách sử dụng chúng trong sắp xếp và các ứng dụng khác.

Các Sắp Xếp Cơ Bản

Các thuật toán sắp xếp đơn giản nhất thực hiện các thao tác sau:

Sắp xếp chọn: Tìm ra phần tử nhỏ nhất và trao đổi nó với phần tử đầu tiên, sau đó tìm phần tử thứ hai nhỏ nhất và trao đổi nó với phần tử thứ hai, v.v.
Sắp xếp chèn: Lấy từng phần tử theo lượt và chèn nó vào vị trí thích hợp trong số những phần tử đã được xem xét (giữ chúng được sắp xếp).

Các thao tác này phản ánh cách con người thường thực hiện các tác vụ sắp xếp và hiệu quả đối với các bài toán nhỏ. Tuy nhiên, chúng không mở rộng tốt và trở nên không thực tế khi sắp xếp các mảng lớn.

Sắp Xếp Chọn

Sắp xếp chọn là một thuật toán sắp xếp đơn giản hoạt động như sau: Đầu tiên, tìm phần tử nhỏ nhất trong mảng và trao đổi nó với phần tử đầu tiên (chính nó nếu phần tử đầu tiên đã là nhỏ nhất). Sau đó, tìm phần tử tiếp theo nhỏ nhất và trao đổi nó với phần tử thứ hai. Tiếp tục theo cách này cho đến khi toàn bộ mảng được sắp xếp.

Vòng lặp bên trong của sắp xếp chọnĐây là bản dịch tiếng Việt của tệp Markdown:

Phương pháp sắp xếp chọn (selection sort) được sử dụng để tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp a[i..N-1]. Chỉ số của phần tử nhỏ nhất được lưu trong min. Sau đó, a[i] được trao đổi với a[min], đặt phần tử nhỏ nhất vào vị trí cuối cùng của nó. Khi chỉ số i di chuyển từ trái sang phải, các phần tử bên trái sẽ được sắp xếp và không bị chạm đến lại.

Đây là một cài đặt của phương pháp sắp xếp chọn bằng Java:

public static void selectionSort(Comparable[] a) {
    // Lấy độ dài của mảng
    int N = a.length;
    // Lặp qua từng phần tử của mảng
    for (int i = 0; i < N; i++) {
        // Gán chỉ số của phần tử nhỏ nhất là i
        int min = i;
        // Tìm phần tử nhỏ nhất trong mảng chưa được sắp xếp
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        // Trao đổi phần tử i với phần tử nhỏ nhất
        exch(a, i, min);
    }
}

Phương pháp sắp xếp chọn sử dụng khoảng ~N^2/2 phép so sánh và N phép trao đổi để sắp xếp một mảng có độ dài N. Thời gian chạy của nó không phụ thuộc vào đầu vào - nó mất khoảng thời gian như nhau để chạy phương pháp sắp xếp chọn cho một mảng đã được sắp xếp, một mảng có tất cả các phần tử bằng nhau, hoặc một mảng ngẫu nhiên.

Phương pháp sắp xếp chèn (Insertion Sort)

Phương pháp sắp xếp chèn là một thuật toán sắp xếp đơn giản khác, hoạt động bằng cách xây dựng mảng đã được sắp xếp một phần tử một lần. Nó kém hiệu quả hơn nhiều so với các thuật toán nâng cao hơn như quicksort, heapsort hoặc merge sort khi sử dụng trên các mảng lớn, nhưng nó có một số ưu điểm:

Nó hiệu quả với các tập dữ liệu nhỏ.
Nó hiệu quả hơn phương pháp sắp xếp chọn trong thực tế.
Nó ổn định; nghĩa là, nó không thay đổi thứ tự tương đối của các phần tử có khóa bằng nhau.
Nó là in-place; nghĩa là, chỉ yêu cầu một lượng bộ nhớ bổ sung O(1).
Nó là online; nghĩa là, có thể sắp xếp một danh sách khi nó nhận được.

Đây là một cài đặt của phương pháp sắp xếp chèn bằng Java:

public static void insertionSort(Comparable[] a) {
    // Lấy độ dài của mảng
    int N = a.length;
    // Lặp qua từng phần tử của mảng, bắt đầu từ phần tử thứ 2
    for (int i = 1; i < N; i++) {
        // Lặp qua các phần tử từ i về 0, di chuyển các phần tử lớn hơn lên một vị trí
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
    }
}

Vòng lặp bên trong của phương pháp sắp xếp chèn di chuyển các phần tử lớn hơn lên một vị trí, tạo ra chỗ trống để chèn phần tử hiện tại.Thời gian chạy của thuật toán sắp xếp chèn phụ thuộc vào thứ tự ban đầu của các mục trong đầu vào. Ví dụ, nếu mảng lớn và các mục của nó đã được sắp xếp (hoặc gần như được sắp xếp), thì thuật toán sắp xếp chèn sẽ nhanh hơn nhiều so với khi các mục được sắp xếp ngẫu nhiên hoặc theo thứ tự ngược lại.

Shellsort

Shellsort là một phần mở rộng đơn giản của thuật toán sắp xếp chèn, tăng tốc độ bằng cách cho phép trao đổi các mục mảng cách xa nhau, để tạo ra các mảng được sắp xếp một phần có thể được sắp xếp hiệu quả, cuối cùng bằng thuật toán sắp xếp chèn.

Ý tưởng là sắp xếp lại mảng để nó có thuộc tính rằng lấy mỗi mục h (bắt đầu từ bất kỳ đâu) sẽ cho ra một dãy con được sắp xếp. Một mảng như vậy được gọi là h-sorted. Nói cách khác, một mảng h-sorted là h dãy con được sắp xếp độc lập, được xen kẽ với nhau. Bằng cách h-sorting cho một số giá trị lớn của h, chúng ta có thể di chuyển các mục trong mảng xa và do đó làm cho việc h-sort với các giá trị h nhỏ hơn trở nên dễ dàng hơn. Sử dụng một quy trình như vậy cho bất kỳ dãy các giá trị của h kết thúc bằng 1 sẽ tạo ra một mảng được sắp xếp: đó là shellsort.

Dưới đây là một cài đặt của shellsort bằng Java:

public class MaxPQ<Key extends Comparable<Key>> {
    // Mảng chứa các phần tử ưu tiên
    private Key[] pq;
    // Số lượng phần tử trong hàng đợi
    private int N;
    
    public MaxPQ(int capacity) {
        // Khởi tạo mảng với kích thước capacity+1
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        // Kiểm tra xem hàng đợi có rỗng không
        return N == 0;
    }
   
    public void insert(Key key) {
        // Thêm một phần tử vào hàng đợi
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        // Lấy ra phần tử lớn nhất và xóa nó khỏi hàng đợi
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        // Sửa lại vị trí của phần tử để đảm bảo tính chất của hàng đợi
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        // Sửa lại vị trí của phần tử để đảm bảo tính chất của hàng đợi
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private boolea
```Dưới đây là bản dịch tiếng Việt của tệp Markdown:
 
```java
private boolean less(int i, int j) {
    // Trả về true nếu phần tử tại vị trí i nhỏ hơn phần tử tại vị trí j
    return pq[i].compareTo(pq[j]) < 0;
}
 
private void exch(int i, int j) {
    // Hoán đổi vị trí của hai phần tử tại các vị trí i và j
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}

Đoạn mã này triển khai một đống nhị phân định hướng cực đại sử dụng một mảng pq để lưu trữ cây nhị phân đầy đủ được sắp xếp theo đống. Các thao tác insert() và delMax() duy trì tính chất của đống bằng cách sử dụng các phương thức trợ giúp swim() và sink() để khôi phục thứ tự của đống bằng cách trao đổi các khóa với một cha lớn hơn một con hoặc một con lớn hơn cha tương ứng.

Đồng hồ bấm giờ

Một kiểu dữ liệu trừu tượng hữu ích hơn là một sự trừu tượng đơn giản và hiệu quả cho một đồng hồ bấm giờ, như được hiển thị ở trang đối diện. Để sử dụng nó, hãy tạo một đối tượng Stopwatch khi bạn muốn bắt đầu bấm giờ, sau đó sử dụng phương thức elapsedTime() để lấy thời gian đã trôi qua tính bằng giây kể từ khi đối tượng được tạo. Cài đặt sử dụng System.currentTimeMillis() của Java để lấy thời gian hiện tại tính bằng mili giây kể từ nửa đêm ngày 1 tháng 1 năm 1970.

Biến thành viên start ghi lại thời gian khi đồng hồ bấm giờ được tạo, và elapsedTime() sử dụng start để tính thời gian đã trôi qua. Ví dụ khách hàng được hiển thị là điển hình: nó thực hiện một số tính toán và sử dụng một Stopwatch để đo thời gian tính toán mất bao lâu. Kiểu dữ liệu Stopwatch là một sự trừu tượng hiệu quả vì nó tách biệt khái niệm về đồng hồ bấm giờ (giao diện) khỏi cài đặt (sử dụng System.currentTimeMillis() của Java). Sự tách biệt giữa giao diện và cài đặt là một đặc điểm cơ bản của các kiểu dữ liệu trừu tượng mà chúng ta sẽ thấy trong mọi ADT trong suốt cuốn sách này.

Tóm tắt

Các kiểu dữ liệu trừu tượng là một yếu tố thiết yếu của lập trình hướng đối tượng và được sử dụng rộng rãi trong lập trình hiện đại. Trong phần này, chúng ta đã thấy:

Định nghĩa một kiểu dữ liệu trừu tượng như một lớp Java, với các biến thành viên để định nghĩa các giá trị của kiểu dữ liệu và các phương thức thành viên để triển khai các thao tác trên những giá trị đó.
Phát triển nhiều cài đặt khác nhau của cùng một API, sử dụng các biểu diễn khác nhau của cùng một kiểu dữ liệu trừu tượng.Loại dữ liệu trừu tượng.
Phân biệt các API, khách hàng và triển khai của một loại dữ liệu trừu tượng.
Thiết kế API cho các loại dữ liệu trừu tượng.
Phát triển khách hàng và khách hàng kiểm tra để sử dụng trong kiểm tra và gỡ lỗi.
Lý luận về tính chính xác của một triển khai loại dữ liệu trừu tượng, sử dụng các khẳng định.
So sánh hiệu suất của các triển khai khác nhau của cùng một API.

Những hoạt động này là một phần thiết yếu của quá trình phát triển bất kỳ chương trình Java nào. Mọi chương trình Java mà chúng ta viết sẽ liên quan đến việc sử dụng các loại dữ liệu trừu tượng từ các thư viện; nhiều chương trình sẽ liên quan đến việc phát triển các loại dữ liệu trừu tượng mới. Trong phần tiếp theo, chúng tôi xem xét ba loại dữ liệu trừu tượng cơ bản là những thành phần thiết yếu trong rất nhiều chương trình, và trong Phần 1.4 chúng tôi xem xét quá trình phân tích các đặc điểm hiệu suất của các triển khai chi tiết.

Chapter 2 Algorithms Fundamentals Chapter 4 Searching Algorithms