بررسی و آزمایش روش های مرتب سازی. قسمت اول

روز دیگر، در نظرات VKontakte، من با یکی از دانش آموزان دیگر این پروژه بحث کردم. ماهیت اختلاف "چه کسی برنده خواهد شد" بود - روشی sort()از یک کلاس java.util.Arraysیا پیاده سازی های خودنوشته الگوریتم های ساده: حباب ، درج ، انتخاب ، پوسته (الگوریتم شل). برای برخی، پاسخ به این سوال ممکن است بدیهی باشد، اما از آنجایی که اختلاف ایجاد شد، علیرغم اینکه هر یک از طرفین دارای "منابع محترم" به نفع دیدگاه خود بودند، تصمیم گرفته شد که مطالعه ای انجام شود که ماده خاکستری را در آن گسترش دهد. فرآیند، پیاده سازی الگوریتم های مختلف. TL;DR: java.util.Arrays.sort() بدون قید و شرط در آرایه های 100000 عنصر یا بیشتر رهبر است؛ با اندازه کوچکتر، روش Shell گاهی اوقات می تواند با آن رقابت کند. بقیه الگوریتم های در نظر گرفته شده کاملاً خالی هستند و فقط در برخی شرایط عجیب و غریب می توانند مفید باشند. حالا بیایید ببینیم که آرایه‌ها چگونه در دستگاه‌های uber سیلیکونی ما مرتب شده‌اند.

مرتب سازی انتخابی مرتب سازی بر اساس انتخاب

بیایید با ساده ترین و واضح ترین روش شروع کنیم. ماهیت آن را رابرت سدویک در سخنرانی ویدیویی خود در مورد coursera کاملاً به ما نشان داده است (من انیمیشن را از آنجا نقل می کنم که بدجوری در یک گیف فشرده شده است): مشاهده در حال اجرا در آرایه از عنصر اول، در هر مرحله ما به دنبال حداقل عنصر در سمت راست باشید که عنصر فعلی را با آن عوض می کنیم. در نتیجه، نسخه نهایی آرایه خود را به شکل مرتب شده رزرو می کنیم. در اینجا کد پیاده سازی این الگوریتم در جاوا آمده است:

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

تجزیه و تحلیل الگوریتم نشان می دهد که در هر گذر باید بقیه آرایه را شانه کرد، یعنی دقیقاً به N + (N-1) + (N-2) + ... + 1 = N^ نیاز خواهیم داشت. 2/2 مقایسه بنابراین، پیچیدگی الگوریتم O(N^2) است. این یعنی چی؟ یعنی با افزایش 2 برابری تعداد عناصر آرایه (N)، زمان اجرای الگوریتم را نه 2، بلکه 2^2 = 4 برابر افزایش می دهیم. با افزایش 10 برابری N، زمان کارکرد را 100 برابر افزایش می دهیم و به همین ترتیب. در لپ تاپ سال 2012 خود با پردازنده Core i3 که اوبونتو 14.4 را اجرا می کند، آپ تایم زیر را دریافت کردم:

مرتب سازی درج. مرتب سازی درج

در اینجا ایده کمی متفاوت است. بیایید دوباره به انیمیشن Doctor Sedgwick بپردازیم: مشاهده آنچه در پیش است حتی توسط ما مشاهده نشده است و هر چیزی که پشت سر می گذاریم همیشه مرتب است. نکته این است که ما هر عنصر جدید آرایه اصلی را تا زمانی که روی یک عنصر کوچکتر قرار بگیرد، به ابتدا "برگردانیم". بنابراین، ما دوباره N پاس داریم (برای هر عنصر از آرایه اصلی)، اما در هر عبور، در بیشتر موارد، ما به کل باقیمانده نگاه نمی کنیم، بلکه فقط به یک قسمت نگاه می کنیم. یعنی گزینه 1 + (N-1) + (N-2) + … + N = N^2/2 را فقط در صورتی دریافت خواهیم کرد که هر عنصر بعدی را به همان ابتدا برگردانیم، یعنی در مورد از ورودی آرایه "در معکوس" مرتب شده است (بدشانس، بدشانس). در مورد یک آرایه از قبل مرتب شده (شانس اینجاست) یک امتیاز رایگان کامل وجود خواهد داشت - در هر پاس فقط یک مقایسه وجود دارد و عنصر در جای خود باقی می ماند، یعنی الگوریتم در زمانی متناسب با N کار می کند. پیچیدگی الگوریتم با بدترین حالت نظری، یعنی O(N^2) تعیین خواهد شد. به طور متوسط، زمان عملیات متناسب با N^2/4 خواهد بود، یعنی دو برابر سریعتر از الگوریتم قبلی. در پیاده سازی من به دلیل عدم استفاده بهینه از جایگشت، زمان اجرا بیشتر از Selection بود. من قصد دارم به زودی پست را اصلاح و به روز کنم. در اینجا کد و نتیجه عملکرد آن در همان دستگاه است:

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

مرتب سازی پوسته مرتب سازی پوسته

یک پسر باهوش، دونالد شل، در سال 1959 متوجه شد که گران‌ترین موارد در الگوریتم برای درج زمانی است که عنصر بسیار دور به ابتدای آرایه برمی‌گردد: در برخی از گذرها، عنصر را با چند موقعیت به ابتدا برمی‌گردانیم. ، و در دیگری عبور تقریباً از کل آرایه تا ابتدا دور و دراز است. آیا می توان این کار را همزمان با پرش از چندین عنصر انجام داد؟ و او چنین راهی را پیدا کرد. این شامل انجام متوالی مرتب‌سازی جزئی خاص است که عموماً به آنها d-sort یا طبق گفته Sedgwick، h-sort می‌گویند (من گمان می‌کنم h به معنای پرش است). به عنوان مثال، مرتب سازی 3، عنصر مورد نظر را با عنصر قبلی مقایسه نمی کند، اما از دو مورد رد می شود و با یکی از 3 موقعیت عقب مقایسه می شود. در صورت تغییر، دوباره آن را با موقعیت عنصر 3 و غیره مقایسه می کند. نکته اصلی این است که آرایه به دست آمده "3- مرتب شده" خواهد بود، یعنی موقعیت نادرست عناصر کمتر از 3 موقعیت خواهد بود. کار با این الگوریتم درج آسان و دلپذیر خواهد بود. به هر حال، "1-sort" چیزی بیش از یک الگوریتم درج نیست =) با اعمال ترتیب مرتب سازی h به آرایه با کاهش مقادیر h، می توانیم یک آرایه بزرگ را سریعتر مرتب کنیم. در اینجا به نظر می رسد: مشاهده چالش اینجاست که چگونه دنباله درستی از مرتب سازی جزئی را انتخاب کنیم. در نهایت، عملکرد الگوریتم به این بستگی دارد. متداول ترین دنباله پیشنهادی دونالد کنوت است: h = h*3 + 1، یعنی 1، 4، 13، 40، ... و به همین ترتیب تا 1/3 اندازه آرایه. این دنباله عملکرد مناسبی را ارائه می دهد و همچنین پیاده سازی آن آسان است. تجزیه و تحلیل الگوریتم نیاز به هزاران زبان دارد و از توانایی من خارج است. وسعت تجزیه و تحلیل نیز توسط انواع مختلف دنباله های h تعیین می شود. از نظر تجربی می توان گفت که سرعت الگوریتم بسیار خوب است - خودتان ببینید: یک میلیون عنصر در کمتر از یک ثانیه! و در اینجا کد جاوا با دنباله 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;
            }
        }
    }

مرتب سازی حبابی روش حباب

این یک کلاسیک است! تقریباً هر برنامه نویس مبتدی این الگوریتم را پیاده سازی می کند. آنقدر کلاسیک است که دکتر سدویک حتی یک انیمیشن برای آن نداشت، بنابراین من مجبور شدم کار را خودم انجام دهم. مشاهده در اینجا، در هر پاس، آرایه را از ابتدا تا انتها پیمایش می‌کنیم و عناصر همسایه را که از نظم خارج شده‌اند، عوض می‌کنیم. در نتیجه، بزرگترین عناصر "شناور" (از این رو نام) تا انتهای آرایه شناور می شوند. هر پاس جدید را با خوش بینانه شروع می کنیم به این امید که آرایه از قبل مرتب شده باشد ( sorted = true). در پایان گذر اگر دیدیم اشتباه کرده ایم، یک گذر جدید را شروع می کنیم. مشکل در اینجا این است که، دوباره، ما در حال پیمایش (تقریبا) کل آرایه در هر پاس هستیم. مقایسه در هر مرحله اتفاق می‌افتد، مبادله تقریباً در هر مرحله اتفاق می‌افتد، که این الگوریتم را یکی از کندترین الگوریتم‌ها می‌کند (اگر الگوریتم‌های پیاده‌سازی شده منطقی را در نظر بگیریم، نه "تکان دادن مرتب کردن" و موارد مشابه). جالب است که به طور رسمی پیچیدگی در اینجا نیز برابر با O(N^2) خواهد بود، اما ضریب آن بسیار بالاتر از ضریب درج و انتخاب است. کد الگوریتم:

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

زمان عملیات: تفاوت را احساس کنید: بیش از نیم ساعت روی یک میلیون عنصر! نتیجه گیری: هرگز از این الگوریتم استفاده نکنید!!!

خلاصه قسمت اول

در نتیجه، پیشنهاد می کنم جدول کلی این الگوریتم ها را مشاهده کنید. همچنین می توانید با نتایج روش داخلی مقایسه کنید java.util.Arrays.sort(). به نظر نوعی جادو است - چه چیزی می تواند سریعتر از شل باشد؟ در قسمت بعدی در این مورد خواهم نوشت. در آنجا به الگوریتم‌های مرتب‌سازی سریع پرکاربرد و همچنین مرتب‌سازی ادغام می‌پردازیم، با تفاوت روش‌های مرتب‌سازی آرایه‌ها از ابتدایی‌ها و انواع مرجع آشنا می‌شویم و همچنین با یک رابط بسیار مهم در این مورد آشنا می‌شویم؛ Comparable) در زیر می‌توانید مطالعه کنید. یک نمودار ساخته شده در مقیاس لگاریتمی با استفاده از جداول داده. هر چه خط صاف تر باشد، الگوریتم بهتر است =) برای کسانی که می خواهند کل پروژه را دانلود کنند و تست ها را خودشان اجرا کنند، لینک را نگه دارند: جاوا در قسمت بعدی می بینمت! =)