کوییک سورت ( به انگلیسی: Quicksort ) ، یکی از الگوریتم های مرتب سازی است که به دلیل مصرف حافظه کم، سرعت اجرای مناسب و پیاده سازی ساده بسیار مورد قبول واقع شده است.
هر پیاده سازی این الگوریتم به صورت کلی از دو بخش تشکیل شده است. یک بخش تقسیم بندی آرایه ( partition ) و قسمت مرتب کردن. روش مرتب سازی سریع ( Quick Sort ) یکی از الگوریتم های مشهور مرتب سازی داده ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده ها ارائه می نماید:
۱ - انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری ( pivot ) - به عنوان مثال عنصر اول - انتخاب می شود.
۲ - تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه های چپ و راست نامیده می شوند.
۳ - مرتب سازی بازگشتی: زیر آرایه های چپ و راست به روش مرتب سازی سریع مرتب می شوند.
مراحل مختلف ( Partition ( 1, 10 را بر روی داده های زیر بنویسید.
i، ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰، i، P
A، ۶۵، ۷۰، ۷۵، ۸۰، ۸۵، ۶۰، ۵۵، ۵۰، ۴۵، ∞، ۲، ۹
جا به جایی ۴۵ با ۷۰: ۹ ، ۲، ∞ ، ۷۰ ، ۵۰ ، ۵۵ ، ۶۰، ۸۵ ، ۸۰ ، ۷۵، ۴۵ ، ۶۵
جا به جایی ۷۵ با ۵۰: ۸ ، ۳، ∞ ، ۷۰ ، ۷۵ ، ۵۵ ، ۶۰ ، ۸۵ ، ۸۰ ، ۵۰ ، ۴۵ ، ۶۵
جا به جایی ۸۰ با ۵۵: ۷ ، ۴، ∞، ۷۰ ، ۵۰ ، ۸۰ ، ۶۰ ، ۸۵ ، ۵۵ ، ۷۵ ، ۴۵ ، ۶۵
جا به جایی ۸۵ با ۶۰: ۶ ، ۵، ∞ ، ۷۰ ، ۵۰ ، ۸۰ ، ۸۵ ، ۶۰ ، ۵۵ ، ۷۵ ، ۴۵ ، ۶۵
جا به جایی ۶۵ با ۶۰: ۵ ، ۶، ∞ ، ۷۰ ، ۵۰ ، ۸۰ ، ۸۵ ، ۶۵ ، ۵۵ ، ۷۵ ، ۴۵ ، ۶۰
فرض کنید که بعد از فراخوانی الگوریتم Partition عنصر افراز در مکان j ام قرار بگیرد، در این صورت بدیهی است که j - 1 عنصر آرایهٔ کوچکتر یا مساوی A است و n - j عنصر باقی مانده بزرگتر یا مساوی آن خواهد بود؛ بنابراین سه حالت زیر امکان پذیر است:
اگر k< j آنگاه kامین عنصر کوچکتر آرایه در A قرار دارد.
اگر k=j آنگاه A، عنصر Kامین عنصر کوچکتر است.
اگر k> j آنگاه kامین عنصر کوچک تر آرایه برابر k - jامین عنصر کوچکتر آرایهٔ A خواهد بود.
مطالب گفته شده توسط الگوریتم Selection در زیر ارائه شده است:
Algorithm Select ( k ) m=1 , r=n+1 , A= ∞ Loop { j=r partition ( m , j ) if k=j then Return ( A ) else if k< j then r=j else m=j+1 } شبه کد آرایه[A[p. . r، عنصر آخر هربار به عنوان pivot قرار می گیرد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفهر پیاده سازی این الگوریتم به صورت کلی از دو بخش تشکیل شده است. یک بخش تقسیم بندی آرایه ( partition ) و قسمت مرتب کردن. روش مرتب سازی سریع ( Quick Sort ) یکی از الگوریتم های مشهور مرتب سازی داده ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده ها ارائه می نماید:
۱ - انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری ( pivot ) - به عنوان مثال عنصر اول - انتخاب می شود.
۲ - تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه های چپ و راست نامیده می شوند.
۳ - مرتب سازی بازگشتی: زیر آرایه های چپ و راست به روش مرتب سازی سریع مرتب می شوند.
مراحل مختلف ( Partition ( 1, 10 را بر روی داده های زیر بنویسید.
i، ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰، i، P
A، ۶۵، ۷۰، ۷۵، ۸۰، ۸۵، ۶۰، ۵۵، ۵۰، ۴۵، ∞، ۲، ۹
جا به جایی ۴۵ با ۷۰: ۹ ، ۲، ∞ ، ۷۰ ، ۵۰ ، ۵۵ ، ۶۰، ۸۵ ، ۸۰ ، ۷۵، ۴۵ ، ۶۵
جا به جایی ۷۵ با ۵۰: ۸ ، ۳، ∞ ، ۷۰ ، ۷۵ ، ۵۵ ، ۶۰ ، ۸۵ ، ۸۰ ، ۵۰ ، ۴۵ ، ۶۵
جا به جایی ۸۰ با ۵۵: ۷ ، ۴، ∞، ۷۰ ، ۵۰ ، ۸۰ ، ۶۰ ، ۸۵ ، ۵۵ ، ۷۵ ، ۴۵ ، ۶۵
جا به جایی ۸۵ با ۶۰: ۶ ، ۵، ∞ ، ۷۰ ، ۵۰ ، ۸۰ ، ۸۵ ، ۶۰ ، ۵۵ ، ۷۵ ، ۴۵ ، ۶۵
جا به جایی ۶۵ با ۶۰: ۵ ، ۶، ∞ ، ۷۰ ، ۵۰ ، ۸۰ ، ۸۵ ، ۶۵ ، ۵۵ ، ۷۵ ، ۴۵ ، ۶۰
فرض کنید که بعد از فراخوانی الگوریتم Partition عنصر افراز در مکان j ام قرار بگیرد، در این صورت بدیهی است که j - 1 عنصر آرایهٔ کوچکتر یا مساوی A است و n - j عنصر باقی مانده بزرگتر یا مساوی آن خواهد بود؛ بنابراین سه حالت زیر امکان پذیر است:
اگر k< j آنگاه kامین عنصر کوچکتر آرایه در A قرار دارد.
اگر k=j آنگاه A، عنصر Kامین عنصر کوچکتر است.
اگر k> j آنگاه kامین عنصر کوچک تر آرایه برابر k - jامین عنصر کوچکتر آرایهٔ A خواهد بود.
مطالب گفته شده توسط الگوریتم Selection در زیر ارائه شده است:
Algorithm Select ( k ) m=1 , r=n+1 , A= ∞ Loop { j=r partition ( m , j ) if k=j then Return ( A ) else if k< j then r=j else m=j+1 } شبه کد آرایه[A[p. . r، عنصر آخر هربار به عنوان pivot قرار می گیرد.
wiki: مرتب سازی سریع