Çeşidləmə üsullarının nəzərdən keçirilməsi və sınaqdan keçirilməsi. I hissə

Ötən gün VKontakte-də şərhlərdə layihənin digər tələbələrindən biri ilə mübahisə etdim. Mübahisənin mahiyyəti "kim qazanacaq" idi - sort()sinifdən bir üsul java.util.Arraysvə ya sadə alqoritmlərin öz-özünə yazılmış tətbiqləri: qabarcıq , daxiletmə , seçim , qabıq (Shell alqoritmi). Bəziləri üçün bu sualın cavabı açıq ola bilər, lakin mübahisə yarandığından, hər bir tərəfin öz nöqteyi-nəzərinin lehinə "hörmətli mənbələrə" malik olmasına baxmayaraq, boz maddəni uzatmaqla bir araşdırma aparmaq qərara alındı. müxtəlif alqoritmlərin həyata keçirilməsi prosesi. TL;DR: java.util.Arrays.sort() 100.000 və ya daha çox elementdən ibarət massivlərdə qeyd-şərtsiz liderdir; daha kiçik ölçüdə Shell metodu bəzən onunla rəqabət apara bilər. Baxılan alqoritmlərin qalan hissəsi tamamilə boşdur və yalnız bəzi ekzotik şəraitdə faydalı ola bilər. İndi isə silikon uber-cihazlarımızda massivlərin necə çeşidləndiyinə baxaq.

Seçim çeşidi. Seçimlə çeşidləmə

Ən sadə və ən aydın üsulla başlayaq. Bunun mahiyyəti bizə Robert Sedgwick tərəfindən kurslara dair video mühazirəsində mükəmməl şəkildə nümayiş etdirilir (Mən oradan gif-də pis şəkildə sıxışdırdığım animasiyadan sitat gətirəcəyəm): Baxış Birinci elementdən massivdə qaçış, hər addımda biz cari elementi dəyişdirdiyimiz sağ tərəfdəki minimum elementi axtarın. Nəticədə, massivimizin son versiyasını çeşidlənmiş formada ehtiyatda saxlayırıq. Java-da bu alqoritmi həyata keçirən kod budur:

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;
    }

Alqoritmin təhlili göstərir ki, hər keçiddə massivin qalan hissəsini taramaq lazımdır, yəni bizə tam olaraq N + (N-1) + (N-2) + ... + 1 = N ^ lazımdır. 2/2 müqayisə. Beləliklə, alqoritmin mürəkkəbliyi O(N^2) təşkil edir. Bu nə deməkdir? Bu o deməkdir ki, massivdə (N) elementlərin sayını 2 dəfə artırmaqla alqoritmin işləmə müddətini 2 deyil, 2^2 = 4 dəfə artıracağıq. N-i 10 dəfə artırmaqla, əməliyyat müddətini 100 dəfə artıracağıq və s. Ubuntu 14.4 ilə işləyən Core i3 prosessoru olan 2012 noutbukumda aşağıdakı iş vaxtı əldə etdim:

Daxiletmə çeşidi. Daxiletmə çeşidi

Burada fikir bir qədər fərqlidir. Yenə də Doktor Sedqvikin animasiyasına müraciət edək: Baxın Qarşıda olana hələ bizim tərəfimizdən baxılmayıb və geridə qoyduqlarımız həmişə öz qaydasında qalır. Məsələ ondadır ki, biz orijinal massivin hər bir yeni elementini daha kiçik bir elementə “dayanana qədər” əvvəlinə “qaytarırıq”. Beləliklə, yenə də N keçidimiz var (orijinal massivin hər bir elementi üçün), lakin hər keçiddə, əksər hallarda, biz bütün qalığa deyil, yalnız bir hissəsinə baxırıq. Yəni 1 + (N-1) + (N-2) + … + N = N^2/2 variantını yalnız hər bir növbəti elementi ən başlanğıcına qaytarmalı olacağıq, yəni bu halda alacağıq. girişin “əksinə” sıralanması (bəxtsiz, uğursuz). Artıq çeşidlənmiş massiv (burada şans var) halında tam pulsuz olacaq - hər keçiddə yalnız bir müqayisə var və elementi yerində qoyur, yəni alqoritm N ilə mütənasib vaxtda işləyəcək. Mürəkkəblik alqoritmin ən pis nəzəri halı, yəni O( N^2) ilə müəyyən ediləcək. Orta hesabla, əməliyyat müddəti N^2/4 ilə mütənasib olacaq, yəni əvvəlki alqoritmdən iki dəfə sürətli. Tətbiqimdə, permutasiyanın qeyri-optimal istifadəsi səbəbindən işləmə müddəti Seçimdən daha uzun idi. Tezliklə postu düzəltməyi və yeniləməyi planlaşdırıram. Budur kod və eyni maşında işləməsinin nəticəsi:

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;
            }
        }
    }

Qabıq çeşidi. Qabıq çeşidi

Ağıllı oğlan Donald Şell hələ 1959-cu ildə qeyd etdi ki, əlavələr üçün alqoritmdə ən bahalı hallar elementin massivin əvvəlinə çox uzağa qayıtmasıdır: bəzi keçidlərdə elementi bir neçə mövqe ilə başlanğıca qaytarırıq. , və başqa bir keçiddə demək olar ki, bütün massivdən başlanğıca qədər uzaq və uzundur. Bunu bir anda bir neçə elementdən keçərək etmək mümkündürmü? Və belə bir yol tapdı. Bu, ümumiyyətlə d-sort və ya Sedgwick-ə görə h-sort adlanan ardıcıl olaraq yerinə yetirilən xüsusi qismən sortlardan ibarətdir (h hop deməkdir). 3-sort, məsələn, sözügedən elementi əvvəlki ilə deyil, ikisini atlayacaq və bir 3 mövqe ilə müqayisə edəcək. Dəyişdirilərsə, onu yenidən element 3 mövqeləri ilə müqayisə edəcək və s. Nəticə odur ki, ortaya çıxan massiv "3-sorted" olacaq, yəni elementlərin yanlış mövqeyi 3 mövqedən az olacaq. Bu daxiletmə alqoritmi ilə işləmək asan və xoş olacaq. Yeri gəlmişkən, “1-sort” sadəcə daxiletmə alqoritmindən başqa bir şey deyil =) H dəyərləri azalan massivə ardıcıl olaraq h-sort tətbiq etməklə biz böyük massivi daha sürətli çeşidləyə bilərik. Göründüyü kimi: Baxın Burada problem qismən çeşidlərin düzgün ardıcıllığını necə seçməkdir. Nəhayət, alqoritmin performansı bundan asılıdır. Ən çox yayılmışı Donald Knuth tərəfindən təklif olunan ardıcıllıqdır: h = h*3 + 1, yəni 1, 4, 13, 40, ... və s. massiv ölçüsünün 1/3 hissəsinə qədər. Bu ardıcıllıq layiqli performans təmin edir və həyata keçirmək də asandır. Alqoritmin təhlili tonlarla dil tələb edir və mənim bacarığım xaricindədir. Təhlilin genişliyi h ardıcıllığının çoxlu variantları ilə də müəyyən edilir. Empirik olaraq deyə bilərik ki, alqoritmin sürəti çox yaxşıdır - özünüz baxın: Bir saniyədən az müddətdə bir milyon element! Və burada Knut ardıcıllığı ilə Java kodu.

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;
            }
        }
    }

Bubble çeşidi. Bubble üsulu

Bu klassikdir! Demək olar ki, hər bir təcrübəsiz proqramçı bu alqoritmi həyata keçirir. Bu elə klassikdir ki, doktor Sedgwick-in onun üçün animasiya belə yox idi, ona görə də işi özüm etməli oldum. Baxın Burada, hər keçiddə sıradan çıxmış qonşu elementləri dəyişdirərək massivi əvvəldən axıra qədər keçirik. Nəticədə, ən böyük elementlər massivin sonuna qədər "üzər" (buna görə də adı). Biz hər yeni keçidə nikbinliklə başlayırıq ki, massiv artıq sıralanıb ( sorted = true). Parçanın sonunda səhv etdiyimizi görsək, yeni bir keçidə başlayırıq. Burada çətinlik ondan ibarətdir ki, biz yenə də hər keçiddə bütün massivi (demək olar ki) keçirik. Müqayisə hər addımda baş verir, mübadilə demək olar ki, hər addımda baş verir ki, bu da bu alqoritmi ən yavaşlardan birinə çevirir (əgər biz rasional şəkildə həyata keçirilənləri nəzərə alsaq, “sırtlama” və bu kimi digərləri deyil). Maraqlıdır ki, formal olaraq burada mürəkkəblik də O(N^2)-ə bərabər olacaq, lakin əmsal əlavələr və seçimlərdən xeyli yüksəkdir. Alqoritm kodu:

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;
        }
    }

İşləmə müddəti: Fərqi hiss edin: bir milyon elementdə yarım saatdan çox! Nəticə: Heç vaxt bu alqoritmdən istifadə etməyin!!!

Birinci hissənin xülasəsi

Nəticədə bu alqoritmlər üçün ümumi cədvələ baxmağı təklif edirəm. Siz həmçinin daxili metodun nəticələri ilə müqayisə edə bilərsiniz java.util.Arrays.sort(). Bir növ sehr kimi görünür - Shell-dən daha sürətli nə ola bilər? Bu haqda növbəti hissədə yazacam. Orada geniş istifadə olunan sürətli çeşidləmə alqoritmlərinə baxacağıq, həmçinin çeşidləmə birləşdirəcək, massivlərin primitivlərdən və istinad tiplərindən çeşidlənməsi üsullarının fərqini öyrənəcəyik, həmçinin bu məsələdə çox vacib interfeys ilə tanış olacağıq Comparable;) Aşağıda öyrənə bilərsiniz. verilənlər cədvəllərindən istifadə edərək loqarifmik miqyasda qurulmuş qrafik. Xətt nə qədər düz olarsa, alqoritm də bir o qədər yaxşı olar =) Bütün layihəni yükləmək və təkbaşına testlər keçirmək istəyənlər üçün linki saxlayın: Java Növbəti hissədə görüşənədək! =)