الگوریتم مرتب سازی انتخابی (Selection Sort)

الگوریتم مرتب سازی انتخابی (Selection Sort)

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

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

• زیر آرایه ای که مقادیر مرتب شده در آن قرار می گیرند.
• زیر آرایه ای که مقادیر نامرتب در آن قرار دارند.

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

arr[] = 64 25 12 22 11
// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64
// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64
// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64
// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

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

مثال

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

// C++ program for implementation of selection sort
#include <bits/stdc++.h>
using namespace std;
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
        if (arr[j] < arr[min_idx])
            min_idx = j;
        // Swap the found minimum element with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
// Driver program to test above functions
int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

امتحان کنید

خروجی:

Sorted array:
11 12 22 25 64

نکات

• پیچیدگی زمانی این الگوریتم برابر با O(n²) است.
• فضای موقت برابر با O(1) است.
• یکی از مزایای Selection Sort این است که هرگز بیشتر از O(n) تعویض انجام نمی دهد. این موضوع برای زمانی که مقدار حافظه محدودی داریم، مناسب است.

نوشته الگوریتم مرتب سازی انتخابی (Selection Sort) اولین بار در سورس سرا - آموزش برنامه نویسی. پدیدار شد.