Xem xét và thử nghiệm các phương pháp sắp xếp. Phần I

Hôm nọ, trong phần bình luận của VKontakte, tôi đã tranh cãi với một trong những sinh viên khác của dự án. Bản chất của cuộc tranh chấp là “ai sẽ thắng” - một phương thức sort()từ một lớp java.util.Arrayshoặc tự viết triển khai các thuật toán đơn giản: bong bóng , chèn , lựa chọn , shell (thuật toán Shell). Đối với một số người, câu trả lời cho câu hỏi này có thể hiển nhiên, nhưng vì tranh chấp nảy sinh, mặc dù thực tế là mỗi bên đều có “nguồn đáng tin cậy” ủng hộ quan điểm của mình, nên người ta đã quyết định tiến hành một nghiên cứu, kéo dài chất xám trong quá trình, thực hiện các thuật toán khác nhau. TL;DR: java.util.Arrays.sort() nó dẫn đầu vô điều kiện trong các mảng có từ 100.000 phần tử trở lên; với kích thước nhỏ hơn, phương pháp Shell đôi khi có thể cạnh tranh với nó. Phần còn lại của các thuật toán được xem xét hoàn toàn trống rỗng và chỉ có thể hữu ích trong một số điều kiện kỳ ​​lạ. Bây giờ chúng ta hãy xem cách các mảng được sắp xếp trong các thiết bị uber silicon của chúng ta.

Sắp xếp lựa chọn. Sắp xếp theo lựa chọn

Hãy bắt đầu với phương pháp đơn giản và rõ ràng nhất. Bản chất của nó đã được Robert Sedgwick thể hiện một cách hoàn hảo cho chúng ta trong video bài giảng của anh ấy về Coursera (Tôi sẽ trích dẫn hoạt hình từ đó mà tôi đã nén rất tệ thành ảnh gif): Xem Chạy qua mảng từ phần tử đầu tiên, ở mỗi bước chúng tôi tìm kiếm phần tử tối thiểu ở phía bên phải mà chúng ta hoán đổi phần tử hiện tại. Do đó, chúng tôi bảo lưu phiên bản cuối cùng của mảng ở dạng được sắp xếp. Đây là mã triển khai thuật toán này trong Java:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

Phân tích thuật toán cho thấy cần phải lược qua phần còn lại của mảng ở mỗi lần truyền, tức là chúng ta sẽ cần chính xác N + (N-1) + (N-2) + ... + 1 = N^ So sánh 2/2. Do đó, độ phức tạp của thuật toán là O(N^2). Điều đó có nghĩa là gì? Điều này có nghĩa là bằng cách tăng số phần tử trong mảng (N) lên 2 lần, chúng ta sẽ tăng thời gian chạy của thuật toán không phải lên 2 mà là 2^2 = 4 lần. Bằng cách tăng N lên 10 lần, chúng ta sẽ tăng thời gian hoạt động lên 100 lần, v.v. Trên máy tính xách tay năm 2012 của tôi có bộ xử lý Core i3 chạy Ubuntu 14.4, tôi có thời gian hoạt động như sau:

Sắp xếp chèn. Sắp xếp chèn

Ở đây ý tưởng hơi khác một chút. Một lần nữa, chúng ta hãy chuyển sang hoạt hình từ Doctor Sedgwick: View Những gì ở phía trước thậm chí còn chưa được chúng tôi xem và mọi thứ chúng tôi bỏ lại phía sau luôn giữ nguyên trật tự. Vấn đề là chúng ta “trả” từng phần tử mới của mảng ban đầu về phần đầu cho đến khi nó “nằm” trên phần tử nhỏ hơn. Do đó, chúng ta lại có N lượt (cho mỗi phần tử của mảng ban đầu), nhưng trong mỗi lượt, trong hầu hết các trường hợp, chúng ta không xem xét toàn bộ phần còn lại mà chỉ xem xét một phần. Nghĩa là, chúng ta sẽ nhận được tùy chọn 1 + (N-1) + (N-2) + … + N = N^2/2 chỉ khi chúng ta phải trả từng phần tử tiếp theo về đầu, nghĩa là trong trường hợp của mảng đầu vào được sắp xếp “ngược lại” (không may, không may). Trong trường hợp một mảng đã được sắp xếp (đây là may mắn) sẽ có một phần mềm miễn phí hoàn chỉnh - trên mỗi lượt chỉ có một so sánh và giữ nguyên phần tử, nghĩa là thuật toán sẽ hoạt động theo thời gian tỷ lệ thuận với N. Độ phức tạp của thuật toán sẽ được xác định theo trường hợp lý thuyết xấu nhất, đó là O(N^2). Tính trung bình, thời gian thực hiện sẽ tỷ lệ thuận với N^2/4, tức là nhanh gấp đôi so với thuật toán trước. Trong quá trình triển khai của tôi, do sử dụng hoán vị không tối ưu nên thời gian chạy dài hơn so với Selection. Tôi dự định sửa chữa và cập nhật bài viết sớm. Đây là mã và kết quả hoạt động của nó trên cùng một máy:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Phân loại vỏ. Phân loại vỏ

Một anh chàng thông minh, Donald Schell, đã nhận thấy vào năm 1959 rằng các trường hợp tốn kém nhất trong thuật toán chèn là khi phần tử quay trở lại rất xa về đầu mảng: trong một số lần chuyển, chúng ta đưa phần tử về đầu một vài vị trí , và trên một đường chuyền khác gần như xuyên qua toàn bộ mảng đến đầu rất xa và dài. Có thể làm điều này cùng một lúc bằng cách nhảy qua một số yếu tố? Và anh ấy đã tìm ra cách như vậy. Nó bao gồm việc thực hiện tuần tự các loại sắp xếp từng phần đặc biệt, thường được gọi là d-sort hoặc, theo Sedgwick, h-sort (tôi nghi ngờ h có nghĩa là hop). Ví dụ: 3-sort sẽ so sánh phần tử được đề cập không phải với phần tử trước đó mà sẽ bỏ qua hai phần tử và so sánh ngược lại với phần tử có 3 vị trí. Nếu thay đổi sẽ so sánh lại với phần tử thứ 3 ở vị trí thứ 3 và cứ thế. Điểm mấu chốt là mảng kết quả sẽ được “sắp xếp 3”, tức là vị trí sai của các phần tử sẽ nhỏ hơn 3 vị trí. Làm việc với thuật toán chèn này sẽ dễ dàng và dễ chịu. Nhân tiện, “1-sắp xếp” không gì khác hơn chỉ là một thuật toán chèn =) Bằng cách áp dụng tuần tự h-sort cho mảng với giá trị h giảm dần, chúng ta có thể sắp xếp một mảng lớn nhanh hơn. Nó trông như thế này: Xem Thử thách ở đây là làm thế nào để chọn đúng thứ tự sắp xếp từng phần. Cuối cùng, hiệu suất của thuật toán phụ thuộc vào điều này. Phổ biến nhất là dãy do Donald Knuth đề xuất: h = h*3 + 1, tức là 1, 4, 13, 40, ... và cứ thế lên tới 1/3 kích thước mảng. Trình tự này cung cấp hiệu suất tốt và cũng dễ thực hiện. Việc phân tích thuật toán đòi hỏi rất nhiều ngôn ngữ và vượt quá khả năng của tôi. Phạm vi phân tích cũng được xác định bởi nhiều biến thể của chuỗi h. Theo kinh nghiệm, chúng ta có thể nói rằng tốc độ của thuật toán là rất tốt - hãy tự mình xem: Một triệu phần tử trong chưa đầy một giây! Và đây là mã Java với chuỗi Knut.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Sắp xếp bong bóng. Phương pháp bong bóng

Đây là một cổ điển! Hầu hết mọi lập trình viên mới làm quen đều thực hiện thuật toán này. Đó là một tác phẩm kinh điển đến nỗi Tiến sĩ Sedgwick thậm chí còn không có phim hoạt hình cho nó, vì vậy tôi phải tự mình thực hiện công việc đó. Xem Ở đây, trên mỗi lượt, chúng ta duyệt mảng từ đầu đến cuối, hoán đổi các phần tử lân cận không theo thứ tự. Kết quả là, các phần tử lớn nhất “thả nổi” (do đó có tên) về cuối mảng. Chúng tôi bắt đầu mỗi lượt mới một cách lạc quan với hy vọng rằng mảng đã được sắp xếp ( sorted = true). Đến cuối đoạn văn nếu thấy mình viết sai thì chúng ta bắt đầu đoạn văn mới. Khó khăn ở đây là, một lần nữa, chúng ta phải duyệt qua (gần như) toàn bộ mảng trên mỗi lượt. Sự so sánh xảy ra ở mọi bước, trao đổi xảy ra ở hầu hết mọi bước, điều này làm cho thuật toán này trở thành một trong những thuật toán chậm nhất (nếu chúng ta xem xét những thuật toán được triển khai hợp lý chứ không phải "sắp xếp rung" và những thuật toán khác tương tự). Điều thú vị là về mặt hình thức, độ phức tạp ở đây cũng sẽ bằng O(N^2), nhưng hệ số này cao hơn nhiều so với hệ số chèn và lựa chọn. Mã thuật toán:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Thời gian hoạt động: Cảm nhận sự khác biệt: hơn nửa giờ trên một triệu phần tử! Kết luận: Không bao giờ sử dụng thuật toán này!!!

Tóm tắt phần đầu tiên

Do đó, tôi khuyên bạn nên xem bảng chung về các thuật toán này. Bạn cũng có thể so sánh với kết quả của phương pháp tích hợp sẵn java.util.Arrays.sort(). Nó trông giống như một loại phép thuật nào đó - cái gì có thể nhanh hơn Shell? Tôi sẽ viết về điều này trong phần tiếp theo. Ở đó, chúng ta sẽ xem xét các thuật toán sắp xếp nhanh được sử dụng rộng rãi, cũng như sắp xếp hợp nhất, tìm hiểu về sự khác biệt trong các phương pháp sắp xếp mảng từ kiểu nguyên thủy và kiểu tham chiếu, đồng thời làm quen với một giao diện rất quan trọng trong vấn đề này Comparable;) Dưới đây bạn có thể nghiên cứu một biểu đồ được xây dựng theo thang logarit bằng cách sử dụng các bảng dữ liệu. Đường càng phẳng thì thuật toán càng tốt =) Ai muốn tải toàn bộ project về và tự chạy test thì giữ link: Java Hẹn gặp lại các bạn ở phần tiếp theo! =)