اثر پروانه ای

برنامه نویسی حرفه ای کامپیوتر به زبان سی شارپ - لیست کامل کلمات کلیدی در ʚĭɞ - ßữʈʨɾflỵ ⓔⓕⓕⓔⓒⓣ

مشخصات بلاگ
اثر پروانه ای

اثر پروانه‌ای نام پدیده‌ای است که به دلیل حساسیت سیستم‌های آشوب‌ناک به شرایط اولیه ایجاد می‌شود. این پدیده به این اشاره می‌کند که تغییری کوچک در یک سیستم آشوب‌ناک چون جو سیارهٔ زمین (مثلاً بال‌زدن پروانه) می‌تواند باعث تغییرات شدید (وقوع توفان در کشوری دیگر) در آینده شود.

ایده‌ٔ این‌که پروانه‌ای می‌تواند باعث تغییری آشوبی شود نخستین بار در ۱۹۵۲ در داستان کوتاهی به نام آوای تندر اثر ری بردبری مطرح شد. عبارت «اثر پروانه ای» هم در ۱۹۶۱ در پی مقاله‌ای از ادوارد لورنتس به وجود آمد. وی در صد و سی و نهمین اجلاس ای‌ای‌ای‌اس در سال ۱۹۷۲ مقاله‌ای با این عنوان ارائه داد که «آیا بال‌زدن پروانه‌ای در برزیل می‌تواند باعث ایجاد تندباد در تکزاس شود؟»

آخرین نظرات
  • ۱۱ بهمن ۹۵، ۱۷:۱۸ - فاروق کریمی زاده
    خوب بود.
اثر پروانه ای

مقایسه تصویری انواع الگوریتم های مرتب‌سازی

پنجشنبه, ۱۲ تیر ۱۳۹۳، ۰۱:۴۶ ب.ظ

مقدمه

به نظرم اولین و مهمترین چیزی که باید بفهمیم اینه که اصلا الگوریتم های مرتب سازی چه هستند. بر اساس ویکی‌پدیا، الگوریتم مرتب سازی، الگوریتمی است که عناصر یک لیست را به ترتیب خاصی در می‌آورد. کاربردی‌ترین ترتیب ها، ترتیب‌های عددی و ترتیب‌های وابسه به حروف هستند. بعضی از الگوریتم‌ها (از جمله الگوریتم‌های جستجو و ادغام) برای اینکه بدرستی کار کنند، نیازمند لیست‌های مرتب شده می باشند؛ مرتب‌سازی مؤثر و کارآمد، برای بهینه سازی کارائی چنین الگوریتم‌هایی، مهم هستند. این اگوریتم‌ها، اغلب اوقات، برای به نظم در آوردن داده‌ها و تولید خروجی قابل خواندن برای انسان، مفید هستند.

من، در این مقاله، برخی از الگوریتم‌های مرتب‌سازی را شرح خواهم داد. همه الگوریتم هایی که در اینجا مورد بحث قرار گرفته اند، در زبان برنامه نویسی #C نوشته شده‌اند و بسیاری از ایده‌ها، بر اساس الگوریتم‌هایی است که شما می‌توانید در ویکی‌پدیا پیدا کنید.


الگوریتم‌هایی که در این مقاله با آنها آشنا خواهید شد:

  • مرتب سازی حبابی دوطرفه (Bidirectional Bubble Sort)
  • مرتب سازی حبابی (Bubble Sort)
  • مرتب سازی سطلی (Bucket Sort)
  • مرتب سازی شانه ای (Comb Sort)
  • مرتب سازی چرخه‌ای (Cycle Sort)
  • مرتب سازی گورزاد (Gnome Sort)
  • مرتب سازی هرمی (Heap Sort)
  • مرتب سازی درجی (Insertion Sort)
  • مرتب سازی ادغامی (Merge Sort)
  • مرتب سازی زوج-فرد (Odd-Even Sort)
  • مرتب سازی لانه کبوتری (Pigeonhole Sort)
  • مرتب سازی سریع (Quick Sort)
  • مرتب سازی سریع با استفاده از مرتب سازی حبابی (Quick Sort with Bubble Sort)
  • مرتب سازی انتخابی (Selection Sort)
  • مرتب سازی شل یا پوسته ای (Shell Sort)

قصد دارم طرز کار این الگوریتم ها رو بصورت دیداری به شما نشان بدهم. کاربر می تواند، خروجی این پروژه را بصورت تصاویر متحرک GIF، با سرعت دلخواه، ذخیره کند.

طرز استفاده از برنامه

این Solution حاوی 2 پروژه است. پروژه اول (Components) ، برای ساختن تصاویر متحرک GIF ، کلاس هایی را ارائه می‌دهد. این پروژه بر اساس پروژه NGIF است. برای اطلاعات بیشتر در مورد این پروژه، به NGIF مراجعه کنید.

پروژه دوم (SortComparison) بخش اصلی Solution است. شما می‌توانید، در فرمی بنام frmMain ، نوع الگوریتم مرتب‌سازی، تعداد نمونه‌هایی که می‌خواهید مرتب کنید، سرعت مرتب‌سازی و اینکه آیا می‌خواهید یک فایل GIF متحرک بسازید را مشخص کنید. روی فرم، 2 پنل به نام‌های pnlSort1 و pnlSort2 وجود دارد که عملیات مرتب‌سازی را بصورت تصویری به نمایش در می‌آورند.

هر الگوریتم، نام مربوط به خود را دارد؛ این نام بر اساس نام الگوریتم مرتب‌سازی مربوطه انتخاب شده و یک پارامتر IList دریافت کرده و یک شیئ IList را برمیگرداند.

متد DrawSamples همه نمونه‌ها را روی پنل رسم می‌کند. این متد زمانی فراخوانی می‌شود که به تعداد کافی، نمونه‌های تصادفی تولید شده باشد. با کلیک بر روی دکمه Shuffle ، می‌توانید نمونه‌های تصادفی تولید کنید. نمونه‌ها در داخل متغیر array ذخیره خواهند شد.

private void DrawSamples()
{
    g.Clear(Color.White);
            
    for (int i = 0; i < array.Count; i++)
    {
        int x = (int)(((double)pnlSamples.Width / array.Count) * i);
                
        Pen pen = new Pen(Color.Black);
        g.DrawLine(pen, new Point(x, pnlSamples.Height), 
          new Point(x, (int)(pnlSamples.Height - (int)array[i])));
    }
}

متد Randomize ، همه نمونه‌ها را بصورت تصادفی و شانسی در متغیر array قرار می‌دهد.

public void Randomize(IList list)
{
    for (int i = list.Count - 1; i > 0; i--)
    {
        int swapIndex = rng.Next(i + 1);
        if (swapIndex != i)
        {
            object tmp = list[swapIndex];
            list[swapIndex] = list[i];
            list[i] = tmp;
        }
    }
}

در حین عمل مرتب‌سازی، وقتی چک‌باکس Create animation تیک خورده باشد، بعد از هر جابجایی در عناصر آرایۀ نمونه‌ها، تصاویر متناظر آن، تولید می‌شود. این تصاویر از 0 تا n شاخص‌گذاری شده‌اند، که n نشان‌دهنده تعداد جابجایی‌های فعلی می‌باشد.

private void SavePicture()
{
    ImageCodecInfo myImageCodecInfo = this.getEncoderInfo("image/gif"); 
    EncoderParameter myEncoderParameter = new EncoderParameter(
      System.Drawing.Imaging.Encoder.Compression, (long)EncoderValue.CompressionLZW);
    EncoderParameter qualityParam = 
      new EncoderParameter(System.Drawing.Imaging.Encoder.Quality, 0L);
    EncoderParameters myEncoderParameters = new EncoderParameters(1);

    EncoderParameters encoderParams = new EncoderParameters(2);
    encoderParams.Param[0] = qualityParam;
    encoderParams.Param[1] = myEncoderParameter;

    string destPath = 
      System.IO.Path.Combine(txtOutputFolder.Text, imgCount + ".gif");
    bmpsave.Save(destPath, myImageCodecInfo, encoderParams);
    imgCount++;
}

الگوریتم‌های مرتب‌سازی

مرتب‌سازی حبابی

Bubble Sort مرتب سازی حبابی یا غرقی

مرتب‌سازی حبابی (Bubble Sort) یا مرتب‌سازی غرقی (Sinking Sort)، یک الگوریتم مرتب‌سازی ساده است. این الگوریتم برای مرتب کردن لیست، مکررا لیست را پیمایش می‌کند و هر جفت‌ از عناصر مجاور هم را مقایسه کرده و در صورتی که در مکان اشتباه قرار گرفته باشند، آنها را جابجا می‌کند. این گذر کردن از لیست، تا زمانی که عناصر لیست نیاز به هیچ جابجایی نداشته باشند (که نشان دهنده مرتب شدن لیست است) ، ادامه پیدا می‌کند. این الگوریتم، نام خود را از اینجا بدست آورده که، عناصر کوچکتر، مانند "حباب" به سمت بالای لیست، حرکت می‌کنند. [و عناصر بزرگتر، مانند "غرق" شدن سنگ، به سمت پایین لیست حرکت می‌کنند]. این الگوریتم برای انجام عملیات روی عناصر لیست، فقط از "مقایسه" استفاده می‌کند، به همین علت، یک الگوریتم مقایسه‌ای است. مرتب‌سازی درجی که به سادگی مرتب‌سازی حبابی است، از کارایی بهتری نسبت به مرتب‌سازی حبابی برخوردار است، بنابراین برخی افراد پیشنهاد می‌کنند که دیگر الگوریتم مرتب‌سازی حبابی، آموزش داده نشود.

public IList BubbleSort(IList arrayToSort)
{
    int n = arrayToSort.Count - 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = n; j > i; j--)
        {
            if (((IComparable)arrayToSort[j - 1]).CompareTo(arrayToSort[j]) > 0)
            {
                object temp = arrayToSort[j - 1];
                arrayToSort[j - 1] = arrayToSort[j];
                arrayToSort[j] = temp;
                RedrawItem(j);
                RedrawItem(j - 1);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
            }
        }
    }
    return arrayToSort;
}

بدترین حالت کارایی: O(n2)
بهترین حالت کارایی: O(n)
کارایی در حالت میانگین: O(n2)
پیچیدگی حافظه در بدترین حالت: کمکی O(1)

مرتب‌سازی حبابی دوطرفه (Bidirectional Bubble Sort)
مرتب سازی حبابی دوطرفه Bidirectional Bubble Sort

مرتب‌سازی Cocktail که با نام مرتب‌سازی حبابی دوطرفه نیز شناخته شده است؛ مرتب‌سازی Cocktail Shaker، مرتب‌سازی Shaker (که به یکی از انواع مرتب‌سازی انتخابی اشاره دارد)، مرتب‌سازی موجی (Ripple)، مرتب‌سازی رفت و برگشتی (Shttle sort)، یا مرتب‌سازی Happy Hour (اینا همه شون اسم های دیگر مرتب‌سازی حبابی دوطرفه هستند)، یک نوع از مرتب‌سازی حبابی است که هم یک الگوریتم پایدار است و هم یک مرتب‌سازی مقایسه‌ای است. این الگوریتم، با مرتب‌سازی حبابی تفاوت دارد، از این جهت که در هر گذر از لیست، مرتب‌سازی را در دو طرف لیست، انجام می‌دهد. پیاده‌سازی این الگوریتم، اندکی از مرتب‌سازی حبابی سخت‌تر است، و مسأله را با همان سرعت الگوریتم مرتب‌سازی حبابی، حل می‌کند.

اولین گذر به سمت راست، بزرگترین عنصر لیست را به مکان صحیح خود (انتهای لیست)، انتقال می‌دهد و گذر سمت چپ، کوچکترین عنصر لیست را به مکان صحیح خود در ابتدای لیست، منتقل خواهد کرد. دومین گذر کامل، در این الگوریتم، کوچکترین عنصر دوم و بزرگترین عنصر دوم را به مکان صحیح خودشان منتقل خواهد کرد و همینطور الی آخر. بعد از i مین گذر، i عنصر اول و i عنصر آخر لیست، در مکان صحیح خودشان قرار می گیرند و نیازی به بررسی کردن هم نیست. با کوتاه‌سازی قسمتی از لیست که هر دفعه مرتب می‌شود، تعداد عملیات مربوط به مرتب‌سازی می‌تواند نصف شود.

public IList BiDerectionalBubleSort(IList arrayToSort) 
{
    int limit = arrayToSort.Count;
    int st = -1;
    bool swapped = false;
    do
    {
        swapped = false;
        st++;
        limit--;
                
        for (int j = st; j < limit; j++)
        {
            if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
            {
                object temp = arrayToSort[j];
                arrayToSort[j] = arrayToSort[j + 1];
                arrayToSort[j + 1] = temp;
                swapped = true;
                RedrawItem(j);
                RedrawItem(j + 1);
                pnlSamples.Refresh();
                if(chkCreateAnimation.Checked)
                    SavePicture();

            }
        }
        for (int j = limit - 1; j >= st; j--)
        {
            if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[j + 1]) > 0)
            {
                object temp = arrayToSort[j];
                arrayToSort[j] = arrayToSort[j + 1];
                arrayToSort[j + 1] = temp;
                swapped = true;
                RedrawItem(j);
                RedrawItem(j + 1);
                        
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();

            }
        }

    } while (st < limit && swapped);

    return arrayToSort;
}

بدترین حالت کارایی: O(n2)
بهترین حالت کارایی: O(n)
کارایی در حالت میانگین: O(n2)
پیچیدگی حافظه در بدترین حالت: کمکی O(1)

مرتب‌سازی سطلی (Bucket Sort)

مرتب‌سازی سطلی یا bin sort ، یک الگوریتم مرتب سازی است که با افراز آرایه به تعدادی سطل، کار می‌کند. نهایتا هر سطل بصورت جداگانه مرتب‌سازی خواهد شد. روش مرتب‌سازی سطل ها می‌تواند با استفاده از الگوریتم‌های مرتب‌سازی دیگر باشد و یا اینکه بصورت بازگشتی، الگوریتم مرتب‌سازی سطلی را اعمال کنیم. این یک مرتب‌سازی توزیع شده، بوده و پسرعموی مرتب‌سازی Radix در اعداد بزرگتر به کوچکتر است. مرتب‌سازی سطلی، تعمیم یافتۀ مرتب‌سازی لانه کبوتری است. از آنجا که مرتب‌سازی سطلی، از نوع مرتب‌سازی مقایسه‌ای نیست، حد پایین (O(n log n غیرقابل تطبیق است. تخمین‌های پیچیدگی محاسباتی با تعداد سطل‌ها در ارتباط است.

مرتب‌سازی سطلی، بصورت زیر کار می‌کند:

  • تنظیم آرایه‌ای از سطل‌ها (سطل‌ها در ابتدا خالی هستند)
  • پراکندن: رفتن به آرایه اصلی، و قرار دادن هر شیئ در سطل خودش.
  • مرتب‌سازی هر سطل غیر-خالی
  • جمع‌آوری: ملاقات منظم سطل‌ها و قرار دادن همه عناصر در آرایه اصلی
public IList BucketSort(IList arrayToSort)
{
    if (arrayToSort == null || arrayToSort.Count == 0) return arrayToSort;

    object max = arrayToSort[0];
    object min = arrayToSort[0];


    for (int i = 0; i < arrayToSort.Count; i++)
    {

        if (((IComparable)arrayToSort[i]).CompareTo(max) > 0)
        {
            max = arrayToSort[i];
        }

        if (((IComparable)arrayToSort[i]).CompareTo(min) < 0)
        {
            min = arrayToSort[i];
        }
    }
    ArrayList[] holder = new ArrayList[(int)max - (int)min + 1];

    for (int i = 0; i < holder.Length; i++)
    {
        holder[i] = new ArrayList();
    }

    for (int i = 0; i < arrayToSort.Count; i++)
    {
        holder[(int)arrayToSort[i] - (int)min].Add(arrayToSort[i]);
    }

    int k = 0;

    for (int i = 0; i < holder.Length; i++)
    {
        if (holder[i].Count > 0)
        {
            for (int j = 0; j < holder[i].Count; j++)
            {
                arrayToSort[k] = holder[i][j];
                RedrawItem(k);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
                k++;
            }
        }
    }

    return arrayToSort;
}

بدترین حالت کارایی: O(n2.k)
بهترین حالت کارایی: -
کارایی در حالت میانگین: O(n.k)
پیچیدگی حافظه در بدترین حالت: O(n.k)

مرتب‌سازی شانه‌ای (Comb Sort)
مرتب سازی شانه ای Comb sort


این مقاله درحال کامل شدن هست...

نظرات  (۶)

یعنی خدایی دمت گرم بابا چقد حوصله داری تو اخه


ایووووووووووووووووووووووووووووووووووووول

مرررررررررررررررررررررررررررررررررررررررررررررسی عالی بود

قربانت الینا
  • فاروق کریمی زاده
  • کد سی و سی پلاس پلاس و سی شارپ اضافه شد
  • فاروق کریمی زاده
  • جدای از شوخی الگوریتم مرتب سازی حبابی با وجود ساده بودنش نسبت به بقیه الگوریتم ها کند تر عمل میکنه.شما این کندی رو نمیبینید مگر زمانی که یک مجموعه بزرگ را بخواهید مرتب کنید.
    کد مرتب سازی به زبان های سی پلاس پلاس و پایتون و سی شارپ و شاید اسمبلی در مطلب الگوریتم مرتب سازی حبابی در وبلاگم قرار دارد:
    اینجا
     یاد آوری کنم در زمان نوشتن این نظر مطلب مورد نظر هنوز کامل نشده است.
    در ضمن من دیگه با سی شارپ کار نمیکنم!
    به اوبونتو مهاجرت کردم.
    پاسخ:
    حیف سی شارپ نبود؟! عایا؟ :)
  • فاروق کریمی زاده
  • به نظرم مرتب سازی حبابی اصلا جالب نیست هر چند که آسونه.
    من کتابخونه ای که داخل اتاقم بود رو خواستم باهاش مرتب کنم.پدرم در اومد! بنظرم اگر از مرتب سازی انتخابی استفاده میکردم خیلی بهتر و سریع تر بود.
    یکسری از شما برنامه نویس ها به فکر کامپیوتر بیچاره نیستید که چقدر باید جون بکنه! فقط به فکر این هستید که سریع تر و راحت تر کدتون رو بنویسید!!!
    پاسخ:
    درست می فرمایید. اما کامپیوتر فقط یک ماشین ساخته دست بشر هست که هیچ احساسی هم نداره. باید به فکر برنامه نویس بیچاره باشیم که پدرش در میاد تا بخواد کد بنویسه :)

    اگه ممکنه یه سری امزش الگوریتم و فلوچارت قرار بدید

    مشتری زیاد داره بخصوص بچه های ترم 1

    پاسخ:
    چشم...
    بزودی آموزش الگوریتم و فلوچارت رو هم می نویسم

    یاعلی
  • سید حسین نسابه
  • سلام استاد حسینی.
    متشکرم به خاطر این مطلب کاربردی  

    1+



    .
    .
    .
    در آخر توضیح هر الگوریتم ، یه چیزایی نوشتید به این عنوان
     " بدترین حالت کارایی - بهترین حالت کارایی  ..... "
    بعدش یه حرف O ، دوتاپرانتز با یه سری چیزا بین اون دو تا پرانتز آوردید . 
    میشه یه خورده درمورد اینا توضیح بدید ؟ قضیه این (...)O چیه ؟ توی بعضی از سوالات مسابقات برنامه نویسی هم دیدم.

                                             با تشکر
    پاسخ:
    سلام آقای نسابه عزیز
    اون حرف O بزرگ (Big O notation) برای نشون دادن پیچیدگی الگوریتم استفاده میشه. منظور از پیچیدگی الگوریتم اینه که برای n داده ورودی به الگوریتم، چه تعداد دستورالعمل اجرایی نیاز است، تا آن الگوریتم به پایان برسد. اما روش شمارش این دستورالعمل های اجرایی، بصورت کاملا دقیق نیست؛ مثلا برای بدست آوردن O الگوریتم، تک تک دستورات رو شمارش نمی کنند، بلکه دستوراتی را شمارش می کنند که با افزوده شدن مقدار n (تعداد ورودی‌ها) باعث افزایش تعداد دستورالعمل های اجرایی الگوریتم می شوند.
    البته محاسبه O یک الگوریتم ظرافت های دیگه ای هم داره که باید با مثال های مختلف توضیح داده بشه و نمیشه همۀ آنها رو در پاسخ نظرات آورد. اما من قول میدم به زودی مطلب خوب و کاملی رو در همین زمینه توی وبلاگ قرار بدم.
    با تشکر از نظر ارزشمند شما.

    موفق باشید
    یاعلی

    ارسال نظر

    لطفا اگر می خواهید در بخش نظرات، کد برنامه مورد نظر خود را بنویسید، قسمت زیر (Program Code) را کپی کرده، و در کادر "پیام" ، paste کنید. سپس برنامه مورد نظر خود را در کادری که ایجاد می شود، وارد کنید.

    • کلید میانبر برای Copy کردن: Ctrl+C

    • کلید میانبر برای paste کردن: Ctrl+V

    //Program Code

    از همکاری شما کمال تشکر را دارم.

    ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
    شما میتوانید از این تگهای html استفاده کنید:
    <b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
    تجدید کد امنیتی