صفحه محصول - پاورپوینت مدیریت فایل مرتب سازی و ادغام فایلها

پاورپوینت مدیریت فایل مرتب سازی و ادغام فایلها (pptx) 27 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 27 اسلاید

قسمتی از متن PowerPoint (.pptx) :

Lecture 12مرتب سازي و ادغام فايلها (Sorting and Merging files) (Sections 8.3 - 8.5) مرتب سازي و ادغام فايلها(Sort and Merge of files) کاربرد هاي ديگر پردازش همزمان (Co-sequential processing) کدامند؟ الگوريتم ادغام چندتايي (K-way Merge) چگونه است؟ روش مرتب سازي Selection Tree چيست؟ روش مرتب سازي Heap Sort چگونه است؟ روش Overlapping در Heap Sort چگونه است؟ مرتب سازي فايلهاي بزرگ چه مشکلاتي دارد؟ روش مرتب سازي Merge-Sort چيست؟ مرتب سازي و ادغام فايلها(Sort and Merge of files) کاربرد هاي ديگر پردازش همزمان کدامند؟ (Co-sequential processing) الگوريتم ادغام چندتايي (K-way Merge) روش مرتب سازي Selection Tree روش مرتب سازي Merge-Sort الگوريتم ادغام چندتايي (K-way) چگونه است؟ ادغام تعداد K ليست مرتب شده و توليد يک ليست واحد (مرتب شده). تعميم الگوريتم قبلي (2-way). تعريف برداري با تعداد K ليست به نام List [K]...List [1] : تعريف برداري با تعداد K آيتم به نام: item[ K]...item [1] مرتب سازي و ادغام فايلها الگوريتم ادغام چندتايي (K-way) چگونه است؟ الگوريتم ادغام (با حذف آيتم هاي تکراري): 1) MinItem = set to min of item[1]…item[ K] Output MinItem to output list (ص 309 کتاب) 3) For i = 1 to K do: If item[ i ]= MinItem then Get next item[ i ] from List[ i ] مرتب سازي و ادغام فايلها روش مرتب سازي Selection Tree چيست؟ يک الگوريتم ديگر براي ادغام ميبا شد که مشابه مسابقات دوره اي (مثل فوتبال) عمل ميکند. وقتي تعداد ليست ها بيش از 8 باشد اين الگوريتم ارجحيت دارد. (چرا؟) مانند يک Binary Tree با عمق Log 2(K) عمل مي کند. مثال: ص 311 کتاب شکل 8.15 مرتب سازي و ادغام فايلها روش مرتب سازي Heap Sort چگونه است؟ يک الگوريتم مرتب سازي در حافظه (RAM) ميباشد. Heap يک درخت دودويي کامل است با ارتفاع Height = log n هر گره (node) يک کليد بيشتر ندارد که بزرگتر يا برابر کليد گره پدر (parent) ميباشد. بصورت يک آرايه (Array) ذخيره ميشود. براي هر گره (i) فرزندان آن در گره هاي (2i) و (2i+1) ذخيره شده اند. پدر هر گره (j) در گره (j/2) ميباشد. مرتب سازي و ادغام فايلها الگوريتم Insert در Heap Sort چگونه است؟ رکورد جديد در آخر Heap اضافه ميشود. کليد آن با کليد گره پدر مقايسه مي شود و اگر مقدار آن کوچکتر بود محل آن با محل گره پدر تعويض ميشود. در صورت لزوم عمل (2) تا ريشه درخت (Root) ادامه مييابد. الگوريتم Insert در Heap Sort int Heap::Insert(char * newKey) { if (NumElements == MaxElements) return FALSE; NumElements++; // add the new key at the last position HeapArtay[NumElementsJ = newKey; // re-order the heap int k = NumElements; int parent; while (k > 1) //I k has a parent { parent = k / 2; if IComparelk. parent) >= 0) break; // HeapArray[k] is in the ri9ht place // else exchange k and parent Exchange(k , parent); k = parent; } return TRUE; } (ص 314، شکل 8.17) مرتب سازي و ادغام فايلها الگوريتم Remove در Heap Sort چگونه است؟ کوچکترين کليد که در گره Root ميباشد خارج ميشود. بزرگترين کليد (آخرين گره) به گره Root منتقل ميگردد. کليد آن با کوچکترين کليد فرزند مقايسه مي شود و اگر بيشتر بود جاي آن دو تعويض ميشود. در صورت لزوم عمل (3) تا آخر Heap تکرار ميگردد.