جائزو وٺڻ ۽ ترتيب ڏيڻ جي طريقن جي جانچ. حصو I

ٻئي ڏينهن، VKontakte تي تبصرن ۾، مون منصوبي جي ٻين شاگردن مان هڪ سان بحث ڪيو. تڪرار جو خلاصو هو ”ڪير کٽيندو“ - sort()هڪ ڪلاس مان هڪ طريقو java.util.Arraysيا سادي الگورتھم جي خود لکيل عملن: بلبل , داخل ڪرڻ , چونڊ , شيل (شيل الگورٿم). ڪجهه ماڻهن لاء، هن سوال جو جواب واضح ٿي سگهي ٿو، پر جڏهن کان تڪرار پيدا ٿيو، ان حقيقت جي باوجود ته هر طرف پنهنجي نقطي نظر جي حق ۾ "معزز ذريعا" هئا، اهو هڪ مطالعو ڪرڻ جو فيصلو ڪيو ويو، سرمائي معاملي کي وڌايو. عمل، مختلف الگورتھم کي لاڳو ڪرڻ. TL؛ DR: java.util.Arrays.sort() اهو غير مشروط طور تي 100,000 عناصر يا وڌيڪ جي صفن تي اڳواڻ آهي؛ ننڍي سائيز سان، شيل طريقو ڪڏهن ڪڏهن ان سان مقابلو ڪري سگهي ٿو. باقي سمجهيا ويندڙ الگورتھم مڪمل طور تي خالي آهن ۽ صرف ڪجهه غير معمولي حالتن ۾ ڪارائتو ٿي سگهن ٿا. هاڻي اچو ته ڏسون ته اسان جي سلڪون اوبر ڊيوائسز ۾ ڪيئن ترتيب ڏنل آهن.

چونڊ جي ترتيب. چونڊ ذريعي ترتيب ڏيڻ

اچو ته آسان ۽ سڀ کان وڌيڪ واضح طريقي سان شروع ڪريون. ان جو خلاصو اسان کي مڪمل طور تي ڏيکاريو ويو آهي رابرٽ سيڊگوڪ پنهنجي وڊيو ليڪچر ۾ ڪورسرا (آئون اتان کان اينيميشن جو حوالو ڏيندس جنهن کي مون هڪ گف ۾ خراب طور تي دٻايو): ڏسو پهرين عنصر کان صف جي ذريعي ڊوڙندو، هر قدم تي اسان ساڄي پاسي گھٽ ۾ گھٽ عنصر ڳوليو، جنھن سان اسان موجوده ھڪڙي کي تبديل ڪريون ٿا. نتيجي طور، اسان ترتيب ڏنل شڪل ۾ اسان جي صف جو آخري نسخو محفوظ ڪيو. هتي جاوا ۾ هن الگورتھم کي لاڳو ڪرڻ جو ڪوڊ آهي:

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 ڀيرا وڌائڻ سان، اسان آپريٽنگ ٽائيم کي 100 ڀيرا وڌائينداسين، وغيره. منهنجي 2012 جي ليپ ٽاپ تي ڪور i3 پروسيسر سان Ubuntu 14.4 هلائيندڙ، مون کي هيٺين اپ ٽائم مليو:

داخل ٿيڻ جي ترتيب. داخل ٿيڻ جي ترتيب

هتي خيال ٿورو مختلف آهي. ٻيهر، اچو ته ڊاڪٽر سيڊگوڪ جي اينيميشن ڏانهن رخ ڪريون: ڏسو اڳتي ڇا آهي اڃا تائين اسان جي طرفان نه ڏٺو ويو آهي، ۽ هر شيء جيڪا اسان پوئتي ڇڏيندا آهيون هميشه ترتيب ۾ رهي ٿي. نقطو اهو آهي ته اسان اصل صف جي هر نئين عنصر کي "واپسي" شروع ڪندا آهيون جيستائين اهو "آرام" هڪ ننڍڙو عنصر تي. اهڙيء طرح، اسان وٽ ٻيهر N پاس (اصل صف جي هر عنصر لاء)، پر هر پاس ۾، اڪثر ڪيسن ۾، اسان باقي باقي نه ڏسندا آهيون، پر صرف هڪ حصو. اهو آهي، اسان کي اختيار حاصل ڪنداسين 1 + (N-1) + (N-2) + … + N = N^2/2 صرف ان صورت ۾ جڏهن اسان کي هر ايندڙ عنصر کي بلڪل شروعات ۾ واپس ڪرڻو پوندو، اهو آهي، صورت ۾. ان پٽ جي ترتيب ڏنل "ريورس" صف ۾ (بدقسمتي، بدقسمت). اڳ ۾ ئي ترتيب ڏنل صف جي صورت ۾ (هتي قسمت آهي) اتي هڪ مڪمل فريبي هوندي - هر پاس تي صرف هڪ مقابلو هوندو آهي ۽ عنصر کي جاءِ تي ڇڏي ويندو آهي، اهو آهي، الورورٿم وقت ۾ ڪم ڪندو N جي تناسب سان. پيچيدگي الورورٿم جو تعين ڪيو ويندو بدترين نظرياتي ڪيس، يعني O(N^2). سراسري طور تي، آپريٽنگ وقت N^2/4 جي متناسب هوندو، يعني اڳئين الگورتھم جي ڀيٽ ۾ ٻه ڀيرا تيز. منهنجي عمل ۾، اجازت جي غير بهتر استعمال جي ڪري، هلندڙ وقت چونڊ کان وڌيڪ ڊگهو هو. آئون جلد ئي پوسٽ کي درست ڪرڻ ۽ تازه ڪاري ڪرڻ جو منصوبو ڪندس. هتي ڪوڊ آهي ۽ ان جي آپريشن جو نتيجو ساڳئي مشين تي:

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 ۾ واپس نوٽ ڪيو ته الورورٿم ۾ سڀ کان مهانگو ڪيس داخل ڪرڻ لاءِ آهن جڏهن عنصر صف جي شروعات تائين تمام گهڻو واپس اچي ٿو: ڪجهه پاسن تي اسان عنصر کي شروعات ۾ واپس ڪريون ٿا ٻه پوزيشن سان. ، ۽ ٻئي لنگهه تي لڳ ڀڳ پوري صف کان شروع تائين تمام پري ۽ ڊگهو آهي. ڇا اهو ممڪن آهي ته هڪ ئي وقت ۾، ڪيترن ئي عناصر ذريعي جمپنگ؟ ۽ هن کي اهڙو رستو مليو. اهو ترتيبوار طور تي خاص جزوي قسم جي ڪارڪردگي تي مشتمل آهي، عام طور تي ڊي-سارٽ سڏيو ويندو آهي يا، Sedgwick جي مطابق، h-sort (مون کي شڪ آهي h جو مطلب آهي هاپ). 3-ترتيب، مثال طور، سوال ۾ عنصر جو مقابلو ڪندو پوئين ھڪڙي سان نه، پر ٻن کي ڇڏي ڏيندو ۽ ھڪڙي 3 پوزيشن سان مقابلو ڪندو. جيڪڏهن تبديل ڪيو ويو، اهو ان کي ٻيهر عنصر 3 پوزيشن واپس ۽ انهي سان مقابلو ڪندو. هيٺيون لڪير اهو آهي ته نتيجو وارو صف "3 ترتيب ڏنل" هوندو، اهو آهي، عناصر جي غلط پوزيشن 3 پوزيشن کان گهٽ هوندي. ھن داخل ڪرڻ واري الگورتھم سان ڪم ڪرڻ آسان ۽ خوشگوار ٿيندو. رستي ۾، "1-ترتيب" صرف هڪ داخل ڪرڻ واري الگورتھم کان وڌيڪ ڪجهه ناهي =) ترتيب سان ترتيب ڏيڻ سان h-sort کي ترتيب ڏيڻ سان گھٽجڻ سان، اسان هڪ وڏي صف کي تيزيء سان ترتيب ڏئي سگهون ٿا. ھتي اھو آھي جيڪو اھو ڏسڻ ۾ اچي ٿو: ڏسو چيلنج ھتي آھي جزوي قسم جي صحيح ترتيب کي ڪيئن چونڊيو. آخرڪار، الورورٿم جي ڪارڪردگي هن تي منحصر آهي. سڀ کان وڌيڪ عام آهي ڊونالڊ ڪنٿ پاران تجويز ڪيل ترتيب: h = h*3 + 1، اهو آهي، 1، 4، 13، 40، ... ۽ ائين ئي ترتيب جي سائيز جي 1/3 تائين. هي سلسلو مهذب ڪارڪردگي مهيا ڪري ٿو ۽ لاڳو ڪرڻ پڻ آسان آهي. الورورٿم جي تجزيي لاءِ گهڻين ٻولي جي ضرورت آهي ۽ اها منهنجي قابليت کان ٻاهر آهي. تجزيي جي وسعت پڻ h sequences جي ڪيترن ئي مختلف قسمن جي ذريعي طئي ڪئي وئي آهي. تجرباتي طور تي، اسان اهو چئي سگهون ٿا ته الورورٿم جي رفتار تمام سٺي آهي - پنهنجو پاڻ لاء ڏسو: هڪ سيڪنڊ کان به گهٽ ۾ هڪ ملين عناصر! ۽ ھتي آھي جاوا ڪوڊ 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؛) هيٺ توهان پڙهي سگهو ٿا. ڊيٽا جدولن جي استعمال سان لاگارٿمڪ اسڪيل تي ٺهيل هڪ گراف. جيتري قدر لائين، اوترو بهتر الورورٿم =) انهن لاءِ جيڪي مڪمل پروجيڪٽ ڊائون لوڊ ڪرڻ چاهين ٿا ۽ پنهنجون ٽيسٽون هلائڻ چاهين ٿا، لنڪ رکو: جاوا ملنداسين ايندڙ حصي ۾! =)