مرتب سازی سریع به عنوان یک روش برنامه نویسی

در سال 1960، K. A. Hoare یک روش مرتب سازی سریع اطلاعات را، که معروف ترین آن بود، توسعه داد. امروزه به طور گسترده ای در برنامه نویسی مورد استفاده قرار می گیرد، زیرا دارای ویژگی های مثبت زیادی است: می توان آن را برای موارد عمومی استفاده کرد، نیاز به افزایش کوچک در حافظه اضافی دارد، با انواع مختلف لیست سازگار است و برای اجرای مناسب است. اما ضعف هایی نیز وجود دارد که مرتب سازی سریع است: زمانی که در کار استفاده می شود خطاهای زیادی را به وجود آورده است و تا حدودی ناپایدار است.

با این حال، این مورد بیشتر مورد مطالعه است. پس از ظهور اولین محاسبات هوار، بسیاری از آنها در مطالعه متراکم خود مشغول به کار بودند. یک پایگاه بزرگ در مورد سوالات نظری پیدا کردن زمان صرف شده برای کار ایجاد شده است، که توسط داده های تجربی پشتیبانی می شود. پیشنهادات واقعی برای بهبود الگوریتم اصلی و افزایش سرعت کار وجود دارد.

مرتب سازی سریع بسیار رایج است، می توان آن را در همه جا پیدا کرد. این بر اساس روش TList.Sort است که در همه نسخه ها (به جز 1) از Delphi، تابع کتابخانه زمان انجام شده اجرا، qsort در C ++ وجود دارد.

اصل اساسی کار می تواند به عنوان "تقسیم و تسخیر" فرموله شود. تجزیه لیست به دو گروه و مرتب سازی برای هر بخشی به صورت خود انجام می شود. به این ترتیب توجه بیشتری به پروسه جداسازی داده می شود که طی آن رخ می دهد: عنصر پایه تعیین می شود و کل لیست در حال حاضر نسبت به آن تغییر یافته است. گروهی از نامزدها به سمت چپ شکل می گیرند، ارزش های آنها کوچکتر است، همه دیگران به سمت راست منتقل می شوند. به نظر می رسد که عنصر اصلی در فهرست مرتب شده در محل قانونی آن قرار دارد. گام بعدی این است که با تابع مرتب سازی مجدد برای هر دو طرف عناصر نسبت به پایه تماس بگیرید. روند کار به پایان می رسد تنها زمانی که لیست تنها شامل یک عنصر است، یعنی آن را مرتب خواهد شد. بنابراین، برای به دست آوردن چنین کارکرد برنامه نویسی به صورت مرتب سازی سریع، ضروری است که عملیات الگوریتم های سطح پایین را بدانیم: الف) انتخاب عنصر پایه؛ ب) موثرترین جایگزینی برای لیست برای به دست آوردن دو مجموعه با مقادیر کوچکتر و بزرگتر.

ما با اصول اول آشنا خواهیم شد. هنگام انتخاب یک عنصر پایه ای، به طور ایده آل میانی باید از لیست انتخاب شود. سپس، زمانی که شکسته شده است، آن را به دو نیمه برابر تقسیم شده است. تنها مقدار محاسبه شده در لیست بسیار دشوار است، بنابراین حتی سریع ترین مرتب سازی، این محاسبات را کنار می گذارد. اما انتخاب عنصر اصلی با حداکثر یا حداقل مقدار نیز بهترین گزینه نیست. در مورد چنین تعریفی، یکی از لیست های ایجاد شده تضمین می شود که خالی باشند، و دوم آن را سرریز می کند. از این رو نتیجه می گیریم که به عنوان عنصر پایه باید یکی از آن را نزدیک تر به میانگین، اما بیشتر از حداکثر و حداقل.

پس از تصمیم گیری در انتخاب، می توانید به عملیات الگوریتم پارتیشن بندی بروید. این چرخه های به اصطلاح داخلی داخلی سریع است. همه چیز بر روی دو شاخص سریع عمل ساخته شده است: اولین عناصر از چپ به راست، و دوم، برعکس، از راست به چپ. عملیات اعدام در سمت راست شروع می شود: شاخص از لیست عبور می کند و تمام مقادیر را با یکی از اصلی مقایسه می کند. یک چرخه کامل در نظر گرفته شده است اگر یک عنصر کمتر یا برابر با یک پایه وجود داشته باشد. بدین معنی که ارزش شاخص را مقایسه و کاهش می دهد. در سمت چپ، وقتی یک مقدار بیشتر یا برابر یافت می شود، کار پایان می یابد. و در اینجا ارزش مقایسه را افزایش می دهد.

در این مرحله از الگوریتم پارتیشن بندی که حاوی مرتب سازی سریع است، دو حالت ممکن بوجود می آیند. اول این است که شاخص در سمت چپ کمتر از راست است. این نشان دهنده یک خطا است، یعنی مواردی که مشخص شده است در فهرست اشتباه هستند. راه خروج در حال تغییر مکان است وضعیت دوم زمانی است که هر دو ستون برابر یا متقاطع باشند. این نشان می دهد که جدایی جدی از لیست، یعنی کار کامل می تواند در نظر گرفته شود.