کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

آموزش مرتب سازی سریع (quick sort) بصورت 0 تا 100

این صفحه مرتب سازی سریع (quick sort) را بصورت 0 تا 100 آموزش داده و مثال مرتب سازی سریع آورده شده است، همچنین بهترین، متوسط و بدترین حالت مرتب سازی سریع بررسی شده

الگوریتم مرتب ‌سازی سریع از نوع الگوریتم ‌های تعویضی یا مقایسه­‌ای بوده است که بر اساس جابه‌جا کردن زیاد عناصر عمل می‌کند. در این الگوریتم هر بار عنصری به عنوان pivot یا محور انتخاب می‌شود (بطور پیش فرض عنصر اول آرایه است) در این حالت با استفاده از الگوریتم partition بقیه داده‌های آرایه طوری جابه‌جا می‌شوند که همه­‌ی عناصر کوچکتر (یا مساوی) از عنصر لولا یا pivot در یک طرف آن و کلیه عناصر بزرگتر (یا مساوی) در طرف دیگر آن قرار بگیرند. سپس دو آرایه ایجاد شده در دو طرف عنصر لولا یا محور را به همین ترتیب به صورت بازگشتی دوباره مرتب می‌کنیم و این کار آنقدر ادامه می­‌یابد تا به تک عنصر برسیم. این روش مرتب سازی سریع یک روش تقسیم و غلبه‌­ای است. بطور کلی الگوریتم‌‌ها دارای انواع مختلفی هستند که برای آشنایی با آنها می‌توانید به صفحه الگوریتم چیستالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد مراجعه نمایید.

در صورتیکه به این مقاله علاقه‌مند هستید، ممکن است صفحات زیر نیز برای شما جذاب باشد:

  1. آموزش جامع مرتب سازی ادغامی
  2. آموزش جامع مرتب سازی حبابی
  3. آموزش جامع مرتب سازی درجی

بخش‌های روش مرتب سازی سریع (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)

پیچیدگی زمانی الگوریتم مرتب ‌سازی سریع

ما در سه حالت کلی پیچیدگی زمانی این الگوریتم را بررسی خواهیم کرد.

بهترین وضعیت زمان اجرا (مرتبه زمانی) در الگوریتم مرتب‌ سازی سریع (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)

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

در این وضعیت:

اگر 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 عبارتست از:

  1. لیست مرتب و مقایسه‌ای نداریم.
  2. 36
  3. 15
  4. 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)

شبه کد الگوریتم مرتب ­سازی سریع


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

  1. 16 , 21 , 9 , 25 , 32 , 41
  2. 41 , 32 , 25 , 21 , 16 , 9
  3. 41 , 32 , 25 , 16 , 21 , 9
  4. 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) است.

همچنین هر گونه سوالی در مورد کلاس‌های آنلاین کنکور کامپیوتر و یا تهیه فیلم‌ها و یا رزرو مشاوره تک جلسه‌ای تلفنی با استاد رضوی دارید می‌توانید به طرق زیر از تیم پشتیبانی بپرسید:

آی دی تلگرام تیم پشتیبانی:     konkurcomputer_admin@

تماس با پشتیبانی:   09378555200

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (4 رای)
اشتراک
بارگذاری نظرات