فرمت فایل: پاورپوینت - ppt  

کتاب سبز - قابل ویرایش ) 

تعداد اسلاید : 44
مرتب سازي سريع Quicksort ساختمان داده ها و الگوريتمها Quicksort Hoare در سال 1962 پيشنهاد كرده است از روش تقسيم و حل (Divide & Conquer) استفاده مي كند آرايه را به صورت “در جا” (In Place)مرتب مي كند شبيه مرتب سازي درجي(Insertion Sort) است. برخلاف (Merge Sort ) به حافظه اضافي نياز ندارد. پياده سازي هاي سريعي كه براي آن ارائه شده، باعث بكارگيري وسيع آن در عمل شده است. تقسيم و حل تقسيم:يك عضو مثل x از آرايه را انتخاب كرده و آرايه را طوري به دو بخش طوري تقسيم مي كنيم كه يك بخش آن از x كوچكتر و بخش ديگر از x بزرگتر باشند. حل: به صورت بازگشتي هر كدام از اين دو بخش را مرتب مي كنيم تركيب: كارخاصي لازم نيست! نكته: هزينه عمل تقسيم خطي است Θ(n) تقسيم PARTITION(A, p, q)// A[p. . q] x←A[p] // pivot= A[p] i←p for j←p+ 1 to q do if A[j] ≤x then i←i+ 1 swap A[i] ↔A[j] swap A[p] ↔A[i] // final place of pivot! return i مثال مثال مثال مثال مثال مثال مثال مثال مثال مثال شبه كد الگوريتم مرتب سازي QUICKSORT(A, p, r) if p< r then q←PARTITION(A, p, r) QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r) Initial call:QUICKSORT(A, 1, n) آناليز الگوريتم فرض كنيد تمام اعضاي آرايه غير تكراري هستند. در عمل معمولا روشهاي مناسبتري براي تقسيم آرايه هايي كه اعضاي تكراري دارند، استفاده مي شود فرض كنيد T(n) هزينه مرتب سازي آرايه اي به طول n با استفاده ازاين الگوريتم در بدترين حالت باشد. معمولا بهترين حالت الگوريتمها را در نظر نمي گيريم اما براي مرتب سازي سريع اين حالت را نيز بررسي مي كنيم. بدترين حالات quicksort درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت بهترين حالت 10% 90% 10% 90% 10% 90% 10% 90% 10% 90% 10% 90% 10% 90% حالتي ديگر Randomized Quicksort آناليز مرتب سازي با تقسيم تصادفي آناليز مرتب سازي با تقسيم تصادفي آناليز مرتب سازي با تقسيم تصادفي آناليز مرتب سازي با تقسيم تصادفي آناليز مرتب سازي با تقسيم تصادفي بحث و بررسي تمرين

قسمتی از متن بالا پروژه میباشد که به صورت نمونه ، بعد از پرداخت آنلاین در جزوه باز آنی فایل را دانلود نمایید .

  

 « پرداخت آنلاین و دانلود در قسمت پایین »