وبینار رایگان سه ماه مهم تا کنکور ارشد مهندسی کامپیوتر و IT
مشاهده وبینار
کنکور کامپیوتر
مرتب سازی سریع

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

  • عنصر اول را به ‌طور پیش‌فرض به عنوان لولا (pivot) در نظر می‌گیریم.
  • اندیس‌های i , j به ترتیب از ابتدا و انتها به صورت زیر حرکت‌ می‌کنند:
  • اندیس i: با شروع از حد پایین به سمت اولین داده‌ای در آرایه حرکت می‌کند که ${A}\left[\mathrm{i}\right]>=\ \mathrm{pivot}$ باشد.

    اندیس j: با شروع از حد بالا به سمت اولین داده‌ای در آرایه حرکت می‌کند که ${A}\left[\mathrm{j}\right]<=\ \mathrm{pivot}$ باشد.

  • بعد از اجرای مرحله 2:

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

  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)

  • 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

  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)

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 رای)
بارگذاری نظرات