دانلود کتاب Quicksort

ترجمه فارسی توضیحات (ترجمه ماشینی)

مرتب سازی سریع

یک مطالعه کامل از بهترین روش هدف کلی برای مرتب‌سازی توسط کامپیوتر ارائه شده است: الگوریتم Quicksort C. A. R. Hoare. توجه ویژه ای به روش های تحلیل ریاضی است که برای نشان دادن کاربرد عملی الگوریتم استفاده می شود. کارآمدترین شکل شناخته شده Quicksort توسعه یافته است و فرمول های دقیقی برای میانگین، بهترین حالت و بدترین زمان اجرا به دست آمده است. مزایای بسیاری از تغییراتی که برای بهبود مرتب‌سازی سریع پیشنهاد شده‌اند، با تأکید بر تأثیر آنها بر تجزیه و تحلیل مورد بحث قرار گرفته‌اند. روش Van Emden، مرتب‌سازی نمونه، و اصلاح میانه سه به تفصیل مورد بحث قرار گرفته‌اند و نشان داده شده است که دومی موثرترین بهبود به Quicksort برای کاربردهای مرتب‌سازی عملی است.

Quicksort

A complete study is presented of the best general purpose method for sorting by computer: C. A. R. Hoare’s Quicksort algorithm. Special attention is paid to the methods of mathematical analysis which are used to demonstrate the practical utility of the algorithm. The most efficient known form of Quicksort is developed, and exact formulas are derived for the average, best case, and worst case running times. The merits of the many modifications which have been suggested to improve Quicksort are discussed, with an emphasis on their impact upon the analysis. Van Emden’s method, samplesort, and the median-of-three modification are discussed in detail, and it is shown that the latter is the most effective improvement to Quicksort for practical sorting applications.