مرتب سازی مقایسه ای مرتب سازی خطی
ساختمان داده ها و الگوریتمها
مرتب سازی مقایسه ای
تاکنون چندین الگوریتم مرتب سازی را بررسی کرده ایم. در همه این الگوریتمها، اعضای آرایه با هم مقایسه می شوند. این نوع الگوریتم ها را مقایسه ای می گوییم.
بهترین زمان اجرای الگوریتمهای بررسی شده در بدترین حالت، n log n بوده است.
Quicksort, Mergesort, Heapsort
آیا می توان الگوریتمی با زمان کمتر از n log n ارائه داد؟
آیا روش دیگری غیر از انواع مختلف الگوریتم های مقایسه ای؛ برای مرتب سازی وجود دارد ؟
مساله مرتب سازی
<a1, a2, a3 > ترتیب ممکن:
<a1, a2, a3>
<a1, a3, a2>
<a2, a1, a3>
<a2, a3, a1>
<a3, a1, a2>
<a3, a2, a1>
a1:a2
a2:a3
a1:a3
a2:a3
<a3,a2,a1>
a1:a3
<a1,a2,a3>
<a1,a3,a2>
<a3,a1,a2>
<a2,a3,a1>
<a2,a1,a3>
Decision Tree for
Insertion Sort
مساله مرتب سازی
ارتفاع درخت = بیشترین تعداد مقایسه ها و بدترین حالت الگوریتم
a1:a2
a2:a3
a1:a3
a2:a3
<a3,a2,a1>
a1:a3
<a1,a2,a3>
<a1,a3,a2>
<a3,a1,a2>
<a2,a3,a1>
<a2,a1,a3>
حداقل هزینه مرتب سازی
درخت تصمیم یک الگوریتم مرتب سازی باید حداقل 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
Counting Sort – Example
A
C
B
Loop 1: Initialization
A
C
B
for i=1 to k
C[i]= 0
Loop 2: Counting …
A
C
B
for j←1 to n
do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|
Loop 2: Counting …
A
C
B
for j←1 to n
do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|
Loop 2: Counting …
A
C
B
for j←1 to n
do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|
Loop 2: Counting …
A
C
B
for j←1 to n
do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|
Loop 2: Counting …
A
C
B
for j←1 to n
do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|
Loop 3: Cumulating…
A
C
B
for j←2 to k
do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|
C’
Loop 3: Cumulating…
A
C
B
for j←2 to k
do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|
C’
Loop 3: Cumulating…
A
C
B
for j←2 to k
do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|
C’
Loop 4: Placement…
A
C
B
for j←n downto 1
do B[C[A[j]]] ←A[j] //Place A[j]
C[A[j]] ←C[A[j]] –1 // Decrement C[A[j]]
C’
Loop 4: Placement…
A
C
B
for j←n downto 1
do B[C[A[j]]] ←A[j] //Place A[j]
C[A[j]] ←C[A[j]] –1 // Decrement C[A[j]]
C’
Loop 4: Placement…
A
C
B
for j←n downto 1
do B[C[A[j]]] ←A[j] //Place A[j]
C[A[j]] ←C[A[j]] –1 // Decrement C[A[j]]
C’
Loop 4: Placement…
A
C
B
for j←n downto 1
do B[C[A[j]]] ←A[j] //Place A[j]
C[A[j]] ←C[A[j]] –1 // Decrement C[A[j]]
C’
Loop 4: Placement…
A
C
B
for j←n downto 1
do B[C[A[j]]] ←A[j] //Place A[j]
C[A[j]] ←C[A[j]] –1 // Decrement C[A[j]]
C’
آنالیز الگوریتم
Loop1: Θ(k)
for i=1 to k do C[i]= 0 :
Loop 2 :Θ(n)
for j←1 to n do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|
Loop 3: Θ(k)
for j←2 to k do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|
Loop 4:Θ(n)
for j←n downto1
do B[C[A[j]]] ←A[j]
C[A[j]] ←C[A[j]] –1
Tootal: Θ(k + n)
آنالیز الگوریتم
if k = Θ(n) T(Countingsort(n))= Θ(n)
آیا این نتیجه تناقضی با حداقل بدست آمده در بخش اول دارد؟
توجه کنید: در این الگوریتم هیچ مقایسه ای صورت نمی گیرد!
نتیجه بدست آمده در بخش اول برای الگوریتم های مقایسه ای بود
Stable Sorting مرتب سازی پایدار
A
B
الگوریتم Counting Sort در صورتی که دو عضو آرایه کلید مساوی داشته باشند، ترتیب آنها را حفظ می کند. این نوع الگوریتم را مرتب سازی پایدار می نامند
Radix Sort مرتب سازی ریشه ای
Herman Hollerith در سال 1890 ، پیشنهاد کرد.
این الگوریتم، در محاسبات آماری سال 1890 آمریکا بصورت مکانیکی و الکتریکی پیاده سازی و استفاده شد
نتایج سرشماری دوره قبل 10 سال طول کشیده بود. با استفاده از این ماشین، گزارشهای آماری اولیه ظرف 6 هفته! منتشر شد
اعداد را رقم به رقم و بصورت پایدار مرتب می کند
الگوریتم اولیه از پر ارزشترین رقم شروع می کند
الگوریتم بهبود یافته از پایین ترین ارزش شروع می کند
Radix Sort Example
درستی Radix Sort
اگر با استفاده از این الگوریتم، دو عدد تا رقم t-1 مرتب شده باشند، با مرتب سازی آنها بر اساس رقم t :
درصورتی که رقم t دو عدد یکی باشد، خاصیت پایداری سبب حفظ ترتیب فعلی آنها می شود.
در صورتی که این دو رقم متفاوت باشند، ارزش بالای رقم t ترتیب دو عدد را تعیین می کند.
آنالیز الگوریتم
برای مرتب سازی n عدد دهدهی(Decimal Integer) که ارقام آنها از 0 تا 9 متغیر است، لازم است به تعداد ارقام اعداد (مثلا d) فرایند مرتب سازی تکرار شود.
با استفاده از Counting Sort بعنوان الگوریتم مرتب سازی ارقام، بسادگی می توان دید که فرایند مرتب سازی هزینه ای برابر Θ(d * (n +k) ) دارد که در آن k تعداد انواع رقم است(برای اعداد دهدهی ، k=10)
می توان این الگوریتم را طوری تغییر داد که در هر فاز بیش از یک رقم را مورد استفاده قرار دهد
آنالیز الگوریتم، ادامه
اعداد در کامپیوتر بصورت باینری ذخیره می شوند و از آنجاکه عملگرهای مقایسه ای بیتها در سخت افزار بصورت دستورات cpu پیاده شده، هوشمندانه است از ارقام دودیی برای مرتب سازی استفاده شود
هنگام استفاده از اعداد باینری، معمولا بیش از 1 بیت بعنوان یک رقم استفاده می شود.
اگر اعداد 32 بیتی را با رقم 4 بیتی مرتب کنیم، 8 بار لازم است فرایند مرتب سازی رو ی ارقام مختلف اجرا شود. Counting Sort 24 یا 16 عدد مختلف را مرتب می کند
آنالیز الگوریتم – ادامه
اگر n عدد مورد نظر برای مرتب سازی b بیتی باشند و از ارقام r بیتی استفاده کنیم، این اعداد d=b/r رقم خواهند داشت.
آرایه C مورد استفاده در Counting Sort باید k=2r رقم مختلف را مرتب کند.
بنابراین هزینه کل الگوریتم برابر است با:
T(n,b) = Θ(d * (n +k) ) = Θ((b/r)(n+2r))
بهترین انتخاب r چیست ؟
آنالیز الگوریتم – ادامه
T(n,b) = Θ(d * (n +k) ) = Θ((b/r)(n+2r))
با مشتق گیری و محاسبه مینیمم این تابع r = log n بدست می آید.
r= log n T(n,b) = Θ((b/logn)(n+2logn))= Θ(bn/logn)
اگر اعداد مورد نظر برای مرتب سازی بین 0..nd -1 باشند:
b =d logn , T(n,b) = Θ(dn)
بحث و بررسی
برای حجم برزرگ آرایه ها، radixsort کارایی خوبی دارد
برای مرتب سازی 2000 عدد 32 بیتی، این الگوریتم چهار بار تکرار می شود اما، mergesort و quicksort حداقل 11 بار تکرار می شوند(عمل تقسیم آرایه به آرایه های کوچکتر 11 بار صورت می گیرد)
Quicksort در هر بار تقسیم، ناحیه مراجعه به حافظه را کوچکتر می سازد. این ویژگی در پردازنده های جدید مجهز به حافظه Cache امتیازی محسوب می شود. از این نظر، Q.S. که خوب طراحی شده باشد، معمولا هم ارز Radix Sort کارایی دارد
تکلیف و تمرین
در اینجا فرض کردیم آرایه های مورد نظر برای مرتب سازی، اعداد صحیح هستند؛ به نظر شما برای مرتب سازی اعداد اعشاری چگونه می توان از این الگوریتمها بهره گرفت؟
در کتاب، الگوریتم Bucket Sort بدین منظور معرفی شده است. این الگوریتم را مطالعه کنید و سعی کنید راه حل دیگری هم برای این مساله پیشنهاد کنید.
مسایل بخش 8 را حل کنید