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

فرمت فایل دانلودی: .zip
فرمت فایل اصلی: pptx
تعداد صفحات: 33
حجم فایل: 267
قیمت: 75500 تومان

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

نوع فایل : .ppt ( قابل ويرايش و آماده پرينت )

تعداد اسلاید : 33 اسلاید

قسمتی از متن .ppt :

مرتب سازی مقايسه ای مرتب سازی خطی

ساختمان داده ها و الگوريتمها

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

در همه اين الگوريتمها، اعضاي آرايه با هم مقايسه مي شوند. اين نوع الگوريتم ها را مقايسه اي مي گوييم.
بهترين زمان اجراي الگوريتمهاي بررسي شده در بدترين حالت، n log n بوده است.
Quicksort Mergesort Heapsort
آيا مي توان الگوريتمي با زمان كمتر از n log n ارائه داد؟
آيا روش ديگري غير از انواع مختلف الگوريتم هاي مقايسه اي؛ براي مرتب سازي وجود دارد ؟

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

ترتيب ممكن:

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

درخت تصميم يك الگوريتم مرتب سازي بايد حداقل n!‌برگ داشته باشد تا تمام حالات ممكن ترتيب nعدد را در برگيرد.
بدترين حالت يك الگوريتم ، ارتفاع درخت است.
درخت دوديي به ارتفاع h حداكثر 2h برگ دارد. اين تعداد برگ بايد تمام ترتيبات مختلف را پوشش دهد.
2h >= n!  h > log(n!)
n! ≈ (n/e) n (قضيه استرلينگ)
h > n log ( n/e)= nlogn –nloge  h = O(nlogn)
كمترين زمان اجراي الگوريتمهاي مقايسه اي n log n است.
اين نتيجه نا اميد کننده است ؟

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←n downto 1
do B[C[A[j]]] ←A[j]
C[A[j]] ←C[A[j]] –1

پرداخت با کلیه کارتهای عضو شتاب امکان پذیر است.