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

صفحه 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 بررسي شده استء اين بخش را مطالعه و با مرتب سازي ارائه شده در اينجا مقايسه كنيد © مسايل ©-) تا ©-© را حل كنيد 

آرايه ها و مرتب سازي ساختمان داده ها و الگوريتمها آرايه ‏ آرايه مجموعه اي محدود و معين از عناصر هم نوع است – ‏ اعضاي آرايه به صورت صريح تعريف مي شوند – – ‏ مثال 2,3,4, 1[ ]5,: آرايه با اعضاي آن به صورت کامل مشخص مي شود تعاريف رياضي و مفهومي مانند “ مجموعه اعدا6د اول کوچکتر از ”100در اينجا استفاده نمي شود اعمال روي آرايه – ساخت آرايه :شامل ا6ختصاص حافظه به تعداد معين و از نوع معين است: ;X = Create_Array(‘integer’ , 100)  – – – دسترسي براي مقدار دهي به آرايه از طريق يک انديس و عملگر []انجام مي گيرد: ‏x[2] = 5 خواندن مقدار آرايه هم با همين عملگر ميسر استy = x[34] : جستجو در آرايه و مرتب سازي آن به منظور جستجوي سريعتر ،مهمترين اعمال سطح باالي آ6رايه هستند مرتب سازي ‏ مرتب سازي – – براي يافتن يک عضو خاص ،بايد تمام اعضاي آرايه را 6بازبيني کرد .براي آرايه هاي خيلي بزرگ اين کار زمان زيادي مي برد اگر آ6رايه مرتب شد باشد يعني يک رابطه ترتيب مثل for all i , j if i < j  : ] A[i]<= A[jبين تمام اعضاي آن برقرار باشد ،محدوده جستجوي الزم براي يافتن عضو مورد نظر کوچکتر مي شود. مثال :براي يافتن عضو ( )3تنها کافي است نيمه اول آرايه [ ]10 9 7 5 4 3 2 1را بازرسي کنيم. معموال مرتب سازي يکبار انجام مي گيرد و پس از آن ،افزودن اعضاي جديد به آرايه با الگوريتم هايي که ترتيب را حفظ مي کنند ،انجام مي شود. – ‏ الگوريتم بکار رفته براي مرتب سازي ممکن است بسيار زمانبر يا پر مصرف باشد. بنابراين سعي بر اين است که ال6گوريتمهايي طراحي کنيم که هزينه کمتري داشته باشند الگوريتم طراحي شده و برنامه نوشته شده بايد : – – – – درست باشد. از منابع موجود به نحو مناسب استفاده كند. با برنامه هاي ديگر بنحو مسالمت آميز اجرا شود. پياده سازي آن راحت باشد. يك الگوريتم مرتب سازي void anysort(int [] A){ int N = A.length ; int flag = 1 ; while (flag ==1 ){ flag = 0 ; for (int k=0 ; k < N -1 ; k ++ ) if (A[k] > A[k+1] ){ int temp = A[k] ; A[k] = A[k+1] ; A[k+1] = temp ; flag = 1 ; } } } هزينه C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 تكرار 1 1 N N N N(N-1) N(N-1) N(N-1) N(N-1) N(N-1) هزينه الگوريتم هزينه كل: C1 +( N -1)( C2 + C3 + C4 + C5) + N(N1) ( C6 + C7 + C8 + C9 + C10) = a N2 + b N +c هزينه C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 تكرار 1 1 N N N-1 N(N-1) N(N-1) N(N-1) N(N-1) N(N-1) بررسي درستي الگوريتم مرتب سازي while (flag ==1 ){ flag = 0 ; for (int k=0 ; k < N -1 ; k ++ ) if (A[k] > A[k+1] ){ swap(A[k] , A[k+1] ) ; flag = 1 ; } } ∀ k∊ [0..N -1] , A[k] >= A[k-1] اثبات درستي :فرض∀ ]k∊ [0..N -1] , A[k] >= A[k-1 :if ∃ m , n : m <n , A[m] > A[n] then  > ]A[m] > A[n -1] , A[m] > A[n-2] … A[m ]A[m+1 A[m] > A[m+1] خالفف رض الگوريتم درست اجرا مي شود Bubble Sort void anysort(int [] A){ int N = A.length ; int flag = 1 ; for( i=0 ; i < N ; i++ ){ for(j=N-1; j > i ; j -- ) { if ( A[j] < A[j-1]) swap (A[j] , A[j-1] ) ; } } } 1+2+…+ n = ½ n ( n +1 ) = هزينه الگوريتمO(N2) هزينه C1 C2 C3 C4 C5 C6 تكرار 1 1 N N+…+1+2 N+…+1+2 N+…+1+2 Insertion Sort void anysort(int [] A){ int N = A.length ; for( i=1 ; i < N ; i++ ){ key = A[i] for(j=i-1; j >= 0 && A[j] > key ; j-- ) { A[j+1] = A[j] ; } A[j + 1] = key ; } } = هزينه الگوريتمO(N2) هزينه C1 C3 C4 C5 C6 C7 تكرار 1 N N-1 1+2+…+N-1 1+2+…+N-1 N-1 رشد توابع f1(N) = 5N2 , f2(N) = 0.01 N3  f2 f1 N 10 500 10  1000050000100  12500001250000500  f2 = 2 f1 1000000050000001000  for N>500, f2 > f1 روشهاي ديگر مرتب سازي استراتژي تقسيم و حلDivide and Conquer : – – مرتب سازي با ادغامMerge Sort مرتب سازي سريعQuick Sort مرتب سازي خطي – ‏Index Sort ، Counting Sort، Radix Sort ساختمان داده هاي ويژه – ‏Heap Sort اين روشها را به مرور در اين درس مطالعه خواهيم کرد. تقسيم و حل حل مسائل بزرگ بوسيله تقسيم به مسايل كوچكتر – – – تقسيم مساله به چند قسمت حل مسايل كوچك ادغام پاسخ مسايل كوچك براي بدست آوردن پاسخ مساله اصلي مثال: – پيدا كردن مينيمم يك آرايه آرايه را به چند بخش تقسيم کرده و مينيمم هر بخش را پيدا مي کنيم .در انتها، مينيمم اين مقادير را 6بعنوان مينيمم آرايه گزارش مي کنيم. مرتب سازي به روش تقسيم و حل ‏ ادغام دو آرايه مرتب – – ‏ الحاق دو آرايه و مرتب سازي آن هزينهO(N2) : ادغام دو آرايه با حفظ ترتيب دو آرايه Lو Rبتنهايي مرتب هستند .به منظور ادغام با حفظ ترتيب: – – – با افزودن يك عدد بسيار بزرگ انتهاي Lو Rرا مشخص مي كنيم در يك حلقه تكراري ،كوچكترين عضو”فعلي” اين دو را انتخاب و يادداشت مي كنيم. محل “فعلي” آرايه انتخاب شده را يك واحد افزايش مي دهيم مرتب سازي با ادغام آرايه ] A=[4 2 7 5 2 1 6 3را مرتب كنيد – اين آرايه را به دو آرايه هم اندازه تقسيم مي كنيم: ‏L=[4 2 7 5], R=[2 1 6 3]  – هر كدام از اين دو آرايه را مرتب مي كنيم ‏L=[2 4 5 7], R=[1 2 3 6]  – و در نهايت اين دو را با حفظ ترتيب ،ادغام مي كنيم: ‏A=[1 2 2 3 4 5 6 7]  ادغام با حفظ ترتيب MERGE(A, p, q, r) .r تاp ازA مرتب سازي آرايه 1. n1 = q - p + 1 ست6 ا6يه6 آرا6قسيم666يت6را666 محلعضو ميانيبq 2. n2 = r - q 3. create arrays L[0 ‥ n1] and R[0 ‥ n2] : 4. for (i = 0 ; i < n1 ; i ++ ) L[i] = A[p + i - 1] 5. for( j = 0 ; j < n2 ; j ++ ) R[j] = A[q + j] 6. L[n1] = ∞ 7. R[n2] = ∞ 8. i=0, j=0 9. for k = p to r 10. if (L[i] ≤ R[j] ) { A[k] =L[i] , i++ } 11. else { A[k] = R[j] , j++ } a (n1 + n2) + b = O(n) = هزينه الگوريتم 1 1 1 n1 n2 1 1 1 r-p+1 r-p+1 r-p+1 ادغام با حفظ ترتيب 1 قسمت مرتب شده اين آرايه را با رنگ روشن مشخص مي كنيم .آرايه هاي Rو Lمرتب هستند. عناصري از اين آرايه ها را كه انتخاب و ادغام شده باشند ،با رنگ تيره نشان مي دهيم. نشان مي دهيم در پايان الگوريتم ادغام ،آرايه A مرتب بوده و Rو Lبه انتها رسيده اند. هنگام شروع ،بخش مرتب شده آرايه Aخالي است ،بنابراين مرتب است! ادغام با حفظ ترتيب 2 ]R[1] < L[1]  A[9] = R[1ق66دم 6اول: قسمتي از آرايه Aكه با رنگ روشن مشخص شده ،مرتب استR[1] .انتخاب شده و رنگ آن تيره شده است. ادغام با حفظ ترتيب 3 ]: L[1] < R[2]  A[10] = L[1قدم دوم آرايه Aكوچكترين عناصر Lو Rرا دارد .ترتيب اين عناصر با مقايسه ] L[i] , R[jمشخص مي شود بنابراين بعد از هر تكرار ،آرايه Aكوچكترين عناصردو آرايه Lو Rرا در خود دارد و مرتب است. ادغام با حفظ ترتيب 4 ]R[2] < L[2]  A[11] = R[2 ادغام با حفظ ترتيب 5 در قسمت ، hآرايه Rبه انتهاي خود رسيده است. عدد ∞ افزوده شده به انتهاي آن سبب مي شود تا در تكرار هاي بعدي حلقه ادغام ،اعضا باقيمانده آرايه Lانتخاب شوند‌ .بنابراين در نهايت و بعد از تكرار حلقه ادغام به تعداد مجموع طول دو آرايه، آرايه Aاعضاي Rو Lرا بصورت مرتب شده در خود خواهد داشت. Mergesort الگوريتم MERGE-SORT(A, p, r) 1 if p < r 2 then q ← ⌊(p + r)/2⌋ 3 MERGE-SORT(A, p, q) 4 MERGE-SORT(A, q + 1, r) 5 MERGE(A, p, q, r) T(N) = O(N) + 2 T(N/2) if N == 1  T(N) = O(1) هزينه 1 1 T(N/2) T(N/2) O(N) مثال Merge Sort آرايه داده شده طي تقسيمات متوالي به آرايه هايي با يك عضو تبديل مي شود: دقت كنيد :هر آرايه يك عضوي ،به خودي خود يك آرايه مرتب است! Merge Sort Example با استفاده از الگوريتم ، mergeاين آرايه ها دوتا دوتا باهم ادغام مي شوند و آرايه هاي دو عضوي تشكيل مي دهند: Merge Sort Example با استفاده از الگوريتم ،mergeاين آرايه ها دوتا دوتا باهم ادغام مي شوند و آرايه هاي چهار عضوي تشكيل مي دهند: Merge Sort Example در نهايت با ادغام دو آرايه بدست آمده از مرحله قبل ،آرايه نهايي مرتب شده بدست مي آيد ارزيابي Merge Sort درستي الگوريتم – – هر آرايه خالي يا تك عضوي ،مرتب است. در قسمت ادغام ديديم كه الگوريتم ادغام عناصر دو آرايه مرتب شده را در يك آرايه مرتب قرار مي دهد. هزينه الگوريتم شامل دو بخش حافظه و زمان است – براي مرتب سازي به حافظه كمكي به اندازه آرايه اصلي نياز داريم. هزينه الگوريتم ‏ هزينه ادغام – ‏ ‏ ‏ ادغام دو آرايه مرتب هزينه اي از مرتبه ) O(Nدارد. هزينه كل الگوريتم يك رابطه بازگشتي به شكل زير است: )T(N) = O(N) + 2T(N/2 روشهاي مختلفي براي حل اين رابطه بازگشتي وجود دارد در اينجا تنها به صورت شهودي رابطه اي برحسب Nمحاسبه مي كنيم. ‏O(N) = cN … T(n) = cN + 2c N/2 + 4 cN/4 + … N cN/N = cn + cn + cn + + cn =cn logn2 – تمرين در فصل دوم كتاب ،CLSRمرتب سازي به روش Insertion Sortبررسي شده است ،اين بخش را مطالعه و با مرتب سازي ارائه شده در اينجا مقايسه كنيد مسايل 1-2تا 5-2را حل كنيد