یکی از روش های مرتب سازی داده ها، استفاده از الگوریتم مرتب سازی به صورت ادغامی است. این الگوریتم از روش تقسیم و حل برای مرتب کردن داده ها استفاده می کند. در روش تقسیم و حل، یک مساله به تعدادی مساله کوچک تر تقسیم می شود که حل آنها ساده تر از حل مساله اصلی است و ادغام نتایج به دست آمده از مسائل کوچک تر جواب مساله اصلی است. در الگوریتم مرتب سازی به روش ادغامی نیز همین گونه است. داده ها به مجموعه ای کوچک تر شکسته شده و مرتب می شوند. سپس از ادغام فهرست های مرتب شده به فهرست مرتب شده اصلی می رسیم. این الگوریتم اولین بار در سال 1945 توسط جان فون نویمان مطرح شد.
روش کار الگوریتم مرتب سازی ادغامی
ابتدا فهرستی از داده ها که قرار است مرتب شوند به 2 فهرست به طول مساوی تقسیم می شوند و سپس فهرست های تولید شده به روش بازگشتی با صدا زدن تابع mergsort هر کدام به دو زیرفهرست تقسیم می شوند. این عمل آنقدر ادامه پیدا می کند تا به فهرست هایی برسیم که طول هر کدام ? باشد.
تمام زیرفهرست های تولیدشده مرتب می شوند و سپس از پایین به بالا با فهرست های مجاور خود ادغام شده و فهرست جدیدی تولید می شود. این فهرست ها نیز با فهرست های مجاور خود ادغام می شوند. آن قدر این فهرست ها با هم ترکیب می شوند تا به فهرست نهایی برسیم. در هر ادغام مرتب بودن داده ها حفظ می شود. حال این روش را با یک مثال توضیح می دهیم.
فرض کنید داده های ما مجموعه ای به نام a است که به صورت زیر تعریف شده است:
a = { 5,2,4,7,1,3,2,6}
ابتدا مجموعه a را به 2 زیرمجموعه با طول یکسان به نام های a1و a2 تقسیم می کنیم:
a1={5,2,4,7}, a2={ 1,3,2,6}
سپس هر کدام از این مجموعه ها را به 2 مجموعه با طول مساوی تقسیم کرده و در نهایت به ? مجموعه به صورت زیر می رسیم:
b={5,2}, c={4,7}, d={1,3}, e={2,6}
از مجموعه های بالا فقط مجموعه b نیاز به مرتب سازی دارد. پس از مرتب کردن جدول b باید مجموعه ها را با هم ادغام کنیم.
عمل ادغام به این صورت است که ابتدا اولین عنصر از هر دو مجموعه را با هم مقایسه کرده و عنصر کوچک تر را در مجموعه سومی قرار می دهیم که همان خروجی این مرحله است. سپس عنصر بعدی را از همان مجموعه ای انتخاب می کنیم که عنصر اول که در مجموعه سوم قرار گرفته است. سپس این عمل را آنقدر ادامه می دهیم که تمامی عناصر یکی از 2 مجموعه در مجموعه سومی که نتیجه حاصل از ادغام دو مجموعه در آن ذخیره شده است، قرار بگیرد. سپس باقی عناصر مجموعه دوم به ترتیب به مجموعه سوم منتقل می شود.
شبه کد این الگوریتم به صورت زیر است:
function merge_sort(m) {
var list left, right, result
if length(m) «= 1
return m
var middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result
}
function merge(left, right) {
var list result
while length(left) » 0 and length(right) » 0
if first(left)«=first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
while length(left) » 0
append left to result
while length(right) » 0
append right to result
return result}
پیچیدگی زمانی الگوریتم مرتب سازی ادغامی
اگر زمان لازم برای مرتب سازی آرایه n عضوی به روش ادغام برابر (t(n باشد داریم:
t(n) = 2t(n/2) + n
در این الگوریتم در هر مرحله آرایه به 2 آرایه شکسته می شود و در هر مرحله از ادغام نیز باید n مقایسه صورت بگیرد.
در نتیجه در بدترین حالت تعداد مقایسه های این الگوریتم برابر (n[log n] -2[log n] +1) است و چون عمل غالب در این الگوریتم مانند باقی الگوریتم های مرتب سازی عمل مقایسه است. پس مرتبه اجرایی این الگوریتم برابر (o(nlogn است. این الگوریتم در بدترین حالت ?? بار سریع تر از الگوریتم مرتب سازی حبابی (bubble sort) است. در جاهایی بدترین حالت این الگوریتم از لحاظ زمانی برابر بهترین حالت الگوریتم سریع (quick sort) با داده های یکسان است.
امیربهاالدین سبط الشیخ
ریاضیات بیتی
... راه حل این مساله، استفاده از آرایه است که در شماره های قبلی در مورد آن توضیح داده شد ... یعنی !1000 را با یک آرایه پیاده سازی کنیم و همین طور !1001 و اعداد دیگر و اعمال ریاضی را روی این اعداد انجام دهیم ...
بهتر از این هم می شود کار کرد!
... 0; y = power3a*x*x + power2b*i; } 2 ارجعات به عناصر آرایه اگر هنگام کدنویسی دقت لازم را نداشته باشیم این محاسبات اضافه که در بالا توضیح داده شد، به پردازش عناصر یک آرایه نیز سرایت می کند و باعث کندی اجرای قطعه کد ما و اتلاف زمان پردازشگر شود ... بگزارید این موضوع را با یک مثال نشان دهیم: فرض کنید دنبال دانشجویانی با اسم “آرش” می گردیم، یک راه این است که “آرش” را با نام همه دانشجویان مقایسه کنیم و کسانی که اسم آنها “آرش” است را در یک لیست ذخیره کنیم، این راه درست است و مشکلی ندارد ولی آیا این راه یک راه بهینه برای حل مساله است؟ پاسخ خیر است، چون در بدترین حالت نام های “آرش” در انتهای لیست هستند و برای یافتن فهرست آنها نیازمند پردازش کل آرایه تا انتها است ... درست است ما یک زمان اضافی برای مرتب سازی آرایه ها صرف کردیم ولی در دفعات بعد برای داده های دیگر نیازی به این عمل نیست چون فقط یک بار داده ها مرتب می شوند و در دفعات بعدی از نتیجه مرتب سازی استفاده می شود ...
عبارات ریاضی در کامپیوتر
... در مورد پشته پیش از این صحبت کردیم، اما برای یاد آوری:پشته یک آرایه است که از ساختار lifo (last input first output) پیروی می کند، یعنی اولین عنصر ورودی آخرین عنصر خروجی است ...
سری اعداد فیبوناچی
... کد روش بازگشتی به صورت زیر است: long fibonaccirecursive(int no) { if ((no == 1) || (no == 2)) return 1; else if (no == 0) return 0; else return fibonaccirecursive(no - 1) + fibonaccirecursive(no - 2); } در هر دو روش ممکن است عدد فیبوناچی حاصل بقدری بزرگ باشد که در متغیر های معمول زبان های برنامه نویسی جای نگیرد، آن وقت تکلیف چیست؟ برای حل این مشکل باید عدد حاصل را یک آرایه تعریف کرده و فرض کنید هر رقم از آرایه یک رقم از عدد است ...
نگاهی به مجموعه نرم افزار koffice2/0
... اگر کاربران در نخستین مواجهه با آرایه ای از dockerها، دچار وحشت یا اضطراب نشوند، دراین صورت به مرور خواهند دید که 2 /0 koffice همه چیز بیشتر در دسترس بوده و در مقایسه با نسخه های قبلی استفاده از آن ها نیز آسان تر است ...
انواع فناوریlcd
... smectic پرکاربردترین آرایه در بین کریستال های مایع nematic است ... کریستالهای مایع فروالکتریک(flc ها) در آرایه ای به همراه مولکول های semectic نوع c از کریستال های مایعی که دارای مولکول های chiral هستند، استفاده می کنند، زیرا طبیعت مارپیچی آن ها اجازه می دهد که وضعیت قرارگیری مولکول ها را در کسری از ثانیه تغییر دهند به همین دلیل flc ها برای استفاده در نمایشگرهای پیشرفته که تصاویرمتحرک با نرخ نوسازی بالا را پخش می کنند، بسیار مناسب هستند ...
انواع raid در سرورها
... در این مقاله پیکربندی آرایه ای و برنامه ای،برای چندین هارد دیسک ارزان قیمت برای داشتن قابلیت fault telorance یا همان کاهش نرخ خطا و همچنین بهبود و افزایش نرخ دسترسی داده ها مهیا شد ...
20 پروژه تحقیقاتی کامپیوتری (2)
... محققان دانشگاه ماساچوست امرس شیوه ای را برای ردیف کردن نوع خاصی از مولکول ها در قالب آرایه های کاملی در نواحی به نسبت گسترده ابداع کرده اند ...
بازی بزرگان
... یکی از ساده ترین روش ها، ذخیره سازی ارقام اعداد در آرایه و انجام عملیات مورد نظر روی آرایه هاست ... حالا بیایید ببینیم که چگونه 2عدد بزرگ را که در آرایه ذخیره شده اند با هم جمع کنیم ... ما اعداد را به صورت آرایه ای از کاراکترها از کاربر دریافت می کنیم ... این عدد به این صورت در آرایه قرار گرفته است: 4خانه باقی مانده بلااستفاده هستند ... ما توسط تابع reverse خانه های آرایه را جابه جا می کنیم و سپس به اندازه اختلاف طول 2عدد با طول بیشتر یا همان len در کد بالا صفر اضافه می کنیم ... در نهایت، حاصل جمع 2عدد در آرایه num1 قرار می گیرد و سپس باید num1 نیز بر عکس شود تا حاصل، نتیجه دلخواه ما باشد ...
|
صفحه 1
|
2 | 3 | 4 |
|
