Mathematical Researches

fa فرآیند مرتب سازی سریع میانه₋محور Median Quicksort Process آمار Stat علمی پژوهشی بنیادی S الگوریتم مرتب‌سازی سریع، دادههای ذخیره شده در یک آرایه را مرتب می‌کند. الگوریتم مرتب‌سازی سریع جزئی، کوچکترین <m:omath><m:r>l</m:r></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAYAAAAWCAIAAABseHqEAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAHtJREFUKFNj/P//PwMqYELjA7k4hbanM4JA+nawHqBZIHB7ghWD1YTbICZM4+1rx6zCvFVAiqBCd25dYdBRA4tAhe5sXXXMSksVYjtEFZI2qBCyNogQijaIEIo2sBBU253t6QinbksDKrVKgzj0/39GykICJdBICUJCGgHwLkBNILKLYgAAAABJRU5ErkJggg==" style="width:4.5pt; height:16.5pt" >  عدد از <m:omath><m:r>n</m:r></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAkAAAAWCAIAAACdcyEJAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAHVJREFUKFPdkssRwCAIRCFlaT+kHWwGi9FeyPqJkxy8Z8Jp8a2LjrK706aOHcD6x1hNZ2TmMxPV3CXHVNv5TcWKm1BQFKQXDWggCHcfLYl13XxDd7acdzNsnS3n9M2Exp5oTC6IEgV7JYJhNIW2lf/xDtsfcwF6u3vf8C93qQAAAABJRU5ErkJggg==" style="width:6.75pt; height:16.5pt" >  عدد ذخیره شده در یک آرایه را مرتب می‌کند. الگوریتم مرتب‌سازی سریع آنی، ابتدا کوچکترین داده، سپس دومین کوچکترین داده و به همین ترتیب تا آخرین دادۀ یک آرایه را به ترتیب زمانی مرتب می‌کند که اگر در<m:omath><m:r><m:rpr><m:scr m:val="roman"><m:sty m:val="p"></m:sty></m:scr></m:rpr>₋</m:r><m:r>l</m:r></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAoAAAAUCAIAAAA7jDsBAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAHRJREFUKFNj/P//PwNuwIRHDihFd+nt6YyMjNYT74CcBXQ5JtiWxpC2DSSM1Wl3bl1JC/AEacYmfWfrKgYtVbCPsUnfvnZMR00FEiB4LMZqN9BiK6jR2AwHG82wfSLUY0BPwAHIN2C+1YTbYFsZh1aMISUgAFyoXaTawYtVAAAAAElFTkSuQmCC" style="width:7.5pt; height:15pt" > امین کوچکترین داده متوقف شویم، آنگاه همان نتیجۀ کار الگوریتم مرتب‌سازی سریع جزئی را ارائه می‌کند. در این مقاله به تحلیل <m:omath><m:ssub><m:ssubpr><m:ctrlpr></m:ctrlpr></m:ssubpr><m:e><m:r>Y</m:r></m:e><m:sub><m:r>n</m:r></m:sub></m:ssub><m:d><m:dpr><m:ctrlpr></m:ctrlpr></m:dpr><m:e><m:box><m:boxpr><m:ctrlpr></m:ctrlpr></m:boxpr><m:e><m:argpr><m:argsz m:val="-1"></m:argsz></m:argpr><m:f><m:fpr><m:ctrlpr></m:ctrlpr></m:fpr><m:num><m:r>l</m:r></m:num><m:den><m:r>n</m:r></m:den></m:f></m:e></m:box></m:e></m:d></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAACQAAAAZCAIAAADWhhu8AAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAcRJREFUSEu9VrtxwzAMpTKL48LnCaQJnMobpKPKZICUGUAq4y4buKImSCbwuTC1iwKAokhClKxPzrjz2aIAPHwfnTRNIx4lT48CQpw1YHWVZ1lZU7h1mSWJfcCDqsyyvDIvO4EyLhIlhZBKO1tdpIX3CC+0kmkqlVMRi5DAsWCu4cj327pFRXe8CMxkFYYJWbDEzHtfVzQITmKVewcs+UhaULJoYgwNMyPvflwYTVr4DfHxYnkRlgaJdMXpmzIG9mAYK791YyJhXnvxeqCuEm3POjSaoGjxvZb3GjY+ZZ3zds8ORylO57LKXz933z9vm/FVT3fPc7ngcoOVs0tNaO8v4uMu0lwYTz9gEKm+DvN9JTGJurFg1fkk5HEi1O9V3+MgDrbfQmsMWI1Y0zqx2e6FoA5Mlfp2sb7bwTeWHS3gUBL30Xc46rE9GxtHvmdcVyvYUOQ/olrGRFEGGUbzYhvkRkehgMWIkOXWbrQi3uNLGnLjQEygZCDoh1YBewXJaY3VNlXgdDyN9dHaEAkF3CeV4D6zNBzS8T/dZ6YaHbUhm2JkPh1DjKbjniy6z3jlbcnH6BhtEvhMXZjVemv+8MwGfyjYH58gPU1cuZRTAAAAAElFTkSuQmCC" style="width:27pt; height:18.75pt" >  یک نسخۀ استاندارد شدۀ تعداد مقایسه‌های مورد نیاز برای مرتب کردن کوچکترین <m:omath><m:r>l</m:r></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAYAAAAWCAIAAABseHqEAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAHtJREFUKFNj/P//PwMqYELjA7k4hbanM4JA+nawHqBZIHB7ghWD1YTbICZM4+1rx6zCvFVAiqBCd25dYdBRA4tAhe5sXXXMSksVYjtEFZI2qBCyNogQijaIEIo2sBBU253t6QinbksDKrVKgzj0/39GykICJdBICUJCGgHwLkBNILKLYgAAAABJRU5ErkJggg==" style="width:4.5pt; height:16.5pt" >  عدد از <m:omath><m:r>n</m:r></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAkAAAAWCAIAAACdcyEJAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAHVJREFUKFPdkssRwCAIRCFlaT+kHWwGi9FeyPqJkxy8Z8Jp8a2LjrK706aOHcD6x1hNZ2TmMxPV3CXHVNv5TcWKm1BQFKQXDWggCHcfLYl13XxDd7acdzNsnS3n9M2Exp5oTC6IEgV7JYJhNIW2lf/xDtsfcwF6u3vf8C93qQAAAABJRU5ErkJggg==" style="width:6.75pt; height:16.5pt" >  عدد ذخیره شده در یک آرایه توسط الگوریتم مرتب‌سازی سریع آنی میانه<m:omath><m:r><m:rpr><m:scr m:val="roman"><m:sty m:val="p"></m:sty></m:scr></m:rpr>₋</m:r></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAUAAAAUCAIAAADKh2CMAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAACJJREFUKFNj/P//PwMSYELmANlDjc/wf1sawgtp2xhp7D8APLsJViu6ilgAAAAASUVORK5CYII=" style="width:3.75pt; height:15pt" > محور می‌پردازیم و نشان می‌دهیم که هرگاه <m:omath><m:r>l</m:r><m:r>≔</m:r><m:d><m:dpr><m:begchr m:val="⌈"><m:endchr m:val="⌉"><m:ctrlpr></m:ctrlpr></m:endchr></m:begchr></m:dpr><m:e><m:r>nt</m:r></m:e></m:d></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAADgAAAAWCAIAAAAaQsgPAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAZxJREFUSEvtlj1ygzAQhUXOYlxkcgJxApImVY4ApdNwCjeoxEdwlQZ0AjiBx4XRXciufjA4iMBEOMOM1QCa1e4b7fuEvKZpyBrG0xpEosYlhQoWeHrEfN6G8NisDJiQS5VQPT833YTiNK3BXE0WTojthIQZrqpT2s4poWGGc/TZn5funtGm9fW5oh9vm3uW/lELrWJtqhYqLifysv1XnYLvj5W9qUqoyO0x6N+AzYRhsDOCxUgXbprg8hUSK1SgiP96qEj16eP0wL4qoVMa32HYEHl9moIj1uFsv03KIiKnC2M5SUpkpTrmUinAg5REBTI0zJ6hy8SoSCdDAqqoN0NybEqB6PZd6rwJ7s3hjo413i1dslKaqLMKuYjezbn1W1NR6HiM8ehfW68t1jKLoq86+ddhnGYQqokHf48e+JtdaTdEuZtyYqCaVhtuDxzcQBgAhRok8YLD9yC5UBy9QmjUd5MDl97arv9dRPjbodqw5ifUk9FdQBwIsqUY4mNWuW6CJS8lTkH0HvdRp/u57H3UqdTVePQh1GnfIdk3YxZtCszQnbkAAAAASUVORK5CYII=" style="width:42pt; height:16.5pt" > ، <m:omath><m:r>t</m:r><m:r>∈</m:r><m:d><m:dpr><m:begchr m:val="["><m:endchr m:val="]"><m:ctrlpr></m:ctrlpr></m:endchr></m:begchr></m:dpr><m:e><m:r>0,1</m:r></m:e></m:d></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAADAAAAASCAIAAACSBMrtAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAaFJREFUSEvtVTGWgjAQjZwFLHicIJ4g2mxla5eU0mxnabcNlHAEq20kJ5AT8ChM7uJOICAgcYmr7+3bt9MB8//8+TMJs8vlgn5TOD8XI+PFrArGHyHjrEYvYqngTxAELDgS4HRCHhFEEoBmtIE+R1BfiIxZ5dmC1U0PQ3JIMNmpBYFvjxl+W44zL0Q7cEysi3AzkCQ5Y0ycyyI3mVkJkvwzxb43mgMUekW6kzbPRlFF78RFyN3uaH449kxySZIkZOWb8Q6CnfSWKcpDr12sazpnm72v2m3itIVSd0Kei97XvBR2i+VAIydYKZqpksNy0G6w26p2bSKYa4DnYxtclatGBl2ZBoZQuqxPpQ59OO/WKc6juzxNGwiSxwNar0wu1NZNHpk7D66FRZmbOzXoA0EAUybD9sbDm4280WIfc5uGAZKHHwoi432K605tDjEcz6iaNKZZZ3lbS0RGu4tQX4G9AHz/bYNoGVUF7bSIrnQY04YNtlhzoCG9/bNuCDU1bxiyqC08wt5c0lrQ7A/+XKednqlZr/iXTa09mvcv6Dv7vgBonHYUJ3UBewAAAABJRU5ErkJggg==" style="width:36pt; height:13.5pt" >  و <m:omath><m:r>n</m:r><m:r>→∞</m:r></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAACYAAAASCAIAAAC4tDtCAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAANhJREFUSEvtlNERhCAMROHKwn5iO7lmsBiuF24XTtAbGP3BH82HA7rmZUMGG2M018brWhxpD3JQzwc0dpkni5jmhTV/3rstX8XoxRkjPoa0ME4Dpvg4gkpLiSTimQHpRFWY0IcANRkM41Wxdw7focRq/XIMZbE5fQ28qoXQw4+DEhTihOTDy+qN8EbtEHRjr98i+Vch7pGV0yH2DDdcFufoK4Hobm5nMUmXm2ZChk61D+mf25XlkShDgW2K4jeNT7GfGnh2fk4cdlNinzt2zPUz4PY5KvQeyC81NyynzIFX/AAAAABJRU5ErkJggg==" style="width:28.5pt; height:13.5pt" > ، آنگاه فرآیند <m:omath><m:ssub><m:ssubpr><m:ctrlpr></m:ctrlpr></m:ssubpr><m:e><m:r>Y</m:r></m:e><m:sub><m:r>n</m:r></m:sub></m:ssub><m:d><m:dpr><m:ctrlpr></m:ctrlpr></m:dpr><m:e><m:r>t</m:r></m:e></m:d><m:r>≔</m:r><m:ssub><m:ssubpr><m:ctrlpr></m:ctrlpr></m:ssubpr><m:e><m:r>Y</m:r></m:e><m:sub><m:r>n</m:r></m:sub></m:ssub><m:d><m:dpr><m:ctrlpr></m:ctrlpr></m:dpr><m:e><m:box><m:boxpr><m:ctrlpr></m:ctrlpr></m:boxpr><m:e><m:argpr><m:argsz m:val="-1"></m:argsz></m:argpr><m:f><m:fpr><m:ctrlpr></m:ctrlpr></m:fpr><m:num><m:d><m:dpr><m:begchr m:val="⌈"><m:endchr m:val="⌉"><m:ctrlpr></m:ctrlpr></m:endchr></m:begchr></m:dpr><m:e><m:r>nt</m:r></m:e></m:d></m:num><m:den><m:r>n</m:r></m:den></m:f></m:e></m:box></m:e></m:d></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAGoAAAAZCAIAAABW9SyvAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAA01JREFUaEPtWLFx6zAMlf8sdopcJpAmkNO4SptOKp0B/hBWaXduU7n50gT2BL4UoXbRB0hRpEhQlCjncjmHTWIKIB8eABLgomma6HeEMvAnVPFH61X5AkZeeYyoiwTEkqJ2yt0VfXWVJy0Z8Y41+9RD33J7bspMClVFkuRVn8r7oQ8ibnXaHM/bpT/myLhMt+fj5vQKFKoFZtBXF50vDUAQ9EleGI761mwHROvrju3TPnc8O5MC4komKcys3i6HNZ3ay3R/fLmuNQLh6ggYbBfHGP/u4ZcI2DZUBTMwK5V2mXHwjJUMPsVZySBJW3tgghDVdtYXixqwUwSGpMOasECjhL6FwyoTdKjxht5kwKjQ93XHFVrPLZF/1T/trkq0g6HZFQlVRR4K4fd4By4hh42GixGcOiRn0zgRsO3GjhPMER6HyCLDISZYKa0n6OP8iPBB+gRfXTjhCgOxRXMCSWC6uKV0OMcDqZwCWARDLxasTFUO4TetZj9Fn6JA0Kf4QxqGDSZSUl3u/BTQuB/M3zbIgxjsFvYC5swY4UBx4jyBCDq63Vv6BH87L3ciR4kFHcfhYPpK+rrDjLqcXb6cCzjIaVKpC2hZuKSbLDq8raO//rqIMrL+936JH1fTipN03zTnbRphdeocLjwzAU9DOq7ryEpvIe5YiH1c4pdnX0F6I8xqmTDA2LBNHyR4GX3V6RBlG18XA0ssH56iywfrL4baTw8Ee0Ar/QH1sfOEmjUSraVjuDrO0YBxpz7gsLw16eP2CvpqBDMy+VaPcXT97LV+9edVaNdVAd2G2qj7MBh3Ack7ATD62wQ8Mw00s9prVyyoihesQ+Anr0eMe5+4DuThH2e9AuGr6j51048CfPPy3az7zHDGqpHbju2M6mf0i+f7ug4q9wYB39qLRtfh7C0ERRCAFld+RH6JsCPIqaVKJxvwcPy1NXPJu1d/ld/veZ3lYpvKvIVmpdXDwZSrwuZ9i7PpuzFtWkpId9uAh5xJPhyM8JJq2mxhfIgQ5xh3it8nX0TK6GW9gEXQ0H289XDg2Ja3OHoqyq5jNMyfLOhq8KyHA9JIiCNxF2jjruhzuV4+8VkvOd5YWYDEzCrontVnPNbfM23S9l/6ZkXBf4XICm99yoBJAAAAAElFTkSuQmCC" style="width:79.5pt; height:18.75pt" >  به <m:omath><m:r>Y</m:r><m:d><m:dpr><m:ctrlpr></m:ctrlpr></m:dpr><m:e><m:r>t</m:r></m:e></m:d></m:omath><img alt="" id="_x0000_i1025" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAB4AAAAWCAIAAABYAbuYAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAUxJREFUSEvdlbF1wjAQho/MAhQ8JpAnIGmoMoIoyQAMIZUwQqo0kSeIJ+BRIO2i6CwLS9Zhi4L38uJS9+u7X/L99sxaC895Xp6DReojaCN3VSUNYcbIqtrJelByF1LyaMEYE3pEminAuiXvI+zMFmyr4WrSguIQycDpW1ZsCSVMqOAR64Rjol+iRLS1STs8WWyRJmvFiYax1qN7Nu4YOEyPeZNHbzMyEok7tGeLnOuvq+w6sGukDsO32XI4fbzC4Wc/Lxl18/3ZsNViTJrMNVfHTQnXafSlYe9voy4Cuv46Ad9S4PlyDc1Fpy1Rvl4SZNcyFDzaoPTe+RYrBudrkjRzPXu5qaVLYd/2VsClbjx8lY4F8SJDrBhPEkrM9VTOiPmjtuRpnAIPhuqOPDtbmOsCvFYii1O3rQ1w/2Xwq7N//ysoTFOQPfKX+TvoX9//FIXRJCqBAAAAAElFTkSuQmCC" style="width:22.5pt; height:16.5pt" >  در فضای توابع کدلگ همگرا است.   The Quicksort algorithm sorts the data stored in an array. The Partial Quicksort algorithm sorts the <m:omath><m:r>l</m:r></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAYAAAAWCAIAAABseHqEAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAIZJREFUKFNj/P//PwMqYELjA7k4he5MtGYEgfTtIE1As8BgWxoDg9WE20AWskarMG8VJFUgRWnbwOqhqu7cusJgpaUKsR4scXuCFdQguKrb144x6KiBDYK6C0UbWCOKNojxKNrAGmHa7kxMh7t+W5oVUK1V2jaQ2///Z6QscFDCkZRQRdEIAAuhX8lOSXTVAAAAAElFTkSuQmCC" style="width:6px; height:22px" > smallest numbers out of numbers stored in an array of length <m:omath><m:r>n</m:r></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAoAAAAWCAIAAAB2RJoKAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAJtJREFUKFPdkbsNAjEMhm1mAQrEBMkEdEzhWye0jEBFQ7LBTYAoSHb5sc+ROJCgRriIbH9+hwHQZ1l8YYp+G7cyRGaOh0bUdY5D8ZWySKqoKZCkJJIrJoMk60VA9gBZNDJonInhrjueOXqsJ3v2rNorxXS1ehtJ9jsfpt2vFDYrNwyX8/HpaJfTSNv1Unew6d9LeycKtg/A//qhD9E6hBeWknlWAAAAAElFTkSuQmCC" style="width:10px; height:22px" >. The Quicksort on the fly provides online first the smallest, then the second smallest and so on. If we stop at the <m:omath><m:r>l</m:r></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAYAAAAWCAIAAABseHqEAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAIZJREFUKFNj/P//PwMqYELjA7k4he5MtGYEgfTtIE1As8BgWxoDg9WE20AWskarMG8VJFUgRWnbwOqhqu7cusJgpaUKsR4scXuCFdQguKrb144x6KiBDYK6C0UbWCOKNojxKNrAGmHa7kxMh7t+W5oVUK1V2jaQ2///Z6QscFDCkZRQRdEIAAuhX8lOSXTVAAAAAElFTkSuQmCC" style="width:6px; height:22px" >-th smallest, we obtain Partial Quicksort. In this paper, we analyze <m:omath><m:ssub><m:ssubpr><m:ctrlpr></m:ctrlpr></m:ssubpr><m:e><m:r>Y</m:r></m:e><m:sub><m:r>n</m:r></m:sub></m:ssub><m:d><m:dpr><m:ctrlpr></m:ctrlpr></m:dpr><m:e><m:box><m:boxpr><m:ctrlpr></m:ctrlpr></m:boxpr><m:e><m:argpr><m:argsz m:val="-1"></m:argsz></m:argpr><m:f><m:fpr><m:ctrlpr></m:ctrlpr></m:fpr><m:num><m:r>l</m:r></m:num><m:den><m:r>n</m:r></m:den></m:f></m:e></m:box></m:e></m:d></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAACcAAAAaCAIAAAC7JdIRAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAe9JREFUSEvllj12gzAMgEXPQjLk5QRwgrRLpqzZyNgeIGMPEMZm65qpS+EEzQnyMgTukkrCJgJbFEg71Qtg2fosWT/A9b5RZEkUJVmhaFGkcA80SwCinUY0mvFcAK1zjacWu8hFEsGddZaOpZIitMD1FPrUY32LO5LqNZSOgFDfWa7NU0L1zaM+JPuJhlcB6lahKFD2NLBkK993g8BL9DhR3YsCdZcMvQfkhYslYk+X0lgI5efhmGRfz6GdaD2L8xGi2cSVomA+hTzPPRsnswiO54IlRAUgrJ2BMl0fVsXbQkEClJeTKoP94/oyUfda06oovPmM8vqHFFQd3J37wsWVrRA+rSLYf6Rp/Apb3bW6icMkhmqwL4fVe4drpWoRBv2I8l4s1WTKVo0goTqczl1Q4BvOsvmUI9RSKWwhWeohJBXIcLTz3juVm2TgGypDZTLkmzgI4jQv+SWINzIZOAoGupgdbEwFrhJ1dbKlosiwd3HMJRTP+NaKa7U4aWHcrohd60x1Q2q7zg3Mnr7Vn9bpUE8tpv7OjXRHz0ZH7d/pbl6t3tDpTl+T/ZouhbVTA5f1eEhXF6ZWrYAv2B3mD6YS1DdRN9m/+INpHUJAycEe59gNzSrRr8ooqzA3brnX3QQCxN/FGrX5F20dwP9P1G8O/umqU5I1cQAAAABJRU5ErkJggg==" style="width:39px; height:26px" >, a correctly normalized version of the number of comparisons needed to sort the <m:omath><m:r>l</m:r></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAYAAAAWCAIAAABseHqEAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAIZJREFUKFNj/P//PwMqYELjA7k4he5MtGYEgfTtIE1As8BgWxoDg9WE20AWskarMG8VJFUgRWnbwOqhqu7cusJgpaUKsR4scXuCFdQguKrb144x6KiBDYK6C0UbWCOKNojxKNrAGmHa7kxMh7t+W5oVUK1V2jaQ2///Z6QscFDCkZRQRdEIAAuhX8lOSXTVAAAAAElFTkSuQmCC" style="width:6px; height:22px" > smallest numbers out of numbers stored in an array of length <m:omath><m:r>n</m:r></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAoAAAAWCAIAAAB2RJoKAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAJtJREFUKFPdkbsNAjEMhm1mAQrEBMkEdEzhWye0jEBFQ7LBTYAoSHb5sc+ROJCgRriIbH9+hwHQZ1l8YYp+G7cyRGaOh0bUdY5D8ZWySKqoKZCkJJIrJoMk60VA9gBZNDJonInhrjueOXqsJ3v2rNorxXS1ehtJ9jsfpt2vFDYrNwyX8/HpaJfTSNv1Unew6d9LeycKtg/A//qhD9E6hBeWknlWAAAAAElFTkSuQmCC" style="width:10px; height:22px" >, by the Median Quicksort algorithm. We show that whenever <m:omath><m:r>l</m:r><m:r>≔</m:r><m:d><m:dpr><m:begchr m:val="⌈"><m:endchr m:val="⌉"><m:ctrlpr></m:ctrlpr></m:endchr></m:begchr></m:dpr><m:e><m:r>nt</m:r></m:e></m:d></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD0AAAAWCAIAAAD8awNLAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAbxJREFUWEftVzFygzAQFHmLnSKTF8ALSJpUeQIqncY/SOcGSujSpnJj9AJ4gccF6C+KTkgyKAIzGsEkM1YlAXe7Wt2thoAxhv7heFiDM82iQI4oow6IBKv4ABMRvwpvgZSU/GhZtds48I5ziGVlomM73koQuRmHzGuHdLw3uwr2Ej5t18Z3xevXSfj+6nKIrtDTcVDSE8eveJNjgZ4f/wxtmn0WKHmLR/cmedPmPFElBPwAExcnsAJTgsFghLfIeRBpcUHp7UeNUPEiXMSquuzL03c9p0p6hqaNqTeZ19YEH5p91aZhfTll+ID2FYNFcewcDnHz4GtlQIzlVtW1wXQ+tcgY0JAIwtPCtBVL+EDNleFZ+ECMfCz0nq6SRfpOQKZf0s3bS93vrhl8gDe9VSW6vr3UiVCKQ16Zgin0mnD40i4b8DZ2O6Ev9/mpQrJXoi0fQGqmpryDlyNsOG8VRjM80lgx0M1jfy4JAutLTsnLneWKf26k12SyW03+4trn3YvCpOyaxP8w+9JYiyXHl02qCA0emfaB/LP8ndHmJy64pp8s4hjLJg3u/w3LCmxkX++/we+27rz96nkr2w9KQqSnU5WqYQAAAABJRU5ErkJggg==" style="width:61px; height:22px" >، <m:omath><m:r>t</m:r><m:r>∈</m:r><m:d><m:dpr><m:begchr m:val="["><m:endchr m:val="]"><m:ctrlpr></m:ctrlpr></m:endchr></m:begchr></m:dpr><m:e><m:r>0,1</m:r></m:e></m:d></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAD8AAAAWCAIAAAD4ntN2AAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAe5JREFUWEftVjGSgjAUDXsWsHA8QTiBbLOVrR2U2uwNPACU0m1rLznBcgLGQrgLm58AJhASFOOMM/u7QPL++8nLy3fqukZvGx+2mFeJ7zThJ9X8LCRq4ZyItHDW2LMEYUaPtv7dufPZr48AVWehCGWX/XzSeoTXsq9I1OrJj4hWTxVJIt+kuY496OomKHXJkLxTM5ehaYkIRCIvKDYlCKCMURp4Y4shjxfs03y1MGiOqYmi4Val/MMwmiks+YQYIPY+MAHzeyFHFuMwo1lgwvC//BX1L8JIERPKk0n0F7Axjm/FAw9xPKhiAnuqHHqbpVTHtUI35SVH4Zfqzz03s6+E/FLes3wwl+veyK26FogqtbNchfcaaECKpwdjD9zw0jOBq1SqPCgVkLekynl2APvqfMqR/nq7ixVCxXXum9lHmLBl2oKBvVE3dA5sXX46P07f/dxQhJvOmRaNjmg4rNbv2a6AzyZdEyGtdHc/Mc7320T/xmiyMfrpgQNUyXaf4/ib2QC0RIN3iVVnPG3ePHBN4lBwNKXlh7inXtVdGH9ByrjJJKUCxxO8k7IRs9CBkGTg9xOengem3PFAUEY645eSy+zt9jncY/XdCokOKDO3oU2HHKSiOB1a2bN97HV4dvfedh3/7G3v8Dj+e+/9HyBXBb+AJaI8AAAAAElFTkSuQmCC" style="width:63px; height:22px" >  and <m:omath><m:r>n</m:r><m:r>→∞</m:r></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAADEAAAAWCAIAAADmV+PFAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAATxJREFUSEvtVbtxwzAMBTOLkyoTUBtkEKhMBsgQdJsuS1AbeAJfClO7MPhQH9qRjlKl3BGFjxLAh8f3QNnEGOFg8XQwPkynciozper0r3Xqu7YxxjTnHiCtTdN2ZWeaqgiFEVZiAKdeA/z81bTbI7oQg7OAziH6EOUB0NOXa1t4tJawFsIjg2o6UKkL9EsnsM4HWs56giKkbNpB+RXwFaIMs7CTUllGDp69ogoVQu9df7tS+vv9JE/h5wKvL7q+j64lmxfj7Qvg8vH8h/Hc4RETP1PL1OZ6E/dFyswsFXmbbam6XCeptDw2Y4w6CaeMBRPc69zaPMnI6jyJBjpQYydNC0HmlJ1u0Izqt4k1w1/QmCmoSZNAwdHFsExx0ow43V2zNHyZrLuM3L3JsFYHi/p/V2ZI1anqVKZAWdUv1MsJJAbt5iwAAAAASUVORK5CYII=" style="width:49px; height:22px" >, then the process <m:omath><m:ssub><m:ssubpr><m:ctrlpr></m:ctrlpr></m:ssubpr><m:e><m:r>Y</m:r></m:e><m:sub><m:r>n</m:r></m:sub></m:ssub><m:d><m:dpr><m:ctrlpr></m:ctrlpr></m:dpr><m:e><m:r>t</m:r></m:e></m:d><m:r>≔</m:r><m:ssub><m:ssubpr><m:ctrlpr></m:ctrlpr></m:ssubpr><m:e><m:r>Y</m:r></m:e><m:sub><m:r>n</m:r></m:sub></m:ssub><m:d><m:dpr><m:ctrlpr></m:ctrlpr></m:dpr><m:e><m:box><m:boxpr><m:ctrlpr></m:ctrlpr></m:boxpr><m:e><m:argpr><m:argsz m:val="-1"></m:argsz></m:argpr><m:f><m:fpr><m:ctrlpr></m:ctrlpr></m:fpr><m:num><m:d><m:dpr><m:begchr m:val="⌈"><m:endchr m:val="⌉"><m:ctrlpr></m:ctrlpr></m:endchr></m:begchr></m:dpr><m:e><m:r>nt</m:r></m:e></m:d></m:num><m:den><m:r>n</m:r></m:den></m:f></m:e></m:box></m:e></m:d></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAHIAAAAaCAIAAADkGJ8dAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAA7hJREFUaEPtWT2W2jAQFjkLUPA4gTmBNw3VttuZkj1AynRpoIQu7VY0sU8AJ+BRYN+FzIxkW/+WbHhJNqhZLcyMvvk0P5Jgt/97lHmWJFleDmPBMMKG2fu3tfOMsWRTU1puEgYjy0OcEsKSNhpr9mcYrWW+gc1ugKl4YOUk2wwNhBAfe8kgMQp0+CCM0no5dFD2XbI4gFYDl8U7XNlFey8y7qVE0aayGEIrZHurpNN6uzWU9KaVx3yAl7hUkGCArbuJ2EJCohUrLqU0JCPVBSwUIu+xUPBIMWnlMuAtk6SbsELKaDjpiOIqeAd6sdZ6G47fmmgtrWWelySCfErkaTxaaK15xWiFvdEoJKie5HUR5fj8sbzG47dUAB58UhgBZv4fBK4ooJZaanLE2+AXIHScLmF+vlYiRln16+OU5cf1uP5A+1sc9iyZTfRvq+33PcuWqaGF9veHwmFt8MfR+MvLyYZfBgIuck9gMp+yogD0oDafjllVFA1TJvbJLGGnC9LKGPp9upRcqNq+fbyWO5MdxQYuII1iNRpN3k+M7V9GOFYGidK26WCK7QI1PGA7qI/DX13PXVsJIm3c7F/erhOkY5aAd4sfLHXFW232zGllyDGPp2IFpP50BirxboGV7ppyTRVS3RU0HzIq5Nc9zL2qjUbhJyUtLDR04/VRJCs4drvxebo+4twfcOPpHG2JNsHLzQaPmp3t3V6aoAg5e1zIWaxXv2qU7oB/GIBGm4qriFY2/voK8foOgdqV/VCL+YZoA2PYUnBJCovZY0cMfkLiqUmDkPJUrmnlprJv3uyX19NhYZtzZRYt5cm6prb2LgICWRh+a1j4io/3O9smzGtaiRVbF7dpKR1CCGBAuvR93yn2oaT5UtGTSFH4ebcWHVoA6F0CNIL4KUPQSqjkFC5W0DwW26KiyWihdgvHiYkiGDW2yjkAz2PeHaNesOvsr57kjMNPFeMxVUAkJl0H+NMNVQHer/CaQS0I3krgmgYz49xrNCi678HgKu2IupD1ipke+B/VQ9vLq8sTiY7mxqHIhkDDi8kfemrx43ecZnptqxpC5K7zqaWTVR7Vf+3DYCf+7qiwPrh4iJcsOmltE5/PoC50HmgH7vVd1UPwKy/PxuquBxc7THpY6XzGljabv7toFfOuFDzAWCh+8aOLC4HlwcUmavzoMgKpQcffT60MLx2HJV7EaVIuWZmmHW8lnA/1OvCpOYp3zv7gEmLnGa0hLEXLPKM1mrIQhSetISxFyzxpjaYsROE3aDbkc1Yo65UAAAAASUVORK5CYII=" style="width:114px; height:26px" > converges to <m:omath><m:r>Y</m:r><m:d><m:dpr><m:ctrlpr></m:ctrlpr></m:dpr><m:e><m:r>t</m:r></m:e></m:d></m:omath><img alt="" src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAB4AAAAUCAIAAAAVyRqTAAAAAXNSR0IArs4c6QAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAUJJREFUSEvVlbF1wjAQho/MAhQ8JpAngDRUGUGUMECGkMowAlWayBPEE/AokHYROsvCknXYangvUan79d2ddL89s9bCa9bba7BI/SNoI/dVJQ3Rp5FVtZf1IOTuumRpwRgTekSaKcC6LV9HOJlt2FbD1WQJikMkA6dvWXFJKGFChRoxTlRM5EuUiLY2SYedxSXSZK04kTDWenTPxhODCtM2H/LoNaNCInGH9myRc/11lV0HZo3UYa43Ow6n4xY+fw/zEheZn3PDVosxaWIZrr42JVyn0deGfbyPVhHQ9fcJ+I4Cz5draK46TYny9ZIgu5Qh4NEGpc/6W6wYXG6J08zt4uWmls6FfdpHALe68fBR2hbEQwZbMZ44lJjrKZ8R80cdyd04BR4M1RN51luY6wK8ViKzU3esNXD/ZfC7s3/5l7kDHUcUgSq0fLIAAAAASUVORK5CYII=" style="width:30px; height:20px" > in the space of cadlag functions.   الگوریتم مرتب‌سازی سریع میانه محور, فرآیند شاخه‌ای وزن‌دار, روش انقباض, فضای توابع کدلگ. Median Quicksort algorithm, weighted branching process, contraction method, space of cadlag function. 45 56 http://mmr.khu.ac.ir/browse.php?a_code=A-10-1807-1&slc_lang=fa&sid=1 Ramin Imany Nabiyyi رامین ایمانی نبیی imany@tabrizu.ac.ir 10031947532846006966 10031947532846006966 Yes University of Tabriz دانشگاه تبریز Mehri Javanian مهری جوانیان javanian@znu.ac.ir 10031947532846006967 10031947532846006967 No University of Zanjan دانشگاه زنجان