مرتب سازی سریع (Quick Sort)
در «مرتب سازی سریع (Quick Sort)» یک «محور (Pivot)» انتخاب می شود. سپس اعداد کوچک تر در چپ قرار می گیرند و اعداد بزرگ تر در راست. بعد همین کار برای زیرآرایه ها، تکراری و بازگشتی انجام می شود.
ایده کوییک سورت با محور
یک مقدار را به عنوان محور برگزین. سپس آرایه را طوری بچین که کوچک ترها چپ باشند و بزرگ ترها راست باشند. آنگاه محور را سرجای درستش بگذار.
پیاده سازی کوییک سورت در پایتون
کد زیر از «تابع بازگشتی (Recursion)» استفاده می کند. بازگشتی یعنی تابع خودش را صدا می زند.
def partition(array, low, high):
pivot = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= pivot:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[high] = array[high], array[i + 1]
return i + 1
def quicksort(array, low = 0, high = None):
if high is None:
high = len(array) - 1
if low < high:
pivot_index = partition(array, low, high)
quicksort(array, low, pivot_index - 1)
quicksort(array, pivot_index + 1, high)
mylist = [64, 34, 25, 5, 22, 11, 90, 12]
quicksort(mylist)
print(mylist)
گام های عملی
- یک محور انتخاب کن.
- کوچک ترها را به چپ بفرست.
- بزرگ ترها را به راست بفرست.
- محور را سرجایش بگذار.
- برای دو زیرآرایه، دوباره انجام بده.
پیچیدگی زمانی
میانگین زمان برابر O(n \log n) است. بدترین حالت برابر O(n^2) است؛ زمانی که محور بد انتخاب شود، مثل آرایه از پیش مرتب.
نکته: برای درک بهتر بازگشت، اول مرتب سازی درج و سپس مرتب سازی حبابی را ببین.
جمع بندی سریع
- محور، آرایه را دو نیم می کند.
- میانگین سریع است؛
O(n \log n). - انتخاب محور خیلی مهم است.
- بازگشتی و مرحله ای کار می کند.
- از روش تقسیم و حل استفاده می کند.