مرتب سازی مقايسه ای و مرتب سازی خطی

صفحه 1:
مرتب سازي مقایسه اي مرتب سازي خطي ساختمان داده ها و الگوریتمها 

صفحه 2:
مرتب سازي مقایسه اي © تاکنون چندین الگوریتم مرتب سازي را بررسي کرده ایم. در همه اين الكوريتمهاة اعضاي آرايه با هم مقايسه مي شوند. اين نوع الكوريتم ها را مقايسه اي مي كوييم. © بهترين زمان اجراي الكوريتمهاي بررسي شده در بدترين حالت» ‎a‏ بسا و بوده است. ‎Quicksont, Dergesont, Weapsort —‏ © آيا مي توان الكوريتمي با زمان كمتر از > دما ح ارائه داد؟ © آيا روش ديكري غير از انواع مختلف الكوريتم هاي مقايسه اي؛ براي مرتب سازي وجود دارد ؟ 

صفحه 3:


صفحه 4:
> (es coe: برگهاي درخت یل( را ارتفاع درخت < بیشترین تعداد مقایسه ها و بدترین حالت الگوریتم 

صفحه 5:
حداقل هزینه مرتب سازي © درخت تصمیم يك الگوریتم مرتب سازي باید حداقل بابرگ داشته باشد تا تمام حالات ممکن ترئیب ب‌عدد را در برگیرد. ‎٩‏ بدترین حالت يك الگوریتم » ارتفاع درخت است. © درخت دوديي به ارتفاع | حداکثر 2 برگ دارد. این تعداد برگ باید تمام ترتیبات مختلف را پوشش دهد. اج ادن و (قضیه لسترلینگک ° ‎ol (we)‏ © (م)0 = ‎k‏ > ات موه ع(وله ) باب < جز و © کمترین زمان اجراي الگوريتمهاي مقایسه اي » بسا ه است. - این نتیجه نا امید کننده است ؟ 

صفحه 6:
و | 1/2۵۵ 9 بو we Of] —O ‏ص لم وخ‎ > we OLPUl] 01 +0 HOU = [fhev = HH Por 4 ‏مس‎ wb Off -0][ + 0۳۳ ۸۵ - Kev Sil ‏بط و و(‎ 1 wh POPE] ۵ APU] —ClPUl] -4 

صفحه 7:


صفحه 8:


صفحه 9:
Por ‏)نم‎ 5 uv ‏حل‎ Cf Pf] —O[P[i] + W/ CfA] = [{kev = AI 

صفحه 10:
Por ‏)نم‎ 5 uv ‏حل‎ Cf Pf] —O[P[i] + W/ CfA] = [{kev = AI 

صفحه 11:
Por ‏)نم‎ 5 uv ‏حل‎ Cf Pf] —O[P[i] + W/ CfA] = [{kev = AI 

صفحه 12:
Por ‏)نم‎ 5 uv ‏حل‎ Cf Pf] —O[P[i] + W/ CfA] = [{kev = AI 

صفحه 13:
Por ‏)نم‎ 5 uv ‏حل‎ Cf Pf] —O[P[i] + W/ CfA] = [{kev = AI 

صفحه 14:
مس مر و ‎we Cf] Off] + 0] 0 > | > ۱‏ 

صفحه 15:
مس مر و ‎we Cf] Off] + 0] 0 > | > ۱‏ 

صفحه 16:
{key <= (| مس مر و ‎we Off] [ + Chi -4[/ 01 <‏ 

صفحه 17:
| [Pk fi] 1 9 | Por j}—o dower (1 wd 0000 06 0-4۱ Oeorewent O[P[] 

صفحه 18:
J ٩۱ 19 8 ‏ا‎ ‎0 ‏إن‎ اا‎ 9 q @ 89 4 © © © 8 ‏ان‎ 5 Por ‏مرو نم‎ ) ‏رف 000۵ حل‎ //Prave Of] Off] —Cl@[] 0 // Decrevect C[O[i] 

صفحه 19:
0 9 3 ‏ان‎ ٩ 3 Por ‏بط تم‎ ) ‏رف 000۵ حل‎ //Prave Of] Off] —Cl@[] 0 // Decrevect C[O[i] 

صفحه 20:
&@ 6 8 8 2ه 8ه @ 6 اه 3 8 ‎a]‏ © ) بط تم ‎Por‏ ‏هس ام ‎bo APU]‏ ]01۵ مه 0-۱ ]0 

صفحه 21:
...boop 6۰ ‏م۳‎ €ee es | 5 ee: q ‏إن‎ 0 9 q 2 e S 4 © © EE 9 we Por ‏مرو نم‎ ) ‏رف 000۵ حل‎ //Prave Of] Off] —Cl@[] 0 // Decrevect C[O[i] 

صفحه 22:
‎Q(h)‏ :سا : © 0 و و (000: 6 مسا ‎cbr COL] LOH] + UI OFA] = [ev = 4}]‏ مس مرجم - ‎Loon 8: O(k)‏ |( ع> | - 01 ‎whee Off] —Of] + Of “ll!‏ ۵ج - (۵)0:) مسر اسب ۰ ۳ - تا ‎ob ASH‏ 4 اه راهن ۶ ۰ +01 تس 

صفحه 23:
‎k = O(a) &‏ 060 ع((ماسصمه۲)6 > ۶ آیا این نتیجه تناقضي با حداقل بدست آمده در بخش اول دارد؟ ‏- توجه کنید: در اين الگوریتم هیچ مقایسه اي صورت نمي كيرد! - ننیجه بدست آمده در بخش اول براي الگوریتم هاي مقایسه اي بود 

صفحه 24:
‎Grobe Goritery‏ مرتب‌سازیپایدار ‎ 

صفحه 25:
‎Wolerik ©‏ مورا در سال990) ۰ پیشنهاد کرد. - این الگوریتم. در محاسبات آماري سال ‎MOOD‏ آمریکا بصورت مكانيكي و الكثريكي پیاده سازي و استفاده شد - نتایج سرشماري دوره قبل (10) سال طول كشيده بود. با استفاده از اين ماشین» گزارشهاي آماري اولیه ظرف ‏ هفته! منتشر شد ‎٩‏ اعداد را رقم به رقم و بصورت پایدار مرتب مي کند ‎٩‏ الگوریتم اولیه از پر ارزشترین رقم شروع مي کند © الگوریتم بهبود یافته از پایین ترین ارزش شروع مي کند 

صفحه 26:
۱ 59 ‏انث الك‎ 9۱ ٩۱ 5 ۴۱ | * ewe 9۱ Quix Gort Gaurvple 

صفحه 27:
«اگر با استفاده از اين الگوریتم» دو عدد تا رقم 0 مرتب شده باشند» با مرتب سازي آنها بر اساس رقم 1 : *درصورتي كه رقم ! دو عدد يكي باشدء خاصيت پايداري سبب حفظ ترتيب فعلي آنها مي شود. در صورتي که اين دو رقم متفاوت باشند» ارزش بالاي رقم؛ ترتيب دو عدد را 0 ‎O| 8‏ © زم زم ‎D ‎ ‎۳9 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 28:
‎٩‏ براي مرتب سازي ب عدد دهدهي(سمحه1 امسنی)) که ارقام آنها از 0 تا ‎٩‏ متغیر است» لازم است به نعداد ارقام اعداد (مثلا 2) فرايند مرتب سازي تکرار شود. ‏© با استفاده از ب«) بجهسصد) بعنوان الگوریتم مرتب سازي ارقامیمسانگی می ثوان دید که فرایند مرب سازري هزیکه اي بززاین ‎O(d * (a +h) )‏ دارد که در آن »| تعداد انواع رقم است(براي اعداد دهدهي « ‎(K=dD‏ ‎٩‏ مي توان اين الگوریتم را طوري تغییر داد که در هر فاز بیش از يك رقم را مورد استفاده قرار دهد 

صفحه 29:
آنالیز الگوریتم» ادامه ‎٩‏ اعداد در کامپیوتر بصورت باينري ذخیره مي شوند و از آنجاکه عملگرهاي مقایسه اي بیتها در سخت افزار بصورت دستورات مرو ‎cond cole‏ هوشمندانه است از ارقام دوديي براي مرتب سازي استفاده شود ‎٩‏ هنگام استفاده از اعداد باينري» معمولا بیش از ) بیت بعنوان يك رقم استفاده مي شود. - اگر اعداد 06 بيتي را با رقم 6 بيتي مرتب کنیم» © بار لازم است ‏فرایند مرتب سازي رو ي ارقام مختلف اجرا شود. ‎Corvette Gort‏ 6 یا 9) عدد مختلف را مرتب مي کند 

صفحه 30:
آنالیز الگوریتم - ادامه ‎SI ©‏ عدد مورد نظر براي مرتب سازي ما بيتي باشند و از ارقام بيتي استفاده کنیم» این اعداد ‎a8) d=b/r‏ خواهند داشت. ‏© آرايه 0 مورد استفاده در مم03 :ج00 بايد “©--! رقم مختلف را مرتب كند. ‏© بنابراين هزينه كل الكوريتم برابر است با: ‎Tab) = O(d * (a th) ) = O((b/-)(wtO")) ‎٩‏ بهترین انتخاب « چیست ؟ 

صفحه 31:
آنالیز الگوریتم - ادامه Mab) = O(d * ‏دم‎ ) = Ol(bé-)(or*)) را دی ریت۳ این تابع ‎rE toy‏ بدست مي ‎r= byt > Doub) = Olle) (otO))= O(bevtrcrs) ©‏ اگر اعداد مورد نظر براي مرتب سازي بین (..0- اب باشند: ‎b =d bor, (a,b) = Och) © 

صفحه 32:
© براي حجم برزرگ آرایه ها» بری‌ولی, كارايي خوبي دارد - براي مرتب سازي (00000© عدد ©© بيتيء اين الكوريتم جهار بار تکرار مي شود اماء ببس و ادب حداقل 10) بار تکرار مي شوند(عمل تقسیم آرایه به آرایه هاي کوچکتر 10 بار صورت مي گیرد) © اضف 09 در هر بار تقسيب ناحیه مرلجعه به حافظه را كوجكتر ميسازد. لينويزكيدر يردازندم هاي‌جدید مجهز بسه حافظه سرب( امتیاز يمحسود‌مي‌شود. از لین‌نظر؛ 6.۵ که خوبطرلحيشده باشدء معمولا هم ارز 7) «۲4) كارليي دارد 

صفحه 33:
© در اینجا فرض کردیم آرایه هاي مورد نظر براي مرتب سازي؛ اعداد صحیح هستند؛ به نظر شما براي مرتب سازي اعداد اعشازي جكونه مي توان .از اين الكوريتمها بهنه كرفت © در كتابء الكوريتم ج3) اص ©) بدين منظور معرفي شده است. اين الكوريتم را مطالعه كنيد و سعي كنيد راه حل ديگري هم براي این مساله پيشنهاد كنيد. © مسايل بخش © را حل كنيد