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

پاورپوینت مرتب سازي مقايسه اي مرتب سازی خطی (pptx) 35 اسلاید

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

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

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

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

بنام خدا مرتب سازي مقايسه ايمرتب سازي خطي ساختمان داده ها و الگوريتمها مرتب سازي مقايسه اي تاكنون چندين الگوريتم مرتب سازي را بررسي كرده ايم. در همه اين الگوريتمها، اعضاي آرايه با هم مقايسه مي شوند. اين نوع الگوريتم ها را مقايسه اي مي گوييم. بهترين زمان اجراي الگوريتمهاي بررسي شده در بدترين حالت، n log n بوده است. Quicksort, Mergesort, Heapsort آيا مي توان الگوريتمي با زمان كمتر از n log n ارائه داد؟ آيا روش ديگري غير از انواع مختلف الگوريتم هاي مقايسه اي؛ براي مرتب سازي وجود دارد ؟ مساله مرتب سازي ترتيب ممكن: a1:a2 a2:a3 a1:a3 a2:a3 a1:a3 Decision Tree for Insertion Sort مساله مرتب سازي ارتفاع درخت = بيشترين تعداد مقايسه ها و بدترين حالت الگوريتم a1:a2 a2:a3 a1:a3 a2:a3 a1:a3 حداقل هزينه مرتب سازي درخت تصميم يك الگوريتم مرتب سازي بايد حداقل n!‌برگ داشته باشد تا تمام حالات ممكن ترتيب nعدد را در برگيرد. بدترين حالت يك الگوريتم ، ارتفاع درخت است. درخت دوديي به ارتفاع h حداكثر 2h برگ دارد. اين تعداد برگ بايد تمام ترتيبات مختلف را پوشش دهد. 2h >= n!  h > log(n!) n! ≈ (n/e) n (قضيه استرلينگ) h > n log ( n/e)= nlogn –nloge  h = O(nlogn) كمترين زمان اجراي الگوريتمهاي مقايسه اي n log n است. اين نتيجه نا اميد کننده است ؟ Counting Sort Counting-sort(A[1..n]) //A is an integer array for i←1 to k // k = max(A[1..n]) do C[i] ←0 for j←1 to n do C[A[j]] ←C[A[j]] + 1 //C[i] = |{key = i}| for i←2 to k do C[i] ←C[i] + C[i–1] //C[i] = |{key ≤i}| for j←n downto 1 do B[C[A[j]]] ←A[j] C[A[j]] ←C[A[j]] –1 Counting Sort - Example A C B Loop 1: Initialization A C B for i=1 to k C[i]= 0