الگوریتم مرتب سازی سریع از نوع الگوریتم های تعویضی یا مقایسهای بوده است که بر اساس جابه‌جا کردن زیاد عناصر عمل میکند. در این الگوریتم هر بار عنصری به عنوان pivot یا محور انتخاب می‌شود (بطور پیش فرض عنصر اول آرایه است) در این حالت با استفاده از الگوریتم partition بقیه داده‌های آرایه طوری جابه‌جا می‌شوند که همه‌ی عناصر کوچکتر (یا مساوی) از عنصر لولا یا pivot در یک طرف آن و کلیه عناصر بزرگتر (یا مساوی) در طرف دیگر آن قرار بگیرند. سپس دو آرایه ایجاد شده در دو طرف عنصر لولا یا محور را به همین ترتیب به صورت بازگشتی دوباره مرتب میکنیم و این کار آنقدر ادامه می‌یابد تا به تک عنصر برسیم. این روش مرتب سازی سریع یک روش تقسیم و غلبه‌ای است. بطور کلی الگوریتمها دارای انواع مختلفی هستند که برای آشنایی با آنها میتوانید به صفحه الگوریتم چیستالگوریتم چیست به زبان ساده و با مثال های فراوان
در این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد مراجعه نمایید.
در صورتیکه به این مقاله علاقه‌مند هستید، ممکن است صفحات زیر نیز برای شما جذاب باشد:
- آموزش جامع مرتب سازی ادغامی
- آموزش جامع مرتب سازی حبابی
- آموزش جامع مرتب سازی درجی
بخش‌های روش مرتب سازی سریع (Quick Sort)
QuickSort (A[L..U]) {
If (L < U){
J=partition (A[L..U])
QuickSort (A[L..J-1])
QuickSort (A[J+1..U])
}
}
الگوریتم مرتب سازی سریع از سه بخش تشکیل شده است. ابتدا به وسیله تابع پارتیشن (partition) عنصر محوری یا لولا (pivot) را بر روی آرایه مشخص میکنیم و سپس روی عناصر سمت چپ و راست لولا، تابع مرتب سازی سریع را به صورت بازگشتی فراخوانی میکنیم.لازم به ذکر است آرایه‌ها نوعی از ساختمان داده هستند که برای ذخیره و نگهداری داده‌ها در کامپیوتر استفاده می‌شوند. در مقاله ساختمان دادهآموزش ساختمان داده و الگوریتم
هر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتمها و کاربردها فراهم میکند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است با آرایه و کابردهای آن بیشتر آشنا شوید.
روش اجرای یک گام (مرحله) از الگوریتم مرتب سازی سریع (Quick-sort)
- عنصر اول را به طور پیش‌فرض به عنوان لولا (pivot) در نظر می‌گیریم.
- اندیس‌های i , j به ترتیب از ابتدا و انتها به صورت زیر حرکت می‌کنند:
-
بعد از اجرای مرحله 2:
اندیس i: با شروع از حد پایین به سمت اولین داده‌ای در آرایه حرکت میکند که ${A}\left[\mathrm{i}\right]>=\ \mathrm{pivot}$ باشد.
اندیس j: با شروع از حد بالا به سمت اولین داده‌ای در آرایه حرکت میکند که ${A}\left[\mathrm{j}\right]<=\ \mathrm{pivot}$ باشد.
الف) اگر i < j آن‌گاه مقادیر خانه‌های A[i] و A[j] را جابه‌جا کرده و به مرحله 2 برمی‌گردیم.
ب) اگر i > = j آن‌گاه مقادیر خانه‌های pivot و A[j] را جابه‌جا کرده و مرحله (گام) مورد نظر تمام می‌شود.
$\begin{array}{c}\ \ {{\stackrel{\mathrm{\ \ \ \ i\ \ \ \ }}{\longrightarrow}}}\ \ \ \ \ \ \ \ \ \ \ \ {{\stackrel{\mathrm{\ \ \ \ j\ \ \ \ }}{\longleftarrow}\ \ }} \\ \ \ \underline{\overline{\left|{\mathrm{a}}_{\mathrm{1}}\right|}}\ \ \ \ \ {\mathrm{a}}_{\mathrm{2}}\dots {\mathrm{a}}_{\mathrm{n}}\ \ \\ \begin{array}{c}\ \ \uparrow \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \mathrm{pivot\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } \end{array} \end{array}$
پیچیدگی زمانی الگوریتم مرتب سازی سریع
ما در سه حالت کلی پیچیدگی زمانی این الگوریتم را بررسی خواهیم کرد.
بهترین وضعیت زمان اجرا (مرتبه زمانی) در الگوریتم مرتب سازی سریع (Quick sort)
بهترین وضعیت برای این الگوریتم زمانی است که داده‌ها به صورت نامرتب وارد شوند تا در هر بار در دو طرف عنصر لولا به‌طور متعادل داده‌ها توزیع شوند. در این وضعیت زمان مرتب سازی از مرتبه $\mathrm{O}\left(\mathrm{n\ }\log_\mathrm{2}{\mathrm{n}}\right)$ خواهد بود که زمان وضعیت متوسط نیز خواهد بود. در بهتـرین حالـت، هر بار که پارتیشن انجام می‌شود، آرایه نصف می‌شود و pivot وسط آرایه قرار می‌گیـرد و یا به عبارتی در صورتی که عنصر pivot (لولا یا محور) داده ماکزیمم (بیشینه) یا مینیمم (کمینه) باشد، آن‌گاه آرایه به دو قسمت (0 , n-1) برای چپ و راست تقسیم می‌شود که در این حالت عمق بازگشت n خواهد شد و فضای پشته O(n) خواهد بود.
الگوریتم مرتب سازی سریع دارای میانگین زمانی بسیار مناسبی است و در بین الگوریتمهای مرتب سازی داخلی زمانی که میانگین زمان اجرا مد نظر باشد، بهترین روش مرتب سازی است.
حالت متوسط زمان اجرا (مرتبه زمانی) در الگوریتم مرتب سازی سریع (Quick sort)
برای بدست آوردن حالت متوسط باید همه‌ی حالات (بعد از پارتیشن هیچ عنصری قبل محور قرار نگیرد یا یک عنصر قرار بگیرد یا دو عنصر قرار بگیرد و...) را بررسی کنیم و سپس میانگین بگیریم.
با انجام این کار به عبارت $T\left(n\right)=\frac{(n+1)}{n}T\left(n-1\right)+2\frac{(n-1)}{n}$ می‌رسیم که رابطه‌ی زمان اجرای مرتب سازی سریع در حالت متوسط است. با حل این رابطه، به عبارت زیر می رسیم:
$T\left(n\right)=\left(n+1\right)\frac{T(n)}{n+1}=2(n+1)\ln{n}$
که در نتیجه $T(n)\in\theta\left(n.lgn\right)$ است. یعنی زمان اجرای الگوریتم مرتب سازی سریع در حالت متوسط از مرتبه $\theta\left(n.lgn\right)$ است.
بدترین وضعیت زمان اجرا (مرتبه زمانی) در مرتب سازی سریع (Quick sort)
بدترین وضعیت برای این الگوریتم زمانی است که داده به صورت مرتب یا مرتب معکوس وارد شوند چون هر بار که عنصر اول به عنوان محور انتخاب می‌شود، بقیه داده‌ها یا سمت چپ و یا سمت راست آن قرار می‌گیرد.
در این وضعیت:
- تعداد مقایسات $\frac{\mathrm{n}\left(\mathrm{n}-\mathrm{1}\right)}{\mathrm{2}}$
- مرتبه زمانی $\mathrm{O}\left(\mathrm{n}^\mathrm{2}\right) $
اگر T(n) را زمان اجرای مرتب سازی سریع برای برای یک آرایه با n عنصر در نظر بگیریم و فرض کنیم بعد از اجرای الگوریتم پارتیشن، تعداد عناصر سمت چپ محور یا لولا برابر M شود، می‌توانیم برای T(n) فرمول بازگشتی به صورت $T(n) = T(M) + T(n-M-1) + n-1$ بنویسیم که در آن عبارت $n-1$ زمان اجرای الگوریتم پارتیشن (partition) است و T(n) و $T(n-M-1)$ به ترتیب زمان اجرای مرتب سازی عناصر سمت چپ و راست محور یا لولا هستند.
بدترین حالت به این صورت شکل می‌گیرد که هر بار که عمل پارتیشن انجام می‌شود، یک سمت لولا خالی می‌ماند. برای مثال اگر M برابر با صفر باشد، میتوان نوشت $T(n) = T(n-1) + n-1$ که با درنظر گرفتن شرط اولیه $T(1)=0$ به عبارت $T\left(n\right)=\frac{n(n-1)}{2}$ می‌رسیم. پس در بدترین حالت مرتبه زمانی برای مرتبسازی سریع برابر با $\theta(n^2)$ است. مثال: لیست s که از ۶ = n حرف تشکیل شده به صورت $A , B , C , D , E , F$ میباشد. مقایسه‌های لازم برای مرتب کردن s با الگوریتم Quick sort عبارتست از:
- لیست مرتب و مقایسهای نداریم.
- 36
- 15
- 10
حل: گزینه 3 درست است.
با توجه به مرتب بودن لیست بدترین وضعیت را داریم در نتیجه تعداد مقایسات برابر است با:
$\frac{\mathrm{n}\left(\mathrm{n}-\mathrm{1}\right)}{\mathrm{2}}=\frac{\mathrm{6\ \times\ 5} }{\mathrm{2}}=\mathrm{15}$
مثال دیگری از الگوریتم مرتب سازی سریع (Quick sort)
مثالی دیگر از الگوریتم مرتبسازی سریع را در تصویر زیر مشاهده می‌کنید:
ویژگی های الگوریتم مرتب سازی سریع (Quick-Sort)
-
1- الگوریتم مرتب سازی سریع یک الگوریتم درجا (in place) است به این معنی که به حافظه اضافی نیاز ندارد و به طول آرایه وابستگی ندارد. پس از نظر مصرف حافظه بصرفه است.
-
روش مرتبسازی سریع یک روش ناپایدار (نامتعادل یا unbalanced) است به این معنی که اگر دو عنصر x1 و x2 در آرایه مقدار برابری داشته باشند ترتیب آنها در آرایه مرتب شدهی نهایی لزوما بدون تغییر نخواهد بود.
-
اگر تعداد عناصر آرایه کم باشد، الگوریتم مرتب سازی سریع روش مناسبی نیست و به جای آن بهتر است از روش مرتب سازی درجی استفاده شود.
-
زمان اجرای آن وابستگی زیادی به عنصر محوری (لولا یا pivot) دارد که میتواند عنصر ابتدا یا انتهای آرایه باشد و یا به صورت تصادفی انتخاب شود. انتخاب عنصر محوری مناسب هزینه بالایی دارد.
شبه کد الگوریتم مرتب سازی سریع
Function Quick-sort (var x : arraylist; L , U : integer);
var i , j , pivot : integer;
begin
if L < U then
begin
i : = L; j : = U + 1; pivot : = x[left];
repeat
repeat
i : = i + 1;
until x[i] > = pivot;
repeat
j : = j - 1;
until x[j] < = pivot;
if i < j then swap (x[i] , x[j]);
until i > = j;
swap (x[Left] , x[j]);
Quick-sort (x , L , j – 1);
Quick-sort (x , j + 1, R);
end;
end;
مثالی از نحوه کار الگوریتم مرتب سازی سریع
در انیمشین زیر، نحوه کار الگوریتم مرتب سازی سریع (Quick sort) را مشاهده می‌کنید:
مثال: فرض کنید بخواهیم روش Quicksort را در مورد آرایه زیر به کار ببریم. در اولین مرحله از کار شکل آرایه مطابق کدام گزینه خواهد بود:
21 , 16 , 9 , 32 , 41 , 25
- 16 , 21 , 9 , 25 , 32 , 41
- 41 , 32 , 25 , 21 , 16 , 9
- 41 , 32 , 25 , 16 , 21 , 9
- 41 , 32 , 25 , 9 , 16 , 21
حل: گزینه 3 درست است.
$\mathop{\mathrm{25}}_{\mathop{\uparrow }_{}}\ ,\ \mathop{\mathrm{41}}^{\mathop{\downarrow }^{}}\ ,\ \mathrm{32}\mathrm{\ ,\ }\mathrm{9}\mathrm{\ ,\ }\mathrm{16}\mathrm{\ ,\ }\mathop{\mathrm{21}}^{\mathop{\downarrow }^{}}$
چون $i < j$ است $A[i] با A[j]$ جابه‌جا می‌شود.
$\mathop{\mathrm{25}}_{\mathop{\uparrow }_{}}\ ,\ \mathrm{21}\ ,\ \mathop{\mathrm{32}}^{\mathop{\downarrow }^{}}\mathrm{,\ }\mathrm{9}\mathrm{\ ,\ }\mathop{\mathrm{16}}^{\mathop{\downarrow }^{}}\mathrm{,\ }\mathrm{41}$
چون $i > = j$ است $A[j]$ با pivot جابه‌جا شده و مرحله اول به اتمام می‌رسد.
$\mathop{\mathrm{25}}_{\mathop{\uparrow }_{}}\ ,\ \mathrm{21}\ ,\ \mathrm{16}\mathrm{,\ }\mathop{\mathrm{9}}^{\mathop{\downarrow }^{}}\mathrm{\ ,\ }\mathop{\mathrm{32}}^{\mathop{\downarrow }^{}}\mathrm{,\ }\mathrm{41}$
41 , 32 , 25 , 16 , 21 , 9
مقایسه‌ی الگوریتمهای مرتب سازی
در جدول زیر چند نمونه از الگوریتمهای مرتبسازی را با هم مقایسه میکنیم.
| الگوریتم مرتب سازی | پایدار | حافظه | بهترین زمان اجرا | بدترین زمان اجرا |
|---|---|---|---|---|
| سریع | خیر | O(1) | O(n.lgn) | O(n2) |
| حبابی | بله | O(1) | O(n) | O(n2) |
| انتخابی | خیر | O(1) | O(n2) | O(n2) |
| درجی | بله | O(1) | O(n) | O(n2) |
| دودویی (باینری) | بله | O(1) | O(n.lgn) | O(n2) |
| Shell sort | خیر | O(1) | O(n.lgn) | O(n.lgn) |
| Merge sort | بله | O(n) | O(n.lgn) | O(n.lgn) |
| Radix sort | بله | O(n) | O(n.lgn) | O(n2) |
| شمارشی | بله | O(k+n) | O(k+n) | O(k+n) |
| هرمی | خیر | O(1) | O(n.lgn) | O(n.lgn) |
| درختی | بله | O(n) | O(n.lgn) | O(n2) |
| Bucket sort | بله | O(k) | O(n) | O(n2) |
اگر مایل به آشنایی و مطالعه جزئیات بیشتری در خصوص انواع الگوریتم های مرتب سازی هستید، پیشنهاد میکنیم به کتاب های مرجع ساختمان داده و یا جزوات ساختمان داده مراجعه نمایید و با دانلود راحت و رایگان آنها به مطالب آموزشی دسترسی پیدا کنید.
کد پیاده سازی الگوریتم پارتیشن (Partition)
کد پیاده سازی الگوریتم پارتیشن (Partition) به زبان برنامه نویسی جاوا (Java)
QuickSort (A[L..U]) {
If (L < U){
J=partition (A[L..U])
QuickSort (A[L..J-1])
QuickSort (A[J+1..U])
}
}
int partition(int array[], int low, int high){
int left = low + 1;
int right = high;
int temp;
int pivot = array[low];
while(left <= right){
while(array[left] <= pivot && left <= right)
left = left+1;
while(array[right] > pivot && left <= right)
right = right-1;
if(left < right){
array[left] = array[left] + array[right];
array[right] = array[left] - array[right];
array[left] = array[left] - array[right];
}
}
array[low] = array[right];
array[right] = pivot;
return right;
}
کد پیاده سازی الگوریتم پارتیشن (Partition) به زبان برنامه نویسی پایتون (Python)
def partition(array, low, high):
left, right, pivot = low + 1, high, array[low]
while left <= right:
while array[left] <= pivot and left <= right:
left = left + 1
while array[right] > pivot and left <= right:
right = right - 1
if left < right:
array[left] = array[right]
array[right] = array[left]
array[low] = array[right]
array[right] = pivot
return right
کد پیاده سازی مرتب سازی سریع (Quick Sort)
کد پیاده سازی مرتب سازی سریع (Quick Sort) به زبان جاوا (Java)
// Java implementation of QuickSort
import java.io.*;
class konkurcomputer{
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
static int partition(int[] arr, int low, int high)
{
// pivot
int pivot = arr[high];
// Index of smaller element and
// indicates the right position
// of pivot found so far
int i = (low - 1);
for(int j = low; j <= high - 1; j++)
{
// If current element is smaller
// than the pivot
if (arr[j] < pivot)
{
// Increment index of
// smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index
*/
static void quickSort(int[] arr, int low, int high)
{
if (low < high)
{
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
static void printArray(int[] arr, int size)
{
for(int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 5, 3, 15, 9, 4, 6 };
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
}
کد پیاده سازی الگوریتم مرتب سازی سریع (Quick-sort) به زبان پایتون(Python)
# Python3 implementation of QuickSort
# Function to find the partition position
def partition (arr, l, h):
low, high = l, h
if l != h and l < h:
# Choose the leftmost element as pivot
pivot = arr[l]
low = low+1
# Traverse through all elements
# compare each element with pivot
while low <= high:
if arr[high] < pivot and arr[low] > pivot:
arr[high], arr[low] = arr[low], arr[high]
if not arr[low] > pivot:
low += 1
if not arr[high] < pivot:
high -= 1
arr[l], arr[high] = arr[high], arr[l]
# Return the position from where partition is done
return high
# Function to perform quicksort
def quick_sort(array, low, high):
if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# Recursive call on the left of pivot
quick_sort(array, low, pi - 1)
# Recursive call on the right of pivot
quick_sort(array, pi + 1, high)
# Driver code
array = [2, 1, 9, 8, 7, 1]
quick_sort(array, 0, len(array) - 1)
print(f'Sorted array: {array}')
همچنین به منظور مشاهده خلاصه‌ای از مرتبسازی سریع (Quick sort) میتوانید این ویدئو را مشاهده کنید.
الگوریتم مرتب سازی سریع (Quick Sort) چیست؟
الگوریتم مرتب سازی سریع (Quick Sort) از نوع الگوریتمهای تعویضی یا مقایسهای میباشد. این روش مرتب سازی یک روش تقسیم و غلبه ای است.
پیچیدگی زمانی الگوریتم مرتب سازی سریع چگونه است؟
زمانی که الگوریتم پارتیشن بندی (Partition)، عنصر میانی یا نزدیک به عنصر میانی را به عنوان محور انتخاب میکند، در این حالت ما نظاره گر بهترین پیچیدگی زمانی در این الگوریتم هستیم، که برابر با O(nLogn) است. از آن سو زمانی که الگوریتم پارتیشن بندی (Partition)، بزرگترین و یا کوچکترین عنصر را به عنوان عنصر محوری انتخاب میکند، بدترین حالت پیچیدگی زمانی را میتوان مشاهده کرد، که برابر با O(n2) است.
