چھانٹنے کے طریقوں کا جائزہ اور جانچ۔ حصہ اول

دوسرے دن، VKontakte پر تبصرے میں، میں نے پروجیکٹ کے دوسرے طالب علموں میں سے ایک کے ساتھ بحث کی تھی۔ تنازعہ کا نچوڑ "کون جیتے گا" تھا - sort()کلاس سے ایک طریقہ java.util.Arraysیا سادہ الگورتھم کے خود تحریری نفاذ: bubble , insertion , Selection , shell (Shell algorithm)۔ کچھ لوگوں کے لیے، اس سوال کا جواب واضح ہو سکتا ہے، لیکن جب سے تنازعہ پیدا ہوا، اس حقیقت کے باوجود کہ ہر فریق کے اپنے نقطہ نظر کے حق میں "محترم ذرائع" موجود تھے، اس لیے یہ فیصلہ کیا گیا کہ ایک مطالعہ کرنے کا فیصلہ کیا گیا، جس میں سرمئی معاملے کو پھیلایا جائے۔ عمل، مختلف الگورتھم کو نافذ کرنا۔ TL؛ DR: java.util.Arrays.sort() یہ غیر مشروط طور پر 100,000 عناصر یا اس سے زیادہ کی صفوں پر رہنما ہے؛ چھوٹے سائز کے ساتھ، شیل طریقہ بعض اوقات اس کا مقابلہ کر سکتا ہے۔ باقی ماندہ الگورتھم مکمل طور پر خالی ہیں اور صرف کچھ غیر ملکی حالات میں کارآمد ہو سکتے ہیں۔ اب آئیے دیکھتے ہیں کہ ہمارے سلیکون اوبر ڈیوائسز میں صفوں کو کس طرح ترتیب دیا جاتا ہے۔

انتخاب کی ترتیب۔ انتخاب کے لحاظ سے ترتیب دینا

آئیے سب سے آسان اور واضح طریقہ سے شروع کرتے ہیں۔ اس کا نچوڑ ہمارے سامنے رابرٹ سیڈگوک نے کورسرا پر اپنے ویڈیو لیکچر میں بخوبی ظاہر کیا ہے (میں وہاں سے اس اینیمیشن کا حوالہ دوں گا جسے میں نے ایک gif میں بری طرح سے کمپریس کیا تھا): پہلے عنصر سے صف میں دوڑتے ہوئے دیکھیں ، ہر قدم پر ہم دائیں جانب کم از کم عنصر تلاش کریں، جس کے ساتھ ہم موجودہ کو تبدیل کرتے ہیں۔ نتیجے کے طور پر، ہم اپنی صف کا آخری ورژن ترتیب شدہ شکل میں محفوظ رکھتے ہیں۔ جاوا میں اس الگورتھم کو نافذ کرنے والا کوڈ یہ ہے:

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) ہے۔ اس کا کیا مطلب ہے؟ اس کا مطلب ہے کہ ارے (N) میں عناصر کی تعداد کو 2 گنا بڑھا کر، ہم الگورتھم کے چلنے کے وقت کو 2 سے نہیں بلکہ 2^2 = 4 گنا بڑھا دیں گے۔ N کو 10 گنا بڑھا کر، ہم آپریٹنگ ٹائم کو 100 گنا بڑھا دیں گے، وغیرہ۔ اوبنٹو 14.4 پر چلنے والے کور i3 پروسیسر کے ساتھ میرے 2012 کے لیپ ٹاپ پر، مجھے درج ذیل اپ ٹائم ملا:

اندراج کی ترتیب۔ اندراج کی ترتیب

یہاں خیال قدرے مختلف ہے۔ ایک بار پھر، آئیے ڈاکٹر سیڈگوک کی اینیمیشن کی طرف رجوع کریں: آگے کیا ہے اسے ہم نے ابھی تک نہیں دیکھا ہے، اور جو کچھ ہم پیچھے چھوڑتے ہیں وہ ہمیشہ ترتیب میں رہتا ہے۔ نقطہ یہ ہے کہ ہم اصل صف کے ہر نئے عنصر کو شروع میں "واپس" کرتے ہیں جب تک کہ یہ کسی چھوٹے عنصر پر "آرام" نہ کرے۔ اس طرح، ہمارے پاس دوبارہ 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 میں دیکھا کہ اندراج کے لیے الگورتھم میں سب سے مہنگے معاملات اس وقت ہوتے ہیں جب عنصر سرنی کے آغاز تک بہت دور واپس آجاتا ہے: کچھ پاس پر ہم عنصر کو شروع میں واپس کر دیتے ہیں۔ ، اور ایک اور پاس پر شروع تک تقریبا پوری صف سے گزرنا دور اور طویل ہے۔ کیا متعدد عناصر کے ذریعے کودتے ہوئے ایک ساتھ ایسا کرنا ممکن ہے؟ اور اس نے ایسا راستہ تلاش کیا۔ یہ ترتیب وار خاص جزوی قسموں پر مشتمل ہوتا ہے، جسے عام طور پر d-sort کہا جاتا ہے یا Sedgwick کے مطابق h-sort (مجھے شبہ ہے کہ h کا مطلب ہے ہاپ)۔ 3-سانٹ، مثال کے طور پر، سوال میں موجود عنصر کا موازنہ پچھلے والے کے ساتھ نہیں کرے گا، لیکن دو کو چھوڑ کر ایک 3 پوزیشنوں سے پیچھے کا موازنہ کرے گا۔ اگر تبدیل کیا جاتا ہے، تو یہ عنصر 3 پوزیشنز کے ساتھ دوبارہ موازنہ کرے گا اور اسی طرح۔ نچلی بات یہ ہے کہ نتیجے میں آنے والی صف "3-سانٹیڈ" ہوگی، یعنی عناصر کی غلط پوزیشن 3 پوزیشنوں سے کم ہوگی۔ اس اندراج الگورتھم کے ساتھ کام کرنا آسان اور خوشگوار ہوگا۔ ویسے، "1-سانٹ" صرف ایک انسرشن الگورتھم سے زیادہ کچھ نہیں ہے =) h کی قدروں میں کمی کے ساتھ ترتیب وار h-sort لاگو کرنے سے، ہم ایک بڑی صف کو تیزی سے ترتیب دے سکتے ہیں۔ یہاں یہ ہے کہ یہ کیسا لگتا ہے: دیکھیں یہاں چیلنج یہ ہے کہ جزوی قسم کی صحیح ترتیب کا انتخاب کیسے کیا جائے۔ بالآخر، الگورتھم کی کارکردگی اس پر منحصر ہے۔ ڈونالڈ ناتھ کی تجویز کردہ ترتیب سب سے عام ہے: h = h*3 + 1، یعنی 1, 4, 13, 40, ... اور اسی طرح سرنی کے سائز کے 1/3 تک۔ یہ ترتیب اچھی کارکردگی فراہم کرتی ہے اور اس پر عمل درآمد بھی آسان ہے۔ الگورتھم کے تجزیے کے لیے بہت ساری زبان درکار ہے اور یہ میری استطاعت سے باہر ہے۔ تجزیے کی وسعت کا تعین h تسلسل کی بہت سی مختلف حالتوں سے بھی ہوتا ہے۔ تجرباتی طور پر، ہم کہہ سکتے ہیں کہ الگورتھم کی رفتار بہت اچھی ہے - خود ہی دیکھیں: ایک سیکنڈ سے بھی کم وقت میں ایک ملین عناصر! اور یہ جاوا کوڈ ہے نٹ کی ترتیب کے ساتھ۔

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؛) ذیل میں آپ مطالعہ کر سکتے ہیں۔ ڈیٹا ٹیبلز کا استعمال کرتے ہوئے لوگارتھمک پیمانے پر بنایا گیا گراف۔ لائن جتنی چاپلوسی ہوگی، الگورتھم اتنا ہی بہتر ہوگا =) ان لوگوں کے لیے جو پورے پروجیکٹ کو ڈاؤن لوڈ کرنا چاہتے ہیں اور خود ٹیسٹ چلانا چاہتے ہیں، اس لنک کو رکھیں: جاوا اگلے حصے میں ملیں گے! =)