آرايه ها و مرتب سازی

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

صفحه 2:
۶ آرایه مجموعه اي محدود و معین از عناصر هم نوع است - مثل :,6] 4 ,6,6,6 ‎٩‏ اعضاي آرایه به صورت صریح تعریف مي شوند - آرایه با اعضاي آن به صورت کامل مشخص مي شود - تعاریف رياضي و مفهومي مانند " مجموعه اعدلد اول کوچکتر از 06000" در اینجا استفاده نمي شود © اعمال روي آرايه - ساخت آرایه: شامل لختصاص حافظه به تعداد معين و از نوع معين است: ۴ (100, تمرم سیب( < ۲ یی ‎vy‏ مقدار دهي به آرايه از طريق يك انديس و عملكر []انجام مي كيرد: ‎x{2] =‏ - خواندن مقدار آرایه هم با همین عملگر میسر است: [00]« < بر - جستجو در آرایه و مرتب سازي آن به منظور جستجوي سریعتر» مهمترین اعمال سطح بالاي لرایه هستند 

صفحه 3:
باید تمام اعضاي آرایه را بازبيني کرد. براي آرایه هاي این کار زمان زيادي مي برد ني یک رابطه ترتیب مثل ‎١ > | :‏ *ازرااه ۳ []) <>[]0) بین تمام اعضاي آن برقرار باشد» محدوده جستجوي لازم براي يافتن عضو مورد نظر کوچکتر مي شود عضو () تنها كافي است نیمه اول آرایه [0 5 5 6 5 2 9 00] را انجاه مي كيرد و يس از أن» الفزودن اعضاي جديد به أرليه با ام مي ‎a‏ . الكوريتم ی شده و برنامه نوشته شده باید : - درست باشد. ‎AS a pray gH‏ - با برنامه هاي دیگر بنحو مسالمت آمیز اجرا شود. - پیاده سازي آن راحت باشد. 

صفحه 4:
)(0 [] )سوه لس ‎it D = lech 5‏ 5 2 ۲ )( 220 با سا © دومع 06 ( :4 0 >۲: عم ۳ ۶) < ۵۲۷ (۲ ce ‏د مسا‎ 0 : or 0[ - 0 : co Olk+d] = ew ; ce Phy = 5 0 

صفحه 5:
تکرار هزینه :هزینه کل 0 00-0 +(06 +06 +09 +409 )+ 00 (©00 + 06 + من + مكن + 06 ) (0 ج+ () ط + 006 م 2< 

صفحه 6:
بررسي درستي الگوریتم مرتب سازي white (Phery ==( () 0 دومع ‎Por (ct K=O 5k <M -; k++)‏ ‎F (OW > Ofh+q] (]‏ ‎Pr = 5‏ } V ke [0..N -1] , A[k] >= A[k-1] 

صفحه 7:
ke [0..N -1] , A[k] >= Alk-1] Vo 8: 4Im,n :m<n, Alm] > A[n] then® A[m] > A[n -1] , A[m] > A[n-2] ... A[m] > A[m+1] yo»2ss A[m] > A[m+1] > * الكوريتم درست اجرا مي شود 

صفحه 8:
تكرار هزینه )(0 0 »)سس ‎ved‏ ا طعططا. 6 د 00م ‎ca ۱‏ د يطعم ‎ce 4‏ )( +۱۱ 0۵ >۱: 0 )بط ‎cs 0‏ ( ۳۱۱۱ ‎ofa)‏ > زا )م ‎OF he‏ هه :0 (0) مه ‎CO 0+...‏ ) ) ce 0+ +0 

صفحه 9:
هزینه co 06 cs ce or wan expoori(st [] OY 4D = Dien | Por( 031 <@ p+ bey = Oli] Por(FH; (>= O && Of] > bev i ){ Ord] = OF ; 1 ۵] + = hey; (0)005 - هزينه الكوريتم 

صفحه 10:
00۰ = (۵)ب۲ , 906 (۳0 PO Fd oe 0 SOO 000 © 6000009000000000 ۶ © ۱ ۰ ۵۵۵۵۵۵0۵۵۵0۵0000 بها © ديم بغ < ريخا ,000 ©<0) سو 

صفحه 11:
روشهاي دیگر مرتب سازي Onide word Coagquer ‏استراتژي تقسیم و حل:‎ ٩ ‏مرتب سازي با ادغامرسظ) حسو()‎ - 6 ‏مرتب سازي سریع0‎ - ‏مرتب سازي خطي‎ ٩ 4adex Gort « Countiog Sorts Radic Gort - ‏ساختمان داده هاي ویژه‎ ٩ Weup Gort - ‏اين روشها را به مرور در اين درس مطالعه خواهيم كرد.‎ © 

صفحه 12:
‎٩‏ حل مسائل بزرگ بوسیله تقسیم به مسایل کوچکتر د ‎creatine ay alls atl‏ ‏- حل مسایل کوچك - ادغام پاسخ مسایل کوچك براي بدست آوردن پاسخ مساله اصلي © مثال: ‏- بيدا كردن مينيمم يك آرايه * آرايه را به جند بخش تقسيم كرده و مينيمم هر بخش را بيدا مي كنيم. در انتهاء مينيمم اين مقادير رل بعنوان مينيمم آرايه كزارش مي كنيم. 

صفحه 13:
مرتب سازي به روش تقسیم و حل © ادغام دو آرایه مرتب - الحاق دو آرايه و مرتب سازي آن > هزينه: (©00) © - ادغام دو آرایه با حفظ ترتيب * در آرایه راو ٩)بتنهايي‏ مرتب هستند. به منظور ادغام با حفظ ترتیب: - با افزودن يك عدد بسیار بزرگ انتهاي راو ) را مشخص مي کنیم - در يك حلقه تراري» کوچکترین عضو" فعلي" اين دو را انتخاب و یادداشت مي کنیم. - محل "فعلي" آرایه انتخاب شده را يك واحد افزایش مي دهیم 

صفحه 14:
مرتب سازي با ادغام ۶ آرایه [9 45 6 6 2 9 6]-<) را مرتب کنید - این آرایه را به دو آرایه هم اندازه تقسیم مي کنیم: ۶ ۸20 ,[ ۶ 9 ]دنا - هر كدام از اين دو آرايه را مرتب مي كنيم «[6 © 2006م ,زم 6 ‎L=[e‏ - و در نهایت اين دو را با حفظ ترتیب؛ ادغام مي كنيم: ۱ 

صفحه 15:
۵6۵0۵6) ‏,د‎ ( . Weg-ptd © ‏ولمع‎ ‏[©ه .. 6۵۱۵ اه .. ]نا سوه مه‎ : Por (=O 51< 0 31 ++) Lf] = ‏م01‎ +۱- Por(i =O 51 < 0 i++) Ri] = Oly +i] ‏,]را‎ = = [sO] = 2 ۱2۵, =O Pork = pwr FOE) s 6[ ( ) 0 2 ][ ۱+ [ ‏سا‎ )0][ > 0, ( 9 (ofl + ( +b = O(a) < ‏هزینه لگرریتم‎ ۶ و و و و و د و و و 2 

صفحه 16:
مرتب شده اين آرایه را با رنگ روشن مي كنيم. أرايه هاي كو را مرتب هد ي از اين آرايه ها را كه انتخاب و ادغام ٠ه‏ باشند» با رنك تيره نشان مي دهيم. ان مي دهیم در پایان الگوریتم ادغام» آرایه 8 + 8 نم ماع 

صفحه 17:
۲۲ - [9]ه ج [0إنا > [0]قدماول: قسمتي از آرايه 9)كه با رنك روشن مشخص شدهء مرتب است. [0]0)انتخاب شده وتنك أن قدو شيط ابح 

صفحه 18:
‎RIO] < ۵]00[ = Lia]‏ > []با عم دم ‏آرایه 69 کوچکترین عناصر راو (1) را دارد. تر ‏این عناصر ‎Lf], Qf] eb‏ مشخص مي شود بنابراین بعد از هر تکرار» آرایه 0) کوچکترین. ‏عناصردو آرایه راو 6 را در خود دارد و مرئب است. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏17 16 دی در در در بر هر 1 2 ‎1 ‎© ‎ ‎ ‎ ‎ ‎ ‎ ‎4 ‎517 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 19:
2 REP lel 1 0 7 مر بر هی در در 1 ۳ i @ 2] > fad) = RIE] ماع 8 نم 17 16 در بر در در بر 10 2 12 -| «iP i © 

صفحه 20:
۸ 213 قسمت | ۰ آرایه ‎٩‏ به انتهاي خود رسیده است. عدد هه افزوده شده بهانتهاي آن سبب مي شود تا در تکرار هاي بعدي حلقه ادغام» اعضا باقیمانده آرایه را انتخاب شوند. بنابراین در نهایت و بعد از ار حلقه ادغام به تعداد مجموع طول دو آرا آرایه 68 اعضاي و رارا بصورت مرتب شده خود خواهد داشت. ۱07 ۱ 1 قد ۰۳۳2 1 3 و کر ها در جر 2 5 

صفحه 21:
هزینه 0 0 DOR) MOR) 0)0( ERBE-GORTN(, p, r) 0 dPp<r ‎Lr tre]‏ ومد ‎OERGE-GORN(®, p, a)‏ ‎MERGE-CORN(O, 4 + 4, r)‏ ‎OERCEC(®, p, av)‏ ‎MM) = O() +E N/R) PO ==d> 1) =O) ‎6 ‎9 ‎S 

صفحه 22:
آرایه داده شده طي تقسیمات متوالي به آرایه هايي با يك عضو تبدیل مي شود: دقت کنید: هر آرایه يك عضوي, به خودي خود يك آرایه مرتب است! ‎x 2 4 7 1 3 2 6‏ initial sequence 

صفحه 23:
با استفده از الگوریتم عومیری» این آرایه ها دوتا دوت باهم ادغام مي شوند و أرايه هاي دو عضوي تشكيل مي دهند: 2 5 4 7 1 2 2 6 fd pi fod fed x 2 4 7 1 3 2 6 initial sequence 

صفحه 24:
با استفاده از الگوریتم ‎camer‏ این آرایه ها دوتا دوتا باهم ادغام مي شوند و آرایه هاي چهار عضوي تشکیل مي دهند: 6 3 ۹ 5 0 2 fl wm 1 2 1 3 2 3 35 7 fue, 2 5 4 7 ‎roe‏ هس ‎x 2 4 x ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎initial sequence ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 25:
اكع ا لك ول يست يب ‎a‏ ‏كار كسار ار كار ار يك initial sequence 

صفحه 26:
‎٩‏ درستي الگوریتم - هر آرایه خالي یا نك عضوي» مرتب است. - در قسمت ادغام دیدیم که الگوریتم ادغام عناصر دو آرایه مرتب شده را در يك آرایه مرتب قرار مي دهد. ‎٩‏ هزینه الگوریتم شامل دو بخش حافظه و زمان است - براي مرتب سازي به حافظه كمكي به اندازه آرایه اصلي نیاز داریم. 

صفحه 27:
۶ هزینه ادغام - ادغام دو آرایه مرتب هزینه اي از مرتبه (0)00 دارد. © هزینه کل الگوریتم يك رابطه بازگشتي به شکل زیر است: ‎MW) = ۵)0( + ۵/۳)0/۵(‏ © روشهاي مختلفي براي حل اين رابطه بازگشتي وجود دارد در اینجا تنها به صورت شهودي رابطه اي برحسب ()محاسبه مي کنیم. 000-0 ۶ ... + وس + مس + وج > (00/0ه () ... + ۵00/۵ ‎F‏ + 5۶10/0 + ۶۵ ۶ (0 - وا مت ‎ox‏ + 

صفحه 28:
© در فصل دوم كتاب <01,0850)» مرتب سازي به روش موه" 82 بررسي شده استء اين بخش را مطالعه و با مرتب سازي ارائه شده در اينجا مقايسه كنيد © مسايل ©-) تا ©-© را حل كنيد