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

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

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

اسلاید 2: آرايهآرايه مجموعه اي محدود و معين از عناصر هم نوع استمثال :,5] [1 ,2,3,4اعضاي آرايه به صورت صريح تعريف مي شوندآرايه با اعضاي آن به صورت کامل مشخص مي شودتعاريف رياضي و مفهومي مانند “ مجموعه اعداد اول کوچکتر از 100” در اينجا استفاده نمي شوداعمال روي آرايهساخت آرايه: شامل اختصاص حافظه به تعداد معين و از نوع معين است:X = Create_Array(‘integer’ , 100);دسترسي براي مقدار دهي به آرايه از طريق يک انديس و عملگر []انجام مي گيرد: x[2] = 5 خواندن مقدار آرايه هم با همين عملگر ميسر است: y = x[34] جستجو در آرايه و مرتب سازي آن به منظور جستجوي سريعتر، مهمترين اعمال سطح بالاي آرايه هستند

اسلاید 3: مرتب سازيمرتب سازيبراي يافتن يک عضو خاص، بايد تمام اعضاي آرايه را بازبيني کرد. براي آرايه هاي خيلي بزرگ اين کار زمان زيادي مي برداگر آرايه مرتب شد باشد يعني يک رابطه ترتيب مثل : for all i , j if i < j  A[i]<= A[j] بين تمام اعضاي آن برقرار باشد، محدوده جستجوي لازم براي يافتن عضو مورد نظر کوچکتر مي شود. مثال: براي يافتن عضو (3) تنها کافي است نيمه اول آرايه [1 2 3 4 5 7 9 10] را بازرسي کنيم.معمولا مرتب سازي يکبار انجام مي گيرد و پس از آن، افزودن اعضاي جديد به آرايه با الگوريتم هايي که ترتيب را حفظ مي کنند، انجام مي شود.الگوريتم بکار رفته براي مرتب سازي ممکن است بسيار زمانبر يا پر مصرف باشد. بنابراين سعي بر اين است که الگوريتمهايي طراحي کنيم که هزينه کمتري داشته باشندالگوريتم طراحي شده و برنامه نوشته شده بايد :درست باشد.از منابع موجود به نحو مناسب استفاده كند.با برنامه هاي ديگر بنحو مسالمت آميز اجرا شود.پياده سازي آن راحت باشد.

اسلاید 4: يك الگوريتم مرتب سازي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 ; }}}هزينهC1C2C3C4C5C6C7C8C9C10تكرار11NNNN(N-1)N(N-1)N(N-1)N(N-1)N(N-1)

اسلاید 5: هزينه الگوريتمهزينه كل:C1 +( N -1)( C2 + C3 + C4 + C5) + N(N-1) ( C6 + C7 + C8 + C9 + C10)= a N2 + b N +c هزينهC1C2C3C4C5C6C7C8C9C10تكرار11NNN-1N(N-1)N(N-1)N(N-1)N(N-1)N(N-1)

اسلاید 6: بررسي درستي الگوريتم مرتب سازي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]

اسلاید 7: اثبات درستي :فرض∀ 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]  خلاف فرضالگوريتم درست اجرا مي شود

اسلاید 8: Bubble Sortvoid 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] ) ; }}}هزينهC1C2C3C4C5C6تكرار11N1+2+…+N1+2+…+N1+2+…+N1+2+…+ n = ½ n ( n +1 )هزينه الگوريتم = O(N2)

اسلاید 9: Insertion Sortvoid 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 ;}}هزينهC1C3C4C5C6C7تكرار1NN-11+2+…+N-11+2+…+N-1N-1هزينه الگوريتم = O(N2)

اسلاید 10: رشد توابعf1(N) = 5N2 , f2(N) = 0.01 N3Nf1f210500101005000010000500125000012500001000500000010000000f2 = 2 f1for N>500, f2 > f1

اسلاید 11: روشهاي ديگر مرتب سازياستراتژي تقسيم و حل: Divide and Conquerمرتب سازي با ادغامMerge Sortمرتب سازي سريعQuick Sortمرتب سازي خطيIndex Sort ، Counting Sort، Radix Sortساختمان داده هاي ويژهHeap Sortاين روشها را به مرور در اين درس مطالعه خواهيم کرد.

اسلاید 12: تقسيم و حلحل مسائل بزرگ بوسيله تقسيم به مسايل كوچكترتقسيم مساله به چند قسمتحل مسايل كوچكادغام پاسخ مسايل كوچك براي بدست آوردن پاسخ مساله اصليمثال:پيدا كردن مينيمم يك آرايهآرايه را به چند بخش تقسيم کرده و مينيمم هر بخش را پيدا مي کنيم. در انتها، مينيمم اين مقادير را بعنوان مينيمم آرايه گزارش مي کنيم.

اسلاید 13: مرتب سازي به روش تقسيم و حلادغام دو آرايه مرتبالحاق دو آرايه و مرتب سازي آن  هزينه: O(N2)ادغام دو آرايه با حفظ ترتيبدو آرايه Lو Rبتنهايي مرتب هستند. به منظور ادغام با حفظ ترتيب:با افزودن يك عدد بسيار بزرگ انتهاي L و R را مشخص مي كنيم در يك حلقه تكراري، كوچكترين عضو”فعلي” اين دو را انتخاب و يادداشت مي كنيم.محل “فعلي” آرايه انتخاب شده را يك واحد افزايش مي دهيم

اسلاید 14: مرتب سازي با ادغامآرايه 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]

اسلاید 15: ادغام با حفظ ترتيبMERGE(A, p, q, r) n1 = q - p + 1 n2 = r - q create arrays L[0 ‥ n1] and R[0 ‥ n2] : for (i = 0 ; i < n1 ; i ++ ) L[i] = A[p + i - 1] for( j = 0 ; j < n2 ; j ++ ) R[j] = A[q + j] L[n1] = ∞ R[n2] = ∞ i = 0 , j = 0 for k = p to r if (L[i] ≤ R[j] ) { A[k] =L[i] , i++ } else { A[k] = R[j] , j++ }مرتب سازي آرايه Aاز pتا r.q محل عضو مياني براي تقسيم آرايه است111n1n2111r-p+1r-p+1r-p+1هزينه الگوريتم = a (n1 + n2) + b = O(n)

اسلاید 16: ادغام با حفظ ترتيب 1قسمت مرتب شده اين آرايه را با رنگ روشن مشخص مي كنيم. آرايه هاي Rو L مرتب هستند. عناصري از اين آرايه ها را كه انتخاب و ادغام شده باشند، با رنگ تيره نشان مي دهيم. نشان مي دهيم در پايان الگوريتم ادغام، آرايه A مرتب بوده و R و L به انتها رسيده اند.هنگام شروع، بخش مرتب شده آرايه A خالي است، بنابراين مرتب است!

اسلاید 17: ادغام با حفظ ترتيب 2 : قدم اولR[1] < L[1]  A[9] = R[1]قسمتي از آرايه Aكه با رنگ روشن مشخص شده، مرتب است. R[1]انتخاب شده و رنگ آن تيره شده است.

اسلاید 18: ادغام با حفظ ترتيب 3قدم دوم: L[1] < R[2]  A[10] = L[1]آرايه A كوچكترين عناصر Lو R را دارد. ترتيباين عناصر با مقايسه L[i] , R[j] مشخص مي شودبنابراين بعد از هر تكرار، آرايه A كوچكترين عناصردو آرايه L و R را در خود دارد و مرتب است.

اسلاید 19: ادغام با حفظ ترتيب 4R[2] < L[2]  A[11] = R[2]

اسلاید 20: ادغام با حفظ ترتيب 5در قسمت h ، آرايه R به انتهاي خود رسيده است. عدد ∞ افزوده شده به انتهاي آن سبب مي شود تا در تكرار هاي بعدي حلقه ادغام، اعضا باقيمانده آرايه L انتخاب شوند. ‌بنابراين در نهايت و بعد از تكرار حلقه ادغام به تعداد مجموع طول دو آرايه، آرايه A اعضاي Rو L را بصورت مرتب شده در خود خواهد داشت.

اسلاید 21: الگوريتم MergesortMERGE-SORT(A, p, r)1 if p < r2 then q ← ⌊(p + r)/2⌋3 MERGE-SORT(A, p, q)4 MERGE-SORT(A, q + 1, r)5 MERGE(A, p, q, r)هزينه11T(N/2)T(N/2)O(N)T(N) = O(N) + 2 T(N/2)if N == 1  T(N) = O(1)

اسلاید 22: مثال Merge Sort آرايه داده شده طي تقسيمات متوالي به آرايه هايي با يك عضو تبديل مي شود:دقت كنيد: هر آرايه يك عضوي، به خودي خود يك آرايه مرتب است!

اسلاید 23: Merge Sort Exampleبا استفاده از الگوريتم merge، اين آرايه ها دوتا دوتا باهم ادغام مي شوند و آرايه هاي دو عضوي تشكيل مي دهند:

اسلاید 24: Merge Sort Exampleبا استفاده از الگوريتم merge، اين آرايه ها دوتا دوتا باهم ادغام مي شوند و آرايه هاي چهار عضوي تشكيل مي دهند:

اسلاید 25: Merge Sort Exampleدر نهايت با ادغام دو آرايه بدست آمده از مرحله قبل، آرايه نهايي مرتب شده بدست مي آيد

اسلاید 26: ارزيابي Merge Sortدرستي الگوريتمهر آرايه خالي يا تك عضوي، مرتب است. در قسمت ادغام ديديم كه الگوريتم ادغام عناصر دو آرايه مرتب شده را در يك آرايه مرتب قرار مي دهد.هزينه الگوريتم شامل دو بخش حافظه و زمان استبراي مرتب سازي به حافظه كمكي به اندازه آرايه اصلي نياز داريم.

اسلاید 27: هزينه الگوريتمهزينه ادغامادغام دو آرايه مرتب هزينه اي از مرتبه O(N) دارد.هزينه كل الگوريتم يك رابطه بازگشتي به شكل زير است: T(N) = O(N) + 2T(N/2) روشهاي مختلفي براي حل اين رابطه بازگشتي وجود دارد در اينجا تنها به صورت شهودي رابطه اي برحسب Nمحاسبه مي كنيم.O(N) = cNT(n) = cN + 2c N/2 + 4 cN/4 + … N cN/N = cn + cn + cn + … + cn =cn logn2

اسلاید 28: تمرين در فصل دوم كتاب CLSR، مرتب سازي به روش Insertion Sort بررسي شده است، اين بخش را مطالعه و با مرتب سازي ارائه شده در اينجا مقايسه كنيدمسايل 2-1 تا 2-5 را حل كنيد