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

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

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

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

اسلاید 3: مساله مرتب سازي <a1, a2, a3 >ترتيب ممكن:<a1, a2, a3><a1, a3, a2><a2, a1, a3><a2, a3, a1><a3, a1, a2><a3, a2, a1>a1:a2a2:a3a1: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 forInsertion Sort

اسلاید 4: برگهاي درخت Leaf Nodes/مساله مرتب سازيارتفاع درخت = بيشترين تعداد مقايسه ها و بدترين حالت الگوريتمa1:a2a2:a3a1:a3<=a2:a3<a3,a2,a1>>>>a1:a3<a1,a2,a3><=><a1,a3,a2><a3,a1,a2>><=<a2,a3,a1><=<a2,a1,a3><=3=h=ارتفاع درخت

اسلاید 5: حداقل هزينه مرتب سازيدرخت تصميم يك الگوريتم مرتب سازي بايد حداقل 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 است.اين نتيجه نا اميد کننده است ؟

اسلاید 6: Counting SortCounting-sort(A[1..n]) //A is an integer arrayfor i←1 to k// k = max(A[1..n])do C[i] ←0for j←1 to ndo C[A[j]] ←C[A[j]] + 1//C[i] = |{key = i}|for i←2to kdo C[i] ←C[i] + C[i–1]//C[i] = |{key ≤i}|for j←n downto 1do B[C[A[j]]] ←A[j]C[A[j]] ←C[A[j]] –1

اسلاید 7: Counting Sort - Example123412345ACB

اسلاید 8: Loop 1: Initialization1234000012345ACBfor i=1 to k C[i]= 0

اسلاید 9: Loop 2: Counting …1234000112345ACBforj←1ton do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|

اسلاید 10: Loop 2: Counting …1234100112345ACBforj←1ton do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|

اسلاید 11: Loop 2: Counting …1234101112345ACBforj←1ton do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|

اسلاید 12: Loop 2: Counting …1234101212345ACBforj←1ton do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|

اسلاید 13: Loop 2: Counting …1234102212345ACBforj←1ton do C[A[j]] ←C[A[j]] + 1// C[k] = |{key = k}|

اسلاید 14: Loop 3: Cumulating…1234102212345ACBforj←2to k do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|12341122C’

اسلاید 15: Loop 3: Cumulating…1234102212345ACBforj←2to k do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|12341132C’

اسلاید 16: Loop 3: Cumulating…1234102212345ACBforj←2to k do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|12341135C’

اسلاید 17: Loop 4: Placement…12341135123453ACBfor 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]]12341125C’

اسلاید 18: Loop 4: Placement…123411351234534ACBfor 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]]12341124C’

اسلاید 19: Loop 4: Placement…1234113512345334ACBfor 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]]12341114C’

اسلاید 20: Loop 4: Placement…12341135123451334ACBfor 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]]12340114C’

اسلاید 21: Loop 4: Placement…123411351234513344ACBfor 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]]12340113C’

اسلاید 22: آناليز الگوريتم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←2to k do C[j] ←C[j] + C[j -1]// C[k] = |{key <= k}|Loop 4:Θ(n)for j←n downto1doB[C[A[j]]] ←A[j]C[A[j]] ←C[A[j]] –1Tootal: Θ(k + n)

اسلاید 23: آناليز الگوريتمif k = Θ(n) T(Countingsort(n))= Θ(n) آيا اين نتيجه تناقضي با حداقل بدست آمده در بخش اول دارد؟توجه كنيد: در اين الگوريتم هيچ مقايسه اي صورت نمي گيرد!نتيجه بدست آمده در بخش اول براي الگوريتم هاي مقايسه اي بود

اسلاید 24: Stable Sorting مرتب سازي پايدار1234513344ABالگوريتم Counting Sort در صورتي كه دو عضو آرايه كليد مساوي داشته باشند، ترتيب آنها را حفظ مي كند. اين نوع الگوريتم را مرتب سازي پايدار مي نامند

اسلاید 25: Radix Sort مرتب سازي ريشه ايHerman Hollerith در سال 1890 ، پيشنهاد كرد.اين الگوريتم، در محاسبات آماري سال 1890 آمريكا بصورت مكانيكي و الكتريكي پياده سازي و استفاده شدنتايج سرشماري دوره قبل 10 سال طول كشيده بود. با استفاده از اين ماشين، گزارشهاي آماري اوليه ظرف 6 هفته! منتشر شداعداد را رقم به رقم و بصورت پايدار مرتب مي كندالگوريتم اوليه از پر ارزشترين رقم شروع مي كندالگوريتم بهبود يافته از پايين ترين ارزش شروع مي كند

اسلاید 26: Radix Sort Example93892375675 4634553027756754553938634923027938027756754634553923

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

اسلاید 28: آناليز الگوريتمبراي مرتب سازي n عدد دهدهي(Decimal Integer) كه ارقام آنها از 0 تا 9 متغير است، لازم است به تعداد ارقام اعداد (مثلا d) فرايند مرتب سازي تكرار شود. با استفاده از Counting Sort بعنوان الگوريتم مرتب سازي ارقام، بسادگي مي توان ديد كه فرايند مرتب سازي هزينه اي برابر Θ(d * (n +k) ) دارد كه در آن k تعداد انواع رقم است(براي اعداد دهدهي ، k=10)مي توان اين الگوريتم را طوري تغيير داد كه در هر فاز بيش از يك رقم را مورد استفاده قرار دهد

اسلاید 29: آناليز الگوريتم، ادامهاعداد در كامپيوتر بصورت باينري ذخيره مي شوند و از آنجاكه عملگرهاي مقايسه اي بيتها در سخت افزار بصورت دستورات cpu پياده شده، هوشمندانه است از ارقام دوديي براي مرتب سازي استفاده شودهنگام استفاده از اعداد باينري، معمولا بيش از 1 بيت بعنوان يك رقم استفاده مي شود.اگر اعداد 32 بيتي را با رقم 4 بيتي مرتب كنيم، 8 بار لازم است فرايند مرتب سازي رو ي ارقام مختلف اجرا شود. Counting Sort 24 يا 16 عدد مختلف را مرتب مي كند

اسلاید 30: آناليز الگوريتم - ادامهاگر n عدد مورد نظر براي مرتب سازي b بيتي باشند و از ارقام r بيتي استفاده كنيم، اين اعداد d=b/r رقم خواهند داشت.آرايه ‍C مورد استفاده در Counting Sort بايد k=2r رقم مختلف را مرتب كند.بنابراين هزينه كل الگوريتم برابر است با:T(n,b) = Θ(d * (n +k) ) = Θ((b/r)(n+2r))بهترين انتخاب r چيست ؟

اسلاید 31: آناليز الگوريتم - ادامه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)

اسلاید 32: بحث و بررسيبراي حجم برزرگ آرايه ها، radixsort كارايي خوبي داردبراي مرتب سازي 2000 عدد 32 بيتي، اين الگوريتم چهار بار تكرار مي شود اما، mergesort و quicksort حداقل 11 بار تكرار مي شوند(عمل تقسيم آرايه به آرايه هاي کوچکتر 11 بار صورت مي گيرد)Quicksort در هر بار تقسيم، ناحيه مراجعه به حافظه را كوچكتر مي سازد. اين ويژگي در پردازنده هاي جديد مجهز به حافظه Cache امتيازي محسوب مي شود. از اين نظر، Q.S. كه خوب طراحي شده باشد، معمولا هم ارز Radix Sort كارايي دارد

اسلاید 33: تكليف و تمريندر اينجا فرض كرديم آرايه هاي مورد نظر براي مرتب سازي، اعداد صحيح هستند؛ به نظر شما براي مرتب سازي اعداد اعشاري چگونه مي توان از اين الگوريتمها بهره گرفت؟ در كتاب، الگوريتم Bucket Sort بدين منظور معرفي شده است. اين الگوريتم را مطالعه كنيد و سعي كنيد راه حل ديگري هم براي اين مساله پيشنهاد كنيد.مسايل بخش 8 را حل كنيد