پژوهش های ریاضی، جلد ۱۱، شماره ۴، صفحات ۴۵-۵۶
عنوان فارسی فرآیند مرتب سازی سریع میانه₋محور
چکیده فارسی مقاله الگوریتم مرتب‌سازی سریع، داده­های ذخیره شده در یک آرایه را مرتب می‌کند. الگوریتم مرتب‌سازی سریع جزئی، کوچکترین l""  عدد از n""  عدد ذخیره شده در یک آرایه را مرتب می‌کند. الگوریتم مرتب‌سازی سریع آنی، ابتدا کوچکترین داده، سپس دومین کوچکترین داده و به همین ترتیب تا آخرین دادۀ یک آرایه را به ترتیب زمانی مرتب می‌کند که اگر در₋l"" امین کوچکترین داده متوقف شویم، آنگاه همان نتیجۀ کار الگوریتم مرتب‌سازی سریع جزئی را ارائه می‌کند. در این مقاله به تحلیل Ynln""  یک نسخۀ استاندارد شدۀ تعداد مقایسه‌های مورد نیاز برای مرتب کردن کوچکترین l""  عدد از n""  عدد ذخیره شده در یک آرایه توسط الگوریتم مرتب‌سازی سریع آنی میانه₋"" محور می‌پردازیم و نشان می‌دهیم که هرگاه l≔nt"" ، t∈0,1""  و n→∞"" ، آنگاه فرآیند Ynt≔Ynntn""  به Yt""  در فضای توابع کدلگ همگرا است.
 
کلیدواژه‌های فارسی مقاله الگوریتم مرتب‌سازی سریع میانه محور، فرآیند شاخه‌ای وزن‌دار، روش انقباض، فضای توابع کدلگ.
عنوان انگلیسی Median Quicksort Process
چکیده انگلیسی مقاله The Quicksort algorithm sorts the data stored in an array. The Partial Quicksort algorithm sorts the l"" smallest numbers out of numbers stored in an array of length n"". The Quicksort on the fly provides online first the smallest, then the second smallest and so on. If we stop at the l""-th smallest, we obtain Partial Quicksort. In this paper, we analyze Ynln"", a correctly normalized version of the number of comparisons needed to sort the l"" smallest numbers out of numbers stored in an array of length n"", by the Median Quicksort algorithm. We show that whenever l≔nt""، t∈0,1""  and n→∞"", then the process Ynt≔Ynntn"" converges to Yt"" in the space of cadlag functions.
 
کلیدواژه‌های انگلیسی مقاله Median Quicksort algorithm, weighted branching process, contraction method, space of cadlag function.
نویسندگان مقاله رامین ایمانی نبیی | Ramin Imany Nabiyyi
University of Tabriz
دانشگاه تبریز

مهری جوانیان | Mehri Javanian
University of Zanjan
دانشگاه زنجان

نشانی اینترنتی http://mmr.khu.ac.ir/browse.php?a_code=A-10-1807-1&slc_lang=fa&sid=1
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده آمار
نوع مقاله منتشر شده علمی پژوهشی بنیادی
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات