دانلود فایل پاورپوینت مرتب سازی مقایسه ایمرتب سازی خطی

بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

مرتب سازي مقايسه اي

تاكنون چندين الگوريتم مرتب سازي را بررسي كرده ايم. در همه اين الگوريتمها،  اعضاي آرايه با هم مقايسه مي شوند. اين نوع الگوريتم ها را مقايسه اي مي گوييم.

  بهترين زمان اجراي الگوريتمهاي بررسي شده در بدترين حالت، n og n بوده است.

–Quicksort, Mergesort, Heapsort

آيا مي توان الگوريتمي با زمان كمتر از n og n ارائه داد؟

آيا روش ديگري غير از انواع مختلف الگوريتم هاي مقايسه اي؛ براي مرتب سازي وجود دارد ؟

اسلاید 2 :

مساله مرتب سازي

 <a1, a2, a3 >  ترتيب ممكن:

<a1, a2, a3>

<a1, a3, a2>

<a2, a1, a3>

<a2, a3, a1>

<a3, a1, a2>

<a3, a2, a1>

اسلاید 3 :

حداقل هزينه مرتب سازي

درخت تصميم يك الگوريتم مرتب سازي بايد حداقل n!‌برگ داشته باشد تا تمام حالات ممكن ترتيب nعدد را در برگيرد.

بدترين حالت يك الگوريتم ، ارتفاع درخت است.

درخت دوديي به ارتفاع h حداكثر 2h  برگ دارد.  اين تعداد برگ بايد تمام ترتيبات مختلف را پوشش دهد.

2h >= n!  à h > og(n!)

n! ≈ (n/e) n  (قضيه استرلينگ)

h > n og ( n/e)= n ogn –n oge à h = O(n ogn)

كمترين زمان اجراي الگوريتمهاي مقايسه اي n og n است.

–اين نتيجه نا اميد کننده است ؟

اسلاید 4 :

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←ndownto 1

do B[C[A[j]]] ←A[j]

C[A[j]] ←C[A[j]] –1

اسلاید 5 :

for j←ndownto 1

 do  B[C[A[j]]] ←A[j]  //P ace A[j]

       C[A[j]] ←C[A[j]] –1 // Decrement C[A[j]]

اسلاید 6 :

آناليز الگوريتم

oop1: Θ(k)

– for i=1 to k  do C[i]= 0 :

oop 2 :Θ(n)

–for j←1 to n  do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|

oop 3: Θ(k)

–for j←2  to k do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|

oop 4:Θ(n)

–for j←ndownto1

do  B[C[A[j]]] ←A[j]

C[A[j]] ←C[A[j]] –1

Toota : Θ(k + n)

–

اسلاید 7 :

if k = Θ(n)  à T(Countingsort(n))= Θ(n)

آيا اين نتيجه تناقضي با حداقل بدست آمده در بخش اول دارد؟

–توجه كنيد: در اين الگوريتم هيچ مقايسه اي صورت نمي گيرد!

–نتيجه بدست آمده در بخش اول براي الگوريتم هاي مقايسه اي بود

اسلاید 8 :

Stab e Sorting مرتب سازي پايدار

• الگوريتم Counting Sort در صورتي كه دو عضو آرايه كليد مساوي داشته باشند، ترتيب آنها را حفظ مي كند. اين نوع الگوريتم را مرتب سازي پايدار مي نامند

اسلاید 9 :

Radix Sort مرتب سازي ريشه اي

Herman Ho erith در سال 1890 ، پيشنهاد كرد.

–اين الگوريتم، در محاسبات آماري سال 1890 آمريكا بصورت مكانيكي و الكتريكي پياده سازي و استفاده شد

–نتايج سرشماري دوره  قبل  10 سال طول كشيده بود. با استفاده از اين ماشين، گزارشهاي آماري اوليه ظرف 6 هفته! منتشر شد

اعداد را رقم به رقم و بصورت پايدار مرتب مي كند

الگوريتم اوليه از پر ارزشترين رقم شروع مي كند

الگوريتم بهبود يافته از پايين ترين ارزش شروع مي كند

اسلاید 10 :

درستي Radix Sort

• اگر با استفاده از اين الگوريتم، دو عدد تا رقم t-1 مرتب شده باشند، با مرتب سازي آنها بر اساس رقم t :
• درصورتي كه رقم t دو عدد يكي باشد، خاصيت پايداري سبب حفظ ترتيب فعلي آنها مي شود.
• در صورتي كه اين دو رقم متفاوت باشند، ارزش بالاي رقم t ترتيب دو عدد را تعيين مي كند.