مرتب سازی سریع یا QuickSort الگوریتمی برای مرتب سازی است که در سال 1960 توسط C.A.R Hoare دانشمند کامپپوتر انگلیسی ابداع شد. این روش به علت سرعت مناسب در لیست های بزرگ و پیاده سازی آسان بسیار مورد استفاده قرار می گیرد. در ادامه نگاهی به شیوه مرتب سازی و نحوه ی پیاده سازی این لگوریتم می اندازیم.
این الگوریتم برای مرتب سازی از متدی به نام "تقسیم و حل" استفاده می کند. به زبان ساده "تقسیم و حل" به معنی خرد کردن یک مسئله به اجزای کوچکتر (و ساده تر) و حل اجزای ساده است و در نهایت به وسیله حل تمام اجزای ساده به حل کل مسئله می رسیم. در مرتب سازی سریع نیز لیست یا آرایه عناصر مورد نظر را در هر مرحله به قطعات کوچکتر تقسیم می کنیم و سپس عملیات مورد نظر را روی آنها انجام می دهیم.

در اولین قدم، یک عنصر دلخواه از لیست را انتخاب می کنیم (بهتر است این عنصر از خانه های وسط لیست باشد)؛ به این عنصر به "عنصر محوری" یا "Pivot element" معروف است. در قدم بعدی تمام عناصر کوچکتر از Pivot را به طرف چپ آن منتقل می کنیم. به این ترتیب تمام عناصر بزرگتر از Pivot نیز به طرف راست آن منتقل خواهند شد. تمام عملیات مرتب سازی سریع از تکرار این دو مرحله تا پایان حاصل می شود. خب گفیتم که تمام عناصر کوچکتر را به طرف چپ و تمام بزرگتر ها را به طرف راست Pivot آوردیم. با این کار لیست اولیه ما به دو لیست کوچکتر تقسیم خواهد شد. می توانیم آنها را لیست چپ و لیست راست بنامیم. برای مرتب سازی کامل لیست کافی است دو باره دو مرحله بالا را برای لیست چپ و لیست راست تکرار کنید . یعنی از هر دو لیست به ترتیب یک عنصر به عنوان عنصر Pivot انتخب کنید و دو باره عناصر کوچکتر را به چپ و عناصر بزرگتر را به سمت راست Pivot منتقل کنید. هر بار که این کار را تکرار کنید لیست های چپ و راست هر کدام به دو لیست کوچکتر تقسیم می شوند که دو باره می توانید آنها را چپ و راست بنامیم.

در هر مرحله عنصر Pivot در مکان صحیح و نهایی خود قرار می گیرد و باید مراحل بالا را تا زمانی که لیست چپ و راست بیش از یک خانه (یا عنصر) دارند ادامه دهید. هنگامی که دیگر لیست های چپ و راست مرحله آخر هر کدام یک خانه دارند دیگر کل لیست مرتب شده است و نیازی نیست عملیات مرتب سازی ادامه پیدا کند.

پس به طور خلاصه سه کار را در هر مرحله انجام می دهیم، ابتدا یک عنصری دلخواه از لیست را انتخاب می کنیم که به آن عنصر محوری یا Pivot گفته می شود. سپس عناصر کوچکتر از Pivot را به طرف چپ آن منتقل می کنیم. لیست به دو بخش از (ابتدا تا Pivot-1 ) و از ( Pivot+1 تا انتها) ( عنصر Pivot دیگر تغییر نخواهد کرد) تقسیم شده است. در مرحله بعد، دو مرحله ی قبل را برای هر دو بخش جدید تکرار می کنیم.
برای اینکه عناصر کوچکتر از Pivot را به سمت چپ آن منتقل کنید از روش های مختلفی می توانید استفاده کنید ولی یکی از بهترین ها روش زیر است :
عنصر Pivot را به انتهای لیست منتقل کنید. ( جای Pivot و خانه ی آخر لیست را عوض کنید)
یک متغیر به نام دلخواه ( برای مثال position ) برای نگه داری مکان فعلی بررسی تعریف کنید و مقدار اولیه آن را ایندکس خانه ابتدای لیست قرار دهید.
از ابتدا تا انتهای لیست اگر هر عنصر کوچکتر از Pivot بود ، آنگاه جای آن را با عنصر خانه ی position عوض کنید و یک واحد به position اضافه کنید.
به زبان برنامه نویسی ( a[ ] لیست مورد نظر است) : if (a[i] < Pivot) swap (a[position++] , a[i])
در آخر جای Pivot (که همان خانه ی آخر لیست است) را با خانه ی position عوض کنید. (دقت کنید که position ایندکس خانه است نه مقدار آن)
با انجام این مراحل تمام عناصر کوچکتر از Pivot به سمت چپ و تمام بزرگتر ها به سمت راست آن منتثل می شوند.
wikipedia.org