پاورپوینت کامل مرتب سازی مقایسه ای ، مرتب سازی خطی ۳۷ اسلاید در PowerPoint

قسمتی از پاورپوینت :

تاکنون چندین الگوریتم مرتب سازی را بررسی کرده ایم. در همه این الگوریتمها، اعضای آرایه با هم مقایسه می شوند. این نوع الگوریتم ها را مقایسه ای می گوییم.
بهترین زمان اجرای الگوریتمهای بررسی شده در بدترین حالت، n log n بوده است.
Quicksort, Mergesort, Heapsort
آیا می توان الگوریتمی با زمان کمتر از n log n ارائه داد؟
آیا روش دیگری غیر از انواع مختلف الگوریتم های مقایسه ای؛ برای مرتب سازی وجود دارد ؟
درخت تصمیم یک الگوریتم مرتب سازی باید حداقل n!‌برگ داشته باشد تا تمام حالات ممکن ترتیب nعدد را در برگیرد.
بدترین حالت یک الگوریتم ، ارتفاع درخت است.
درخت دودیی به ارتفاع h حداکثر ۲h برگ دارد. این تعداد برگ باید تمام ترتیبات مختلف را پوشش دهد.
۲h >= n! h > log(n!)
n! ≈ (n/e) n (قضیه استرلینگ)
h > n log ( n/e)= nlogn –nloge h = O(nlogn)
کمترین زمان اجرای الگوریتمهای مقایسه ای n log n است.
این نتیجه نا امید کننده است ؟
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