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

تعداد صفحات: 14 فرمت فایل: word کد فایل: 6521
سال: 1386 مقطع: مشخص نشده دسته بندی: تحقیق مقاله مهندسی کامپیوتر
قیمت قدیم:۵,۰۰۰ تومان
قیمت: ۲,۹۰۰ تومان
دانلود فایل
  • خلاصه
  • فهرست و منابع
  • خلاصه تحقیق مقاله الگوریتم های مرتب سازی

    مقدمه :

    الگوریتم مرتب سازی، در علوم کامپیوتر و ریاضی، الگوریتمی است که لیستی از داده‌ها را به ترتیبی مشخص می‌چیند.

    پر استفاده‌ترین ترتیب‌ها، ترتیب‌های عددی و لغت‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه سازی الگوریم‌هایی که به لیست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.

    از ابتدای علم کامپیوتر مسائل مرتب‌سازی تحقیقات فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده‌است. برای مثال مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده می‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌شوند (مثلاً مرتب‌سازی کتاب خانه‌ای در سال ۲۰۰۴ مطرح شد).

    مبحث مرتب‌سازی در کلاس‌های معرفی علم کامپیوتر بسیار پر کاربرد است، مبحثی که در آن وجود الگوریتم‌های فراوان به آشنایی با ایده‌های کلی و مراحل طراحی الگوریتم‌های مختلف کمک می‌کند؛ مانند تحلیل الگوریتم، داده‌ ساختار ها، الگوریتم‌ های تصادفی، تحلیل بدترین و بهترین حالت و حالت میانگین، هزینهٔ زمان و حافظه، و حد پایین.

     

    در علم کامپیوتر معمولاً الگوریتم‌های مرتب‌سازی بر اساس این معیارها طبقه‌بندی می‌شوند:

    پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین): با توجه به اندازهٔ لیست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.

    حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتم‌های مرتب‌سازی «در جا[1]» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.

    پایداری[2] : الگوریتم‌ های مرتب‌ سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.

    مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.

    روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.

     

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

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

    (به انگلیسی: Bubble Sort)

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

  • فهرست و منابع تحقیق مقاله الگوریتم های مرتب سازی

    فهرست:

    ندارد.
     

    منبع:

    الگوریتم QuickSort را می‌توان در هر مرجع داده ساختار و الگوریتم یافت. با این وجود مراجع زیر (به خصوص کتاب کناث) برای مطالعات بعدی توصیه می‌شود.

    D.E.Knuth «The Art of Computer Programming» Vol.۲

    Udi Manber , Introduction to Algorithms- A creative Approach

    CLRS , Introduction to Algorithms

    Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function

     

ثبت سفارش
عنوان محصول
قیمت