دانلود پاورپوینت با موضوع مرتب سازي سريع Quicksort و ساختمان داده ها و الگوريتمها،
در قالب ppt و در 44 اسلاید، قابل ویرایش.
بخشی از متن پاورپوینت:
Hoare در سال 1962 پيشنهاد كرده است
از روش تقسيم و حل (Divide & Conquer) استفاده مي كند
آرايه را به صورت “در جا” (In Place)مرتب مي كند
شبيه مرتب سازي درجي(Insertion Sort) است.
برخلاف (Merge Sort ) به حافظه اضافي نياز ندارد.
پياده سازي هاي سريعي كه براي آن ارائه شده، باعث بكارگيري وسيع آن در عمل شده است.
تقسيم و حل
تقسيم:يك
عضو مثل x از آرايه را انتخاب كرده و آرايه را طوري به دو بخش طوري
تقسيم مي كنيم كه يك بخش آن از x كوچكتر و بخش ديگر از x بزرگتر باشند.
حل: به صورت بازگشتي هر كدام از اين دو بخش را مرتب مي كنيم
تركيب: كارخاصي لازم نيست!
نكته: هزينه عمل تقسيم خطي است Θ(n)
بهترين حالت
در بهترين حالت، دو بخش تقسيم شده تقريبا هم اندازه هستند و اندازه مساله در هر بار تقسيم نصف مي شود:
T(n) = 2T(n/2) + Θ(n) Θ(n log n) (mergesort)
سوال: اگر تقسيم طوري صورت بگيرد كه 90% اعضاي آرايه در يك بخش و %10 در بخش ديگر قرار بگيرند، هزينه الگوريم چگونه خواهد بود ؟
T(n) = T(n/10) + T(9n/10)+ Θ(n)
از روش تقسيم و حل (Divide & Conquer) استفاده مي كند
آرايه را به صورت “در جا” (In Place)مرتب مي كند
شبيه مرتب سازي درجي(Insertion Sort) است.
برخلاف (Merge Sort ) به حافظه اضافي نياز ندارد.
پياده سازي هاي سريعي كه براي آن ارائه شده، باعث بكارگيري وسيع آن در عمل شده است.
تقسيم و حل
تقسيم:يك
عضو مثل x از آرايه را انتخاب كرده و آرايه را طوري به دو بخش طوري
تقسيم مي كنيم كه يك بخش آن از x كوچكتر و بخش ديگر از x بزرگتر باشند.
حل: به صورت بازگشتي هر كدام از اين دو بخش را مرتب مي كنيم
تركيب: كارخاصي لازم نيست!
نكته: هزينه عمل تقسيم خطي است Θ(n)
بهترين حالت
در بهترين حالت، دو بخش تقسيم شده تقريبا هم اندازه هستند و اندازه مساله در هر بار تقسيم نصف مي شود:
T(n) = 2T(n/2) + Θ(n) Θ(n log n) (mergesort)
سوال: اگر تقسيم طوري صورت بگيرد كه 90% اعضاي آرايه در يك بخش و %10 در بخش ديگر قرار بگيرند، هزينه الگوريم چگونه خواهد بود ؟
T(n) = T(n/10) + T(9n/10)+ Θ(n)
دانلود فایل”پاورپوینت مرتب سازي سريع Quicksort و ساختمان داده ها و الگوريتمها”