دانلود مرتب سازي سريع
دسته بندي :
علوم پایه »
دانلود پاورپوینت های علمی
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : powerpoint (..ppt) ( قابل ويرايش و آماده پرينت )
تعداد اسلاید : 45 اسلاید
قسمتی از متن powerpoint (..ppt) :
بنام خدا
1
مرتب سازي سريع Quicksort
ساختمان داده ها و الگوريتمها
2
Quicksort
Hoare در سال 1962 پيشنهاد كرده است
از روش تقسيم و حل (Divide & Conquer) استفاده مي كند
آرايه را به صورت “در جا” (In Place) مرتب مي كند
شبيه مرتب سازي درجي (Insertion Sort) است.
برخلاف (Merge Sort ) به حافظه اضافي نياز ندارد.
پياده سازي هاي سريعي كه براي آن ارائه شده، باعث بكارگيري وسيع آن در عمل شده است.
3
تقسيم و حل
تقسيم:يك عضو مثل x از آرايه را انتخاب كرده و آرايه را طوري به دو بخش طوري تقسيم مي كنيم كه يك بخش آن از x كوچكتر و بخش ديگر از x بزرگتر باشند.
x
>= x
حل: به صورت بازگشتي هر كدام از اين دو بخش را مرتب مي كنيم
تركيب: كارخاصي لازم نيست!
نكته: هزينه عمل تقسيم خطي است Θ(n)
4
تقسيم
هزينه تقسيم براي آرايه n عضوي برابر Θ(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
5