الگوریتم مرتب سازی انتخابی چیست؟ — توضیح و پیاده سازی الگوریتم در ۳ زبان

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

الگوریتم مرتب سازی انتخابی چیست؟

الگوریتم مرتب‌ سازی انتخابی «Selection Sort Algorithm» یک روش ساده برای مرتب کردن داده‌ها است که با پیدا کردن کوچک‌ترین (یا بزرگ‌ترین) عنصر در لیست مرتب‌نشده و قرار دادن آن در جایگاه صحیح خود در لیست مرتب‌شده، عمل می‌کند. این فرآیند به طور مکرر برای بقیه عناصر مرتب‌نشده تکرار می‌شود تا زمانی که کل لیست مرتب گردد. به عبارت دیگر، در هر مرحله، الگوریتم کوچک‌ترین عنصر را انتخاب و با عنصر موجود در موقعیت فعلی جابجا می‌کند، از این رو نام “انتخابی” را به خود گرفته است. این روش، به دلیل سادگی پیاده‌سازی، برای لیست‌های کوچک مناسب است اما برای لیست‌های بزرگتر به دلیل کارایی پایین، معمولاً توصیه نمی‌شود.

نحوه‌ی کار مرتب سازی انتخابی

۱. اولین عنصر را به عنوان کمینه در نظر بگیرید.

۲. مقایسه‌ی کمینه (کوچکترین عنصر فعلی) با عنصر دوم. اگر عنصر دوم از کمینه کوچک‌تر بود، عنصر دوم را به عنوان کمینه در نظر بگیرید.

مقایسه‌ی کمینه با عنصر سوم. دوباره، اگر عنصر سوم از کمینه کوچک‌تر بود، کمینه را به عنصر سوم اختصاص دهید، در غیر این صورت کاری انجام ندهید. این روند تا آخرین عنصر ادامه دارد.

۳. پس از هر تکرار، کمینه (کوچکترین عنصر یافت شده) در ابتدای لیست مرتب نشده قرار می‌گیرد.

۴. در هر تکرار، نمایه گذاری از اولین عنصر مرتب نشده آغاز می‌شود. مراحل ۱ تا ۴ تا زمانی که تمام عناصر در جایگاه صحیح خود قرار گیرند، تکرار می‌شوند.

مرحله اول

مرحله دوم:

مرحله سوم:

مرحله چهارم:

در شکل بالا مرتب سازی پایان یافته و عناصر آرایه از کوچک به بزرگ مرتب شده اند.

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

پیچیدگی زمانی: O(n²) زیرا دو حلقه‌ی تو در تو وجود دارد:

1. یک حلقه برای انتخاب تک تک عناصر آرایه = O(n)
2. حلقه‌ی دیگر برای مقایسه‌ی آن عنصر با هر عنصر دیگر آرایه = O(n)
3. بنابراین، پیچیدگی کلی = O(n) * O(n) = O(n²)

فضای کمکی: O(1) چرا که تنها حافظه‌ی اضافی مورد استفاده، برای متغیرهای موقت است.

مزایا و معایب الگوریتم مرتب‌ سازی انتخابی

در ادامه درمورد مزایا و معایب الگوریتم انتخابی برای مرتب سازی داده‌ها صحبت خواهیم کرد.

مزایای الگوریتم مرتب‌ سازی انتخابی

مزایای الگوریتم مرتب‌ سازی انتخابی به شرح زیر است:

• سادگی و سهولت درک و پیاده‌سازی: الگوریتم مرتب‌ سازی انتخابی بسیار ساده است و درک و پیاده‌سازی آن آسان است. این امر آن را برای آموزش مفاهیم اساسی مرتب سازی و همچنین برای استفاده در موقعیت‌هایی که سادگی مهم‌تر از سرعت است، مناسب می‌کند.
• فضای حافظه کمکی ثابت (O(1)): این الگوریتم از حافظه اضافی کمی استفاده می‌کند. فقط به چند متغیر موقت برای جابجایی عناصر نیاز دارد. این ویژگی آن را برای محیط‌هایی که حافظه محدود است، مانند سیستم‌های تعبیه‌شده، مفید می‌کند.
• تعداد جابه‌جایی‌های کم (نسبتاً): در مقایسه با برخی الگوریتم‌های مرتب سازی دیگر (مانند مرتب سازی حبابی)، مرتب سازی انتخابی تعداد کمتری جابه‌جایی انجام می‌دهد. این می‌تواند در مواردی که عمل جابه‌جایی (نوشتن در حافظه) گران است (مثلاً در حافظه‌های فلش) یک مزیت باشد. در این زمینه، تنها الگوریتم مرتب سازی چرخه‌ای (Cycle Sort) از آن بهتر عمل می‌کند.
• کاربرد در آموزش: به دلیل سادگی، مرتب سازی انتخابی اغلب به عنوان یک الگوریتم آموزشی برای معرفی مفاهیم مرتب سازی استفاده می‌شود.

معایب مرتب سازی انتخابی

معایب اصلی الگوریتم مرتب‌ سازی انتخابی (Selection Sort) عبارتند از:

• بازدهی پایین (کند): الگوریتم مرتب‌ سازی انتخابی دارای پیچیدگی زمانی O(n^2) است. این بدان معناست که زمان اجرای الگوریتم با افزایش اندازه ورودی (تعداد عناصر برای مرتب سازی) به صورت درجه دوم افزایش می‌یابد. به همین دلیل، مرتب سازی انتخابی برای مجموعه‌ داده‌های بزرگ، نسبت به الگوریتم‌های مرتب سازی کارآمدتر مانند مرتب سازی ادغامی (Merge Sort) یا مرتب سازی سریع (Quick Sort)، بسیار کندتر عمل می‌کند.
• تعداد مقایسه‌های زیاد: مرتب سازی انتخابی برای مرتب سازی عناصر، مقایسه‌های زیادی انجام می‌دهد، حتی اگر ورودی تقریباً مرتب شده باشد. این باعث می‌شود که الگوریتم در عمل، برای ورودی‌هایی که تقریباً مرتب شده‌اند، بازدهی کمتری داشته باشد.
• مناسب نبودن برای داده‌های بزرگ: با توجه به پیچیدگی زمانی O(n^2)، مرتب سازی انتخابی برای مرتب سازی مجموعه‌ داده‌های بزرگ، به دلیل زمان اجرای طولانی، ناکارآمد است.
• عدم پایداری (Stability): مرتب سازی انتخابی یک الگوریتم ناپایدار است. به این معنی که ترتیب نسبی عناصری با مقادیر مساوی، پس از مرتب سازی ممکن است تغییر کند. این می‌تواند در برخی از برنامه‌ها که حفظ ترتیب اصلی عناصر با مقادیر برابر مهم است، مشکل‌ساز باشد.
• استفاده محدود: به دلیل بازدهی پایین و معایب دیگر، مرتب سازی انتخابی معمولاً در برنامه‌های کاربردی عملیاتی استفاده نمی‌شود، مگر در مواردی که سادگی پیاده‌سازی از اهمیت بیشتری نسبت به کارایی برخوردار باشد، یا برای مجموعه‌ داده‌های بسیار کوچک استفاده شود.

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

الگوریتم مرتب‌ سازی انتخابی در برخی موارد خاص کاربردهایی دارد که در ادامه به آن‌ها اشاره می‌کنیم:

آموزش و یادگیری

• به دلیل سادگی پیاده‌سازی، مرتب سازی انتخابی یک ابزار آموزشی عالی برای معرفی مفاهیم اساسی مرتب سازی در علوم کامپیوتر است.
• درک این الگوریتم آسان است و به دانشجویان کمک می‌کند تا اصول مرتب سازی را به طور شهودی درک کنند.

مجموعه‌های داده‌های کوچک

• برای مجموعه‌های داده‌های بسیار کوچک (مثلاً کمتر از ۵۰ عنصر)، مرتب سازی انتخابی می‌تواند به اندازه‌ی کافی سریع باشد و overhead اضافی الگوریتم‌های پیچیده‌تر را نداشته باشد.
• در این موارد، سادگی و پیاده‌سازی آسان آن ممکن است از کارایی کمی کمتر آن مهم‌تر باشد.

بهینه سازی حافظه

• مرتب سازی انتخابی درجا (in-place) است، به این معنی که در همان آرایه ورودی عمل مرتب سازی را انجام می‌دهد و به حافظه اضافی قابل توجهی نیاز ندارد.
• در محیط‌هایی که حافظه محدود است، این ویژگی می‌تواند یک مزیت محسوب شود.

سادگی پیاده‌سازی

• در مواردی که سادگی کد و سرعت توسعه مهم‌تر از کارایی باشد، مرتب سازی انتخابی می‌تواند یک گزینه مناسب باشد.
• پیاده‌سازی این الگوریتم بسیار ساده است و به سرعت انجام می‌شود.

به عنوان یک الگوریتم پایه برای مقایسه

• مرتب سازی انتخابی می‌تواند به عنوان یک مرجع یا پایه برای مقایسه با الگوریتم‌های مرتب سازی پیشرفته‌تر استفاده شود.
• با مقایسه عملکرد الگوریتم‌های دیگر با مرتب سازی انتخابی، می‌توان درک بهتری از مزایا و معایب هر الگوریتم به دست آورد.

مقایسه الگوریتم مرتب‌ سازی انتخابی با الگوریتم مرتب سازی حبابی

الگوریتم مرتب‌ سازی انتخابی

• اصل: در هر مرحله، کوچک‌ترین (یا بزرگ‌ترین) عنصر را در بخش مرتب‌نشده‌ی لیست پیدا می‌کند و آن را به ابتدای (یا انتهای) بخش مرتب‌شده منتقل می‌کند.
• پیچیدگی زمانی: O(n^2) در تمام حالات (بهترین، متوسط، بدترین). این بدین معنی است که زمان مورد نیاز برای مرتب سازی با افزایش تعداد عناصر به صورت مربع افزایش می‌یابد.
• پیچیدگی فضایی: O(1) به مقدار ثابتی از حافظه نیاز دارد، صرف نظر از تعداد عناصر.
• مزایا: ساده و قابل فهم است. پیچیدگی فضایی پایین.
• معایب: در مقایسه با الگوریتم‌های مرتب سازی با پیچیدگی زمانی کمتر مانند مرتب سازی سریع یا ادغام، برای لیست‌های بزرگ کارایی پایینی دارد.

الگوریتم مرتب سازی حبابی

• اصل: دو عنصر مجاور را با هم مقایسه می‌کند و در صورت لزوم آنها را جا به جا می‌کند تا بزرگ‌ترین عنصر (یا کوچک‌ترین عنصر) به انتهای (یا ابتدای) لیست منتقل شود. این فرآیند تا زمانی ادامه می‌یابد که لیست مرتب شود.
• پیچیدگی زمانی: O(n^2) در تمام حالات (بهترین، متوسط، بدترین).
• پیچیدگی فضایی: O(1) نیاز به فضای کم دارد.
• مزایا: ساده و قابل فهم است. پیچیدگی فضایی پایین.
• معایب: در مقایسه با الگوریتم‌های مرتب سازی با پیچیدگی زمانی کمتر، کارایی پایینی دارد. مخصوصا برای لیست‌های بزرگ، زمان زیادی را می‌گیرد.

پاورپوینت مقایسه الگوریتم های مرتب سازی (Sorting algorithm)

کلیک کنید

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

در ادامه پیاده سازی الگوریتم مرتب سازی انتخاب در زبان‌های برنامه نویسی مختلف آورده شده است.

پیاده سازی الگوریتم مرتب سازی انتخابی در زبان جاوا

// Java program for implementation of Selection Sort
import java.util.Arrays;

class GfG {

    static void selectionSort(int[] arr){
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
          
            // Assume the current position holds
            // the minimum element
            int min_idx = i;

            // Iterate through the unsorted portion
            // to find the actual minimum
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                  
                    // Update min_idx if a smaller element
                    // is found
                    min_idx = j;
                }
            }

            // Move minimum element to its
            // correct position
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;           
        }
    }

    static void printArray(int[] arr){
        for (int val : arr) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
  
    public static void main(String[] args){
        int[] arr = { 64, 25, 12, 22, 11 };

        System.out.print("Original array: ");
        printArray(arr);

        selectionSort(arr);

        System.out.print("Sorted array: ");
        printArray(arr);
    }
}

خروجی:

Original vector: 64 25 12 22 11 
Sorted vector:   11 12 22 25 64

پیاده سازی الگوریتم مرتب سازی انتخابی در زبان ++C

// C++ program to implement Selection Sort
#include <bits/stdc++.h>
using namespace std;

void selectionSort(vector<int> &arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; ++i) {

        // Assume the current position holds
        // the minimum element
        int min_idx = i;

        // Iterate through the unsorted portion
        // to find the actual minimum
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[min_idx]) {

                // Update min_idx if a smaller
                // element is found
                min_idx = j; 
            }
        }

        // Move minimum element to its
        // correct position
        swap(arr[i], arr[min_idx]);
    }
}

void printArray(vector<int> &arr) {
    for (int &val : arr) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};

    cout << "Original array: ";
    printArray(arr); 

    selectionSort(arr);

    cout << "Sorted array: ";
    printArray(arr);

    return 0;
}

خروجی:

Original vector: 64 25 12 22 11 
Sorted vector:   11 12 22 25 64

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

# Python program for implementation of Selection
# Sort

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
      
        # Assume the current position holds
        # the minimum element
        min_idx = i
        
        # Iterate through the unsorted portion
        # to find the actual minimum
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
              
                # Update min_idx if a smaller element is found
                min_idx = j
        
        # Move minimum element to its
        # correct position
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

def print_array(arr):
    for val in arr:
        print(val, end=" ")
    print()

if __name__ == "__main__":
    arr = [64, 25, 12, 22, 11]
    
    print("Original array: ", end="")
    print_array(arr)
    
    selection_sort(arr)
    
    print("Sorted array: ", end="")
    print_array(arr)

خروجی:

Original vector: 64 25 12 22 11 
Sorted vector: 11 12 22 25 64

سخن آخر

الگوریتم مرتب سازی انتخابی یک روش ساده برای مرتب کردن داده‌ها است که با یافتن کوچک‌ترین عنصر در لیست و قرار دادن آن در ابتدای لیست شروع می‌شود. این فرآیند برای بقیه عناصر تکرار می‌شود، به طوری که در هر مرحله، کوچک‌ترین عنصر از قسمت مرتب نشده‌ی لیست انتخاب شده و در جایگاه صحیح خود قرار می‌گیرد. این روند تا زمانی ادامه می‌یابد که تمام عناصر در جایگاه مناسب خود قرار گیرند. اگرچه مرتب سازی انتخابی از نظر مفهومی ساده است، اما برای مجموعه‌داده‌های بزرگ، به دلیل داشتن پیچیدگی زمانی O(n^2)، کارایی کمتری نسبت به الگوریتم‌های مرتب سازی پیچیده‌تر مانند مرتب سازی ادغامی یا سریع دارد.