تبلیغات
سی شارپ کده - الگوریتم های مرتب سازی

سی شارپ کده

یکشنبه 20 شهریور 1390

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

نویسنده: حمیدرضا مهدوی پناه   طبقه بندی: نکته های آموزشی، 


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



الگوریتم مرتب سازی انتخابی (Selection Sort ): در این روش، برنامه کوچکترین مقدار را یافته و آنرا در اولین خانه ی آرایه قرار می دهد. حال که کوچکترین عضو یافت شده است، برنامه به سراغ یافتن دومین عنصر کوچک در میان اعداد باقی مانده که از 2 تا n هستند می رود و دومین عدد کوچک را در خانه دوم قرار میدهد. حال به سراغ سومین عدد کوچک می رود و این رویه را تا یافتن آخر عدد و قرار دادن آن در جای خودش تکرار میکند. با توجه به اینکه برنامه باید n عدد را n بار با هم مقایسه کند مرتبه ی پیچیدگی این الگوریتم O (n2)است.

مرتب سازی حبابی (Bubble Sort ): در این روش هر عنصر با عنصر بعدی اش مقایسه میشود. در صورتی که عنصر دومی کوچکتر از عنصر اولی باشد، جای دو عنصر با هم عوض میشود. برنامه به کارش ادامه میدهد و عناصر دوم و سوم را با هم مقایسه میکند و این کار را تا اخر آرایه ادامه میدهد. دوباره الگوریتم ، پویش را از اول آرایه شروع میکند و مراحل قبل را تکرار میکند و این مراحل آنقدر تکرار میشوند تا آرایه کاملا مرتب شده باشد. مرتبه ی پیچیدگی این الگوریتم O(n2) است.

مرتب سازی درجی (Insertion Sort ): در این روش عنصر اول و دوم با هم مقایسه شده و در صورت نیاز مرتب میشوند و سپس سومین عنصر با عناصر اول و دوم مقایسه میشود. در صورتی که عنصر سوم از اولی کوچکتر باشد به جای اولین عنصر می نشیند و عناصر قبلی به سمت راست هل داده میشوند. اگر عنصر سوم از اولی بزرگتر و از دومی کوچکتر باشد، بین آنها درج میشود و عنصر دوم به بعد یکی به سمت راست هل داده میشود. (پس در این روش همیشه عناصر ِ قبل از عنصری که میخواهیم مرتبش کنیم، مرتب هشتند.) این روال برای بقیه عناصر نیز اجرا میشود و هر عنصر در جای خودش قرار می گیرد تا تمام عناصر مرتب شوند. مرتبه ی پیچیدگی این الگوریتم O (n2) است.

مرتب سازی سریع(Quick Sort ) : در این الگوریتم یک عنصر را بعنوان محور (pilot ) مرتب سازی انتخاب میکنیم. و تمام عناصر کوچکتر از آن را به سمت چپ آن برده و عناصر بزرگتر را به سمت راست اش می‌بریم. حالا بخش چپ خودش یک بخش جدید است که با الگوریتمی که گفتیم آنرا مرتب میکنیم و سمت راست را نیز همینطور. یعنی در سمت چپی ها دوباره یک عنصر را بعنوان pilot در نظر میگیریم و عناصر کوچکتر از pilot را به سمت چپ آن و عناصر بزرگتر از pilot این قسمت را ، به سمت راست pilot می بریم. دوباره الگوریتم را روی یک چهارم های به وجود آمده اجرا میکنیم و اینکار را آنقدر ادامه میدهیم تا کل آرایه مرتب شود. مرتبه پیچیدگی این الگوریتم در بدترین حالت O (n2) است. اما در حال نرمال O (n log n) است که کمترین مرتبه پیچیدگی برای مرتب سازی اعداد به حساب می آید.

مرتب سازی ادغام (Merge Sort ): این الگوریتم به روش بازگشتی (Recursive ) عمل میکند و آرایه را به چند آرایه ی دو عنصری تقسیم میکند و آنها را مرتب میکند. سپس آرایه های کوچک را دوبه‌دو با هم ادغام میکند تا آرایه های مرتب 4 عنصری ایجاد شوند و بعد آرایه های 8 عنصری و به همین ترتیب پیش می رود تا آرایه اصلی بصورت مرتب شده ظاهر شود. مرتبه پیچیدگی این الگوریتم O(n log n) است.

مرتب سازی هرمی (Heap Sort ): در این روش، برنامه از کل آرایه ی داده شده یک درخت MaxHeap می سازد. (درخت مکس هیپ درختی دودویی و کامل است که مقدار ذخیره شده در هر گره ، بزرگتر و یا مساوی مقدار ذخیره شده در گره فرزندانش است) سپس مقدار ماگزیمم را از درخت حذف میکند و آنرا در انتهای آرایه میگذارد و دوباره از بقیه اعداد یک درخت maxHeap میسازد و باز روش مذکور را روی آن نیز اعمال میکند تا دومین عدد بزرگ یافت شود. در این روش آرایه از آخر به اول مرتب میشود. مرتبه پیچیدگی این الگوریتم O (n log n)است.

 روش هایی وجود دارند که حداقل مرتبه ی پیچیدگی هر الگوریتم را با روابطی اثبات میکنند. بطور مثال برای الگوریتم های مرتب سازی ، میزان O (n Log n) حداقل است و کمتر از این میزان ممکن نیست و همانطور که میدانیم الگوریتم های ادغام و هرمی و سریع هر سه با همین میزان پیچیدگی مرتب سازی را انجام میدهند. بنابراین الگوریتمی نمیتوان نوشت که سریعتر از این حالت عمل کند و الگوریتم های مینیمم پیچیدگی در این زمینه ،قبلا کشف و ایجاد شده اند . اما مواردی هستند مانند ضرب دو ماتریس n در n که مرتبه ی پیچیدگی شانO(n3) است و روش های جدیدی مانند روش استراسن آنرا به O(n2.81) کاهش داده است. طبق روشهای اثبات شده امکان کمتر شدن این میزان وجود دارد. اما هنوز الگوریتمی که هزینه ی پیچیدگی کمتری از الگوریتم استراسن داشته باشد کشف نشده است. بنابراین هنوز شما میتوانید وقت خود را روی کاهش مرتبه ی پیچیدگی این الگوریتم و یافتن الگوریتم بهینه تر بگذارید.
الگوریتم های شبیه سازی در ویکی پدیا 
شبیه سازی و مقایسه الگوریتم ها در کنار هم در حالات مختلف 
شبیه سازی مرتب سازی های مختلف (توسط اپلت جاوا)
دموی دوم از الگوریتم های مرتب سازی (برای شروع به کار الگوریتم ها رویشان کلیک کنید.)
سورس کد زبان C برای الگوریتم های مرتب سازی
دموی اجرای کد ها و حلقه های تودرتوی هر الگوریتم

منبع:فرین سافت


نظرات() 
How we can increase our height?
دوشنبه 27 شهریور 1396 05:24 ق.ظ
What's up to all, the contents existing at this web page are really awesome
for people experience, well, keep up the nice work fellows.
What do you do for Achilles tendonitis?
سه شنبه 10 مرداد 1396 05:59 ق.ظ
Way cool! Some extremely valid points! I appreciate you writing this post and the rest of the site is
also really good.
manicure
یکشنبه 3 اردیبهشت 1396 02:55 ق.ظ
I do not even know the way I ended up right
here, however I believed this publish used to be great.
I do not understand who you're but certainly you are going
to a famous blogger for those who aren't already.
Cheers!
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر

آمار وبلاگ

  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :