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

پنجشنبه ۹ آبان ۱۳۹۸
بازدید ۷,۴۷۴ نفر
سعید سیفی زاده
(54 امتیاز از 12 رای)
Loading...

تصویر selection-sort-algorithm_7309 الگوریتم مرتب سازی انتخابی (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

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-flowchart_7309 الگوریتم مرتب سازی انتخابی (Selection Sort)

مثال

پیاده سازی الگوریتم 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;
}

// 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

1 2	Sorted array: 11 12 22 25 64

تغییر به حالت نزولی

برای تغییر به حالت نزولی کافیست در تابع selectionSort شرط if (arr[j] < arr[min_idx]) را به if (arr[j] > arr[min_idx]) تغییر دهید.

نکات

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

الگوریتم ها - مرتب سازی درجی الگوریتم ها - مرتب سازی حبابی