لطفا به نکات زیر در هنگام خرید دانلود فایل پاورپوینت مرتب سازي مقايسه اي مرتب سازي خطي توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود فایل پاورپوینت مرتب سازي مقايسه اي مرتب سازي خطي قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 4 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

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

اسلاید ۱ :

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

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

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

–Quicksort, Mergesort, Heapsort

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

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

اسلاید ۲ :

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

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

l<a1, a2, a3>

l<a1, a3, a2>

l<a2, a1, a3>

l<a2, a3, a1>

l<a3, a1, a2>

l<a3, a2, a1>

اسلاید ۳ :

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

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

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

l2h >= n!  à h > log(n!)

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

lh > n log ( n/e)= nlogn –nloge à h = O(nlogn)

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

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

ارتفاع درخت = بيشترين تعداد مقايسه ها و بدترين حالت الگوريتم

اسلاید ۴ :

Counting-sort(A[1..n]) //A is an integer array

for i←۱ to k  // k = max(A[1..n])

do C[i] ←۰

for j←۱ to n

do C[A[j]] ←C[A[j]] + 1  //C[i] = |{key = i}|

for i←۲  to k

do C[i] ←C[i] + C[i–۱]  //C[i] = |{key ≤i}|

for jn downto 1

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

C[A[j]] ←C[A[j]] –۱

اسلاید ۵ :

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

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

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

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

اسلاید ۶ :

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

اسلاید ۷ :

lHerman Hollerith در سال ۱۸۹۰ ، پيشنهاد كرد.

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

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

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

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

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

اسلاید ۸ :

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

اسلاید ۹ :

lبراي مرتب سازي  n عدد دهدهي(Decimal Integer)  كه ارقام آنها از ۰ تا ۹ متغير است،   لازم است به تعداد ارقام اعداد (مثلا d) فرايند مرتب سازي تكرار شود.

l با استفاده از Counting Sort بعنوان الگوريتم مرتب سازي ارقام، بسادگي مي توان ديد كه فرايند مرتب سازي هزينه اي برابر Θ(d * (n +k) )  دارد كه در آن k تعداد انواع رقم است(براي اعداد دهدهي ، k=10)

lمي توان اين الگوريتم را طوري تغيير داد كه در هر فاز بيش از يك رقم را مورد استفاده قرار دهد

اسلاید ۱۰ :

lاعداد در كامپيوتر بصورت باينري ذخيره مي شوند و از آنجاكه عملگرهاي مقايسه اي بيتها در سخت افزار بصورت دستورات cpu پياده شده، هوشمندانه است از ارقام دوديي براي مرتب سازي استفاده شود

lهنگام استفاده از اعداد باينري، معمولا بيش از ۱ بيت بعنوان يك رقم استفاده مي شود.

–اگر اعداد ۳۲ بيتي را با رقم ۴ بيتي مرتب كنيم، ۸ بار لازم است فرايند مرتب سازي رو ي ارقام مختلف اجرا شود.  Counting Sort 24 يا ۱۶ عدد مختلف را مرتب مي كند