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

سی شارپ کده

یکشنبه 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 برای الگوریتم های مرتب سازی
دموی اجرای کد ها و حلقه های تودرتوی هر الگوریتم

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


نظرات() 
Buy cialis
پنجشنبه 15 آذر 1397 11:10 ب.ظ

You suggested this exceptionally well.
comprar cialis navarr buy brand cialis cheap cialis herbs rezeptfrei cialis apotheke the best site cialis tablets wow cialis 20 buy cialis online nz cialis generic cialis lowest price cialis generico en mexico
buy cialis germany
پنجشنبه 15 آذر 1397 03:41 ق.ظ

Fantastic material. Kudos!
american pharmacy cialis cialis usa cost overnight cialis tadalafil cialis cuantos mg hay cialis 20 mg cost generic cialis pro best generic drugs cialis usa cialis online purchase once a day cialis generic for cialis
buy cheap cialis no prescription
چهارشنبه 14 آذر 1397 10:22 ق.ظ

Nicely put, Appreciate it!
costo in farmacia cialis cialis uk how do cialis pills work cialis prices in england cialis generic availability cialis 50 mg soft tab cialis 20 mg effectiveness cialis daily reviews purchase once a day cialis cialis australia org
buy cials online
سه شنبه 13 آذر 1397 11:58 ق.ظ

Nicely put, Kudos.
what is cialis free cialis dose size of cialis comprar cialis 10 espa241a cialis kaufen we choice cialis pfizer india cialis online holland we use it cialis online store il cialis quanto costa cialis qualitat
Cialis pills
سه شنبه 13 آذر 1397 12:23 ق.ظ

Thanks a lot. I enjoy this!
cialis pills in singapore can i take cialis and ecstasy generic cialis tadalafil cialis et insomni cialis generico are there generic cialis cialis without a doctor's prescription cilas cialis taglich cialis therapie
Cialis 20 mg
دوشنبه 12 آذر 1397 11:26 ق.ظ

You said this really well.
cialis australian price canada discount drugs cialis cialis 5 mg cialis rezeptfrei sterreich 40 mg cialis what if i take cialis professional from usa india cialis 100mg cost cialis tablets american pharmacy cialis generic cialis pill online
buy cials online
یکشنبه 11 آذر 1397 11:56 ب.ظ

Appreciate it! A good amount of data!

generic cialis levitra cialis preise schweiz acheter du cialis a geneve cialis generika in deutschland kaufen only best offers cialis use cialis 10 doctissimo acheter du cialis a geneve chinese cialis 50 mg cheap cialis cialis 200 dollar savings card
buy cialis with no prescription
یکشنبه 11 آذر 1397 10:49 ق.ظ

You actually reported it effectively!
if a woman takes a mans cialis cialis soft tabs for sale generic cialis tadalafil click here to buy cialis cialis generico en mexico we recommend cialis info cialis generic tadalafil buy we recommend cialis info safe site to buy cialis online wow look it cialis mexico
buy generic cialis pills
یکشنبه 11 آذر 1397 12:01 ق.ظ

Appreciate it, Loads of postings.

5 mg cialis pharmacie en ligne acheter cialis kamagra cialis 5 mg preis cialis 20mg schweiz enter site 20 mg cialis cost we recommend cheapest cialis side effects for cialis buy cialis cheap 10 mg buy cialis sample pack cialis 5mg prix
buy cialis
شنبه 10 آذر 1397 10:46 ق.ظ

Nicely put. Thanks!
comprar cialis navarr cialis qualitat cialis coupon cialis for sale where to buy cialis in ontario low cost cialis 20mg deutschland cialis online cialis for daily use cialis italia gratis viagra vs cialis
buy generic cialis online
جمعه 9 آذر 1397 11:27 ب.ظ

You actually revealed it really well!
wow cialis 20 cialis online napol cialis 20mg the best site cialis tablets tadalafil generic price cialis per pill only here cialis pills cialis 20mg online prescriptions cialis cialis generika
Cialis canada
جمعه 9 آذر 1397 11:43 ق.ظ

Really quite a lot of wonderful data!
cialis from canada online prescriptions cialis tadalafil cialis name brand cheap cialis 100mg suppliers walgreens price for cialis cialis 5mg prix rx cialis para comprar order cialis from india buying cialis on internet
buy tadalafil
جمعه 9 آذر 1397 12:25 ق.ظ

Thanks, Plenty of data.

free cialis female cialis no prescription click now buy cialis brand cialis venta a domicilio cialis price thailand compare prices cialis uk cialis 100 mg 30 tablet calis cialis pills price each deutschland cialis online
Cialis canada
پنجشنبه 8 آذر 1397 01:03 ب.ظ

Amazing a good deal of very good data.
cialis venta a domicilio cialis taglich cialis kaufen wo acquistare cialis internet sublingual cialis online cheap cialis cialis kaufen wo we like it cialis price cialis cuantos mg hay cialis 5mg
Cialis 20 mg
پنجشنبه 8 آذر 1397 12:39 ق.ظ

Very well expressed certainly! .
cialis for sale south africa cialis price in bangalore cheap cialis link for you cialis price only best offers cialis use we recommend cialis best buy cialis qualitat cialis cuantos mg hay only here cialis pills cialis tablets australia
Cialis online
چهارشنبه 7 آذر 1397 12:21 ب.ظ

Nicely put. Regards.
buying cialis overnight we like it cialis price cialis generico en mexico cialis baratos compran uk cialis cipla best buy comprar cialis navarr calis cialis pills price each prezzo di cialis in bulgaria cialis online napol
Cialis generic
چهارشنبه 7 آذر 1397 12:15 ق.ظ

Nicely put. Thanks a lot!
what is cialis acquisto online cialis comprar cialis navarr weblink price cialis cialis prezzo al pubblico cialis without a doctor's prescription canadian drugs generic cialis cialis 20 mg overnight cialis tadalafil acheter cialis meilleur pri
levitra prices
چهارشنبه 18 مهر 1397 10:56 ب.ظ

Appreciate it, Quite a lot of write ups!

vardenafil buy levitra 20 mg generic levitra levitra 20 mg bayer prezzo vardenafil 20mg levitra 10 mg kopen vardenafil 20mg levitra 10 mg kopen levitra generic levitra 20 mg
buy cheap cialis coupon
دوشنبه 9 مهر 1397 11:19 ب.ظ

You actually reported it really well!
cialis 5mg billiger cialis online cialis prezzo al pubblico wow cialis 20 5 mg cialis pharmacie en ligne cialis dosage recommendations dose size of cialis cialis generic tadalafil buy how much does a cialis cost tadalafil tablets
Cialis 20 mg
شنبه 7 مهر 1397 09:44 ب.ظ

Whoa all kinds of great data.
cialis in sconto cialis online nederland cialis 5mg prix if a woman takes a mans cialis cialis coupons printable venta de cialis canada weblink price cialis cialis tadalafil cialis name brand cheap buy cialis
http://buycialisonla.com/
شنبه 7 مهر 1397 06:14 ب.ظ

Well spoken indeed. .
sublingual cialis online enter site natural cialis side effects for cialis viagra vs cialis vs levitra cialis alternative cialis online generic cialis 20mg uk cialis professional from usa cialis for sale we use it 50 mg cialis dose
Online cialis
جمعه 6 مهر 1397 05:50 ب.ظ

This is nicely put! .
venta de cialis canada how does cialis work female cialis no prescription price cialis best order cialis from india only here cialis pills cialis free trial cialis pills cialis for sale buying brand cialis online
http://cialisvipsale.com/
چهارشنبه 28 شهریور 1397 03:32 ب.ظ

Excellent facts. Regards!
cialis kaufen bankberweisung viagra vs cialis buy online cialis 5mg pastillas cialis y alcoho cialis 5mg viagra or cialis effetti del cialis safe dosage for cialis calis cialis for bph
viagraessale.com
جمعه 23 شهریور 1397 05:19 ب.ظ

Thank you. Numerous data!

cialis en mexico precio cialis billig cialis uk cialis generika in deutschland kaufen side effects for cialis comprar cialis navarr we like it cialis soft gel cialis tablets cialis qualitat buy cialis sample pack
buycialisky.com
چهارشنبه 14 شهریور 1397 11:59 ب.ظ

Thanks! I like it!
cialis from canada click here take cialis cialis prices cialis prezzo al pubblico tadalafil 20mg female cialis no prescription cialis prices in england tadalafil 5mg trusted tabled cialis softabs buy cialis online nz
Online viagra
سه شنبه 13 شهریور 1397 02:03 ق.ظ

Amazing write ups. Cheers!
buy viagra mastercard order viagra online without a prescription buying real viagra online sildenafil prescription buy viagra online with a prescription buy legal viagra uk viagra prices safe place to buy viagra online uk how to order viagra pills how to buy viagra uk
Buy generic cialis
دوشنبه 12 شهریور 1397 06:27 ب.ظ

Useful knowledge. Many thanks.
cialis generic availability we like it safe cheap cialis cialis generika in deutschland kaufen cialis 20mg preis cf how to buy cialis online usa tarif cialis france wow cialis tadalafil 100mg non 5 mg cialis generici cialis 5 mg schweiz only now cialis 20 mg
cialisky.com
یکشنبه 11 شهریور 1397 11:53 ب.ظ

Terrific tips. With thanks.
cialis 10mg prix pharmaci prezzo cialis a buon mercato cialis cost cialis generisches kanada click here take cialis cialis professional yohimbe buy cialis online cialis dosage amounts cialis generico en mexico cost of cialis per pill
http://viagraessale.com/
یکشنبه 11 شهریور 1397 11:21 ق.ظ

Amazing many of amazing facts.
prix cialis once a da i recommend cialis generico rezeptfrei cialis apotheke cialis 5 mg generic cialis 20mg tablets cialis authentique suisse american pharmacy cialis generic for cialis cialis canada on line click here take cialis
viabiovit.com/vergelijk-drug-store-recept-prijzen.html
سه شنبه 23 مرداد 1397 02:24 ق.ظ

Fantastic info. Regards.
price of viagra uk viagra order online how to get viagra prescription can you purchase viagra online buy viagra usa online viagra pharmacy viagra online pharmacy viagra ordering viagra online order viagra online usa getting viagra online where can you buy viagra uk
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر
نمایش نظرات 1 تا 30

آمار وبلاگ

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