الگوریتم مرتب سازی انتخابی و پیاده سازی آن در زبان های مختلف
![الگوریتم مرتب سازی انتخابی و پیاده سازی آن در زبان های مختلف](https://blog.faradars.org/wp-content/webp-express/webp-images/doc-root/wp-content/uploads/2024/07/Symbolic_space-A-computer-with-code-on-the-screen-1.jpg.webp)
«الگوریتم مرتب سازی انتخابی» (Selection Sort Algorithm)، یکی از الگوریتمهای کارآمد در مبحث مرتبسازی دادهها است. این الگوریتم بر اساس انتخاب تکراری کوچکترین یا بزرگترین عنصر در بخش مرتب نشده لیست و انتقال آن به بخش مرتب شده لیست کار میکند. مرتبسازی انتخابی تقریبا سادهترین الگوریتم ممکن است. این الگوریتم از نوع تکنیکهای «مقایسه درجا» (In-Place Comparison) برای مرتبسازی دادهها است. در مرتبسازی انتخابی، آرایه به دو بخش تقسیم میشود. بخش اول، قسمت مرتب شده و بخش دوم قسمت نامرتب الگوریتم را تشکیل میدهند. در ابتدای کار، بخش مرتب شده آرایه خالی است و بخش نامرتب آرایه شامل آرایه داده شده به مسئله به عنوان داده ورودی میشود. معمولا بخش مرتب شده آرایه در سمت چپ و بخش نامرتب آرایه در بخش سمت راست قرار میگیرد.
در این مطلب از مجله فرادرس، درباره عملکرد الگوریتم مرتب سازی انتخابی بحث میکنیم. روش کار این الگوریتم را به صورت دقیق و واضح توضیح داده و کدهای مربوط به تکنیک مرتبسازی دادهها با روش انتخابی را در زبانهای برنامه نویسی مختلف پیادهسازی میکنیم. در آخر هم عملکرد این الگوریتم را ارزیابی کرده و توضیحاتی را درباره مزایا و معایب مختص به آن به صورت خلاصه ارائه دادهایم.
الگوریتم مرتب سازی انتخابی چیست؟
مرتبسازی انتخابی، الگوریتمی کارآمد برای مرتبسازی دادهها است. الگوریتم مرتب سازی انتخابی بر اساس انتخاب پشت سر هم کوچکترین یا بزرگترین عنصر در بخش مرتب نشده آرایه و انتقال آن به بخش مرتب شده آرایه کار میکند. در ضمن این الگوریتم فرایند درک و پیادهسازی بسیار سادهای نیز دارد.
فرایند کار این الگوریتم بسیار ساده است. در مرتبسازی انتخابی، کوچکترین یا بزرگترین عنصر از سمت نامرتب آرایه به عنوان اولین عنصر انتخاب میشود و به عنوان اولین عنصر در بخش مرتب شده آرایه - که سمت چپ است - قرار میگیرد. در واقع جای خود را با عنصر موجود در این بخش از آرایه تعویض میکند. سپس دومین عنصر بزرگ یا کوچک در آرایه انتخاب شده و جای خود را با دومین عنصر از سمت چپ در آرایه جابهجا میکند. این روند به همین صورت ادامه پیدا میکند تا در نهایت کل آرایه به صورت مرتب شده در بیاید.
حالت میانگین و بدترین زمان اجرای این الگوریتم برابر با است. n در این فرمول نشان دهنده تعداد عناصر آرایه است. در نتیجه مرتبسازی انتخابی گزینه مناسبی برای کار بر روی مجموعه دادههای بزرگ نیست.
آشنایی با مبحث طراحی الگوریتم به کمک فرادرس
طراحی الگوریتم یکی از مباحث بسیار پایه در علوم کامپیوتری است. البته این رشته علمی، کاربردهای بسیار گستردهتری حتی به غیر از علوم کامپیوتری نیز دارد. فرادرس با تاکید بر آموزشی علوم کامپیوتر به تولید فیلمهای آموزشی با هدف افزایش مهارتهای توسعه دهندگان نرمافزار یا حتی آمادگی جهت شرکت در آزمونهای دانشگاهی پرداخته است. این شاخه از علم در علوم کامپیوتر رابطه نزدیکی با برنامهنویسی و مبحث ساختمان داده دارد. به همین منظور در فرادرس با نگرش برنامه نویسی به تهیه فیلمهای آموزشی طراحی الگوریتمها و ساختمان داده پرداختهایم.
![مجموعه آموزش طراحی الگوریتم - نوشتن الگوریتم](https://blog.faradars.org/wp-content/uploads/2024/05/Algoritm-design-learning-collection-1.png)
در این بخش چند فیلم آموزشی در ارتباط با طراحی الگوریتم را معرفی کردهایم. آشنایی و تسلط به این دانش یکی از الزامات برای حرفهای شدن برنامهنویسان و مهندسین نرم افزار است. در صورت نیاز با کلیک بر روی تصویر بالا میتوانید وارد صفحه اصلی این مجموعه آموزش شده و از فیلمهای آموزشی بیشتری استفاده کنید.
- فیلم آموزش طراحی الگوریتم با فرادرس
- فیلم آموزش طراحی الگوریتم همراه با حل مثال های عملی در فرادرس
- فیلم آموزش حل سوالات آزمون های استخدامی طراحی الگوریتم با فرادرس
- فیلم آموزش حل روابط بازگشتی با فرادرس
الگوریتم مرتب سازی انتخابی چگونه کار میکند؟
بهترین روش برای درک کردن روش کار الگوریتم مرتبسازی و پیادهسازی آن، آشنایی با تکنیکهای طراحی الگوریتم است. علاوه بر مطلب بیان شده، درس طراحی و تحلیل الگوریتمها، یکی از دروس مهم رشته کارشناسی کامپیوتر و پایه و اساس برنامهنویسی است. بهمنظور آشنایی بسیار خوب با طراحی الگوریتم پیشنهاد میدهیم که فیلم آموزش طراحی الگوریتم به صورت جامع و با مفاهیم کلیدی را از فرادرس مشاهده بفرمایید. در جهت کمک به شما لینک مربوط به فیلم را در ادامه نیز قرار دادهایم.
برای اینکه روند کار الگوریتم مرتبسازی را درک کنیم در ابتدا به صورت مصور همراه با آرایهای فرضی روش کار این الگوریتم را نمایش داده و بعد از آن شبهه کد مربوط به الگوریتم را ارائه میدهیم.
روش کار مرتب سازی انتخابی
در این بخش، روند کار الگوریتم مرتب سازی انتخابی را با اجرای این الگوریتم بر روی مثال سادهای نمایش دادهایم. برای نمایش این مثال، آرایه نامرتبی را انتخاب کردهایم. آرایه فرضی مسئله به شکل زیر است.
![آرایه فرضی برای نمایش کار الگوریتم مرتب سازی انتخابی](https://blog.faradars.org/wp-content/uploads/2024/06/selection-sort-1.png)
الان برای انتخاب اولین عنصر در بخش مرتب شده آرایه، باید کل آرایه بالا را به صورت پشتسرهم بررسی کنیم.
در آرایه بالا میتوان دید که مقدار اولین جایگاه آرایه برابر با ۱۲ است. با جستوجوی کل آرایه، در مییابیم که جایگاهی با مقدار ۸ در آرایه وجود دارد. به طور مشخص، این مقدار از عدد ۱۲ کوچکتر است.
![آرایه فرضی برای نمایش کار الگوریتم مرتب سازی انتخابی](https://blog.faradars.org/wp-content/uploads/2024/06/selection-sort-2.png)
بنابراین برای مقدار دهی اولین جایگاه از بخش مرتب شده آرایه، لازم است که مقادیر ۱۲ و ۸ با یکدیگر جابهجا شوند. بعد از اولین پیمایش بر روی آرایه، عدد ۸ به عنوان کوچکترین عنصر بخش مرتب شده شناسایی میشود و در ابتدای این بخش قرار میگیرد.
![آرایه فرضی برای نمایش کار الگوریتم مرتب سازی انتخابی](https://blog.faradars.org/wp-content/uploads/2024/06/selection-sort-3.png)
برای جایگاه دوم، جایی که در حال حاضر عدد ۲۹ قرار دارد، باید دوباره به صورت متوالی، بقیه عناصر موجود در بخش نامرتب آرایه را بررسی کنیم. بعد از این بررسی میبینیم که دومین عنصر کوچک آرایه برابر با عدد ۱۲ است. در نتیجه عدد ۱۲ باید در جایگاه دوم بخش مرتب شده آرایه قرار بگیرد.
![آرایه فرضی برای نمایش کار الگوریتم مرتب سازی انتخابی](https://blog.faradars.org/wp-content/uploads/2024/06/selection-sort-4.png)
الان اعداد ۲۹ و ۱۲ را با یکدیگر جابهجا میکنیم. بعد از دومین پیمایش آرایه عدد ۱۲ در جایگاه دومین عنصر بخش مرتب شده آرایه قرار میگیرد. در نتیجه قابل مشاهده است که بعد از دوبار پیمایش بخش نامرتب آرایه دو عنصر از کوچکترین مقادیر در این آرایه در موقعیت شروع بخش مرتب شده آرایه قرار گرفتهاند.
![آرایه فرضی برای نمایش کار الگوریتم مرتب سازی انتخابی](https://blog.faradars.org/wp-content/uploads/2024/06/selection-sort-5.png)
همین روال بر روی قسمت باقیمانده بخش نامرتب آرایه به صورت تکراری اعمال میشود. در تصویر پایین میتوانیم نمایش مصوری از تکرار روند اشاره شده در بالا را بر روی کل آرایه مشاهده کنیم.
![آرایه فرضی برای نمایش کار الگوریتم مرتب سازی انتخابی](https://blog.faradars.org/wp-content/webp-express/webp-images/doc-root/wp-content/uploads/2024/06/selection-sort-6.png.webp)
در انتهای این روند تکراری به آرایهای رسیدهایم که اکنون به صورت کامل مرتب شده است. قبل از پیادهسازی کدهای مربوط به این الگوریتم لازم است، با شبهه کد آن نیز آشنا شویم.
شبهه کد مرتب سازی انتخابی
شبهه کد مربوط به این الگوریتم را در فهرست پایین ارائه کردهایم.
تعریف تابع SELECTION
ابتدای کار، تابع مخصوص الگوریتم مرتب سازی انتخابی را به نام دلخواه SELECTION SORT(arr, n) تعریف میکنیم. عملیات زیر، داخل تابع انجام میشود.
- مرحله اول: حلقهای تعریف میکنیم تا مراحل دوم و سوم را برای هر i = 0 تا n-1 تکرار کند.
- مرحله دوم: تابعی به نام SMALLEST(arr, i, n, pos) را فراخوانی میکنیم. این تابع باید کوچکترین عنصر را پیدا کند.
- مرحله سوم: arr[i] را با arr[pos] جابهجا میکنیم. arr[i] نشاندهنده عنصر فعلی و arr[pos]نشان دهنده مقدار کوچکترین عنصر همراه با جایگاه آن در آرایه است.
- مرحله چهارم: خروج از حلقه و سپس خروج از برنامه
تعریف تابع SMALLEST
- مرحله اول: کوچکترین مقدار را برابر با arr[i] قرار میدهد. SMALL = arr[i]
- مرحله دوم: موقعیت آن را برابر با i قرا میدهد. pos = i
- مرحله سوم: به صورت تکراری به ازای j = i+1 تا nروند زیر را انجام میدهد.
- اگر SMALL > arr[j] بود، کوچکترین عنصر را برابر با arr[j] قرار میدهد. SMALL = arr[j]
- سپس مقدار pos را مساوی با j میکند.
- در غیر این صورت به سراغ بعدی arr[j]میرود.
- شرط به پایان میرسد.
- از حلقه خارج میشویم.
- مرحله چهارم: در این مرحله مقدار pos را برمیگرداند.
پیادهسازی کدهای مربوط به مرتب سازی انتخابی
در این قسمت از مطلب، کدهای مربوط به الگوریتم مرتب سازی انتخابی برای کار بر روی آرایههایی با مقادیر نامرتب را با هفت زبان برنامه نویسی مختلف پیادهسازی کردهایم. نمایش این کدها را با زبان ++C شروع میکنیم.
پیاده سازی الگوریتم مرتب سازی انتخابی در زبان ++C
در کادر زیر، کدهای مربوط به پیادهسازی الگوریتم مرتب سازی انتخابی را با استفاده از زبان برنامه نویسی ++C مشاهده میکنیم.
1#include <bits/stdc++.h>
2using namespace std;
3
4// Function for Selection sort
5void selectionSort(int arr[], int n)
6{
7 int i, j, min_idx;
8
9 // One by one move boundary of
10 // unsorted subarray
11 for (i = 0; i < n - 1; i++) {
12
13 // Find the minimum element in
14 // unsorted array
15 min_idx = i;
16 for (j = i + 1; j < n; j++) {
17 if (arr[j] < arr[min_idx])
18 min_idx = j;
19 }
20
21 // Swap the found minimum element
22 // with the first element
23 if (min_idx != i)
24 swap(arr[min_idx], arr[i]);
25 }
26}
27
28// Function to print an array
29void printArray(int arr[], int size)
30{
31 int i;
32 for (i = 0; i < size; i++) {
33 cout << arr[i] << " ";
34 cout << endl;
35 }
36}
37
38// Driver program
39int main()
40{
41 int arr[] = { 64, 25, 12, 22, 11 };
42 int n = sizeof(arr) / sizeof(arr[0]);
43
44 // Function Call
45 selectionSort(arr, n);
46 cout << "Sorted array: \n";
47 printArray(arr, n);
48 return 0;
49}
پیاده سازی الگوریتم مرتب سازی انتخابی در زبان C
در کادر زیر، کدهای مربوط به پیادهسازی الگوریتم مرتب سازی انتخابی را با استفاده از زبان برنامه نویسی C مشاهده میکنیم.
1#include <stdio.h>
2
3void swap(int *xp, int *yp)
4{
5 int temp = *xp;
6 *xp = *yp;
7 *yp = temp;
8}
9
10void selectionSort(int arr[], int n)
11{
12 int i, j, min_idx;
13
14 // One by one move boundary of unsorted subarray
15 for (i = 0; i < n-1; i++)
16 {
17 // Find the minimum element in unsorted array
18 min_idx = i;
19 for (j = i+1; j < n; j++)
20 if (arr[j] < arr[min_idx])
21 min_idx = j;
22
23 // Swap the found minimum element with the first element
24 if(min_idx != i)
25 swap(&arr[min_idx], &arr[i]);
26 }
27}
28
29/* Function to print an array */
30void printArray(int arr[], int size)
31{
32 int i;
33 for (i=0; i < size; i++)
34 printf("%d ", arr[i]);
35 printf("\n");
36}
37
38// Driver program to test above functions
39int main()
40{
41 int arr[] = {64, 25, 12, 22, 11};
42 int n = sizeof(arr)/sizeof(arr[0]);
43 selectionSort(arr, n);
44 printf("Sorted array: \n");
45 printArray(arr, n);
46 return 0;
47}
پیاده سازی الگوریتم مرتب سازی انتخابی در زبان جاوا
زبان برنامهنویسی جاوا یکی از زبانهای پرطرفدار و قدرتمند برنامهنویسی است. برای اینکه کدهای پایین را درک کنیم باید با ساختار این زبان آشنایی داشته باشیم. یکی از بهترین و سریع ترین راههای آشنایی با جاوا مطالعه مطلب آینده زبان برنامه نویسی جاوا چیست و آیا ارزش یادگیری دارد؟ همراه با فیلم رایگان درباره این زبان از مجله فرادرس است.
در کادر زیر، کدهای مربوط به پیادهسازی الگوریتم مرتب سازی انتخابی را با استفاده از زبان برنامه نویسی جاوا مشاهده میکنیم.
1import java.io.*;
2public class SelectionSort
3{
4 void sort(int arr[])
5 {
6 int n = arr.length;
7
8 // One by one move boundary of unsorted subarray
9 for (int i = 0; i < n-1; i++)
10 {
11 // Find the minimum element in unsorted array
12 int min_idx = i;
13 for (int j = i+1; j < n; j++)
14 if (arr[j] < arr[min_idx])
15 min_idx = j;
16
17 // Swap the found minimum element with the first
18 // element
19 int temp = arr[min_idx];
20 arr[min_idx] = arr[i];
21 arr[i] = temp;
22 }
23 }
24
25 // Prints the array
26 void printArray(int arr[])
27 {
28 int n = arr.length;
29 for (int i=0; i<n; ++i)
30 System.out.print(arr[i]+" ");
31 System.out.println();
32 }
33
34 // Driver code to test above
35 public static void main(String args[])
36 {
37 SelectionSort ob = new SelectionSort();
38 int arr[] = {64,25,12,22,11};
39 ob.sort(arr);
40 System.out.println("Sorted array");
41 ob.printArray(arr);
42 }
43}
پیاده سازی الگوریتم مرتب سازی انتخابی در زبان پایتون
در کادر زیر، کدهای مربوط به پیادهسازی الگوریتم مرتب سازی انتخابی را با استفاده از زبان برنامه نویسی پایتون مشاهده میکنیم.
1A = [64, 25, 12, 22, 11]
2
3# Traverse through all array elements
4for i in range(len(A)-1):
5
6 # Find the minimum element in remaining
7 # unsorted array
8 min_idx = i
9 for j in range(i+1, len(A)):
10 if A[min_idx] > A[j]:
11 min_idx = j
12
13 # Swap the found minimum element with
14 # the first element
15 A[i], A[min_idx] = A[min_idx], A[i]
16
17# Driver code to test above
18print ("Sorted array")
19for i in range(len(A)):
20 print(A[i],end=" ")
پیاده سازی الگوریتم مرتب سازی انتخابی در زبان #C
در کادر زیر، کدهای مربوط به پیادهسازی الگوریتم مرتب سازی انتخابی را با استفاده از زبان برنامه نویسی #C مشاهده میکنیم.
1using System;
2
3class GFG
4{
5 static void sort(int []arr)
6 {
7 int n = arr.Length;
8
9 // One by one move boundary of unsorted subarray
10 for (int i = 0; i < n - 1; i++)
11 {
12 // Find the minimum element in unsorted array
13 int min_idx = i;
14 for (int j = i + 1; j < n; j++)
15 if (arr[j] < arr[min_idx])
16 min_idx = j;
17
18 // Swap the found minimum element with the first
19 // element
20 int temp = arr[min_idx];
21 arr[min_idx] = arr[i];
22 arr[i] = temp;
23 }
24 }
25
26 // Prints the array
27 static void printArray(int []arr)
28 {
29 int n = arr.Length;
30 for (int i=0; i<n; ++i)
31 Console.Write(arr[i]+" ");
32 Console.WriteLine();
33 }
34
35 // Driver code
36 public static void Main()
37 {
38 int []arr = {64,25,12,22,11};
39 sort(arr);
40 Console.WriteLine("Sorted array");
41 printArray(arr);
42 }
43
44}
پیاده سازی الگوریتم مرتب سازی انتخابی در زبان جاوا اسکریپت
در کادر زیر، کدهای مربوط به پیادهسازی الگوریتم مرتب سازی انتخابی را با استفاده از زبان برنامه نویسی جاوا اسکریپت مشاهده میکنیم.
1<script>
2function swap(arr,xp, yp)
3{
4 var temp = arr[xp];
5 arr[xp] = arr[yp];
6 arr[yp] = temp;
7}
8
9function selectionSort(arr, n)
10{
11 var i, j, min_idx;
12
13 // One by one move boundary of unsorted subarray
14 for (i = 0; i < n-1; i++)
15 {
16 // Find the minimum element in unsorted array
17 min_idx = i;
18 for (j = i + 1; j < n; j++)
19 if (arr[j] < arr[min_idx])
20 min_idx = j;
21
22 // Swap the found minimum element with the first element
23 swap(arr,min_idx, i);
24 }
25}
26
27function printArray( arr, size)
28{
29 var i;
30 for (i = 0; i < size; i++)
31 document.write(arr[i] + " ");
32 document.write(" <br>");
33}
34
35var arr = [64, 25, 12, 22, 11];
36 var n = 5;
37 selectionSort(arr, n);
38 document.write("Sorted array: <br>");
39 printArray(arr, n);
40
41</script>
پیاده سازی الگوریتم مرتب سازی انتخابی در زبان PHP
در کادر زیر، کدهای مربوط به پیادهسازی الگوریتم مرتب سازی انتخابی را با استفاده از زبان برنامه نویسی PHP مشاهده میکنیم.
1function selection_sort(&$arr, $n)
2{
3 for($i = 0; $i < $n ; $i++)
4 {
5 $low = $i;
6 for($j = $i + 1; $j < $n ; $j++)
7 {
8 if ($arr[$j] < $arr[$low])
9 {
10 $low = $j;
11 }
12 }
13
14 // swap the minimum value to $ith node
15 if ($arr[$i] > $arr[$low])
16 {
17 $tmp = $arr[$i];
18 $arr[$i] = $arr[$low];
19 $arr[$low] = $tmp;
20 }
21 }
22}
23
24// Driver Code
25$arr = array(64, 25, 12, 22, 11);
26$len = count($arr);
27selection_sort($arr, $len);
28echo "Sorted array : \n";
29
30for ($i = 0; $i < $len; $i++)
31 echo $arr[$i] . " ";
خروجی همه این کدها به صورت زیر به کاربر نمایش داده میشود.
Sorted array: 11 12 22 25 64
ارزیابی عملکرد مرتب سازی انتخابی
مهمترین معیارهای ارزیابی کیفیت عملکرد الگوریتمها اندازه پیچیدگی فضایی و زمانی آنها است. برای ارزیابی عملکرد این الگوریتم هم باید این معیارها را اندازه گرفت. تعداد مقایسههایی که در الگوریتم مرتب سازی انتخابی انجام میگیرند برابر با مقدار نمایش داده شده در زیر است.
(n - 1) + (n - 2) + (n - 3) + ... + 1 = n(n - 1) / 2
در نتیجه مقدار نهایی بدست آمده که برابر با n(n - 1) / 2 است را میتوان تقریبا برابر با مقایسه برای هر آرایه در نظر گرفت.
همچنین یکی دیگر از راههای اندازهگیری پیچیدگی، مشاهده تعداد حلقهها است. فقط کافیست تعداد حلقهها را در یکدیگر ضرب کنیم. در این الگوریتم دو حلقه وجود دارد، بنابر این پیچیدگی برابر با است.
پیچیدگی زمانی
همیشه برای اندازهگیری «پیچیدگی زمانی» (Time Complexity) باید این معیار را در سه موقعیت بهترین، بدترین و حالت میانگین اندازهگیری کرد.
- بدترین حالت پیچیدگی زمانی: این حالت زمانی روی میدهد که بخواهیم آرایه را به حالت صعودی مرتب کنیم درحالی که آرایه داده شده در حالت نزولی است. میزان پیچیدگی زمانی در این حالت برابر با است.
- بهترین حالت پیچیدگی زمانی: این حالت زمانی روی میدهد که آرایه ورودی به مسئله از قبل در حالت مرتب شده قرار داشته باشد. میزان پیچیدگی زمانی در این حالت هم برابر با است.
- حالت میانگین پیچیدگی زمانی: این حالت زمانی روی میدهد که عناصر آرایه ورودی به مسئله در حالت درهم و نامنظم قرار داشته باشند. میزان پیچیدگی زمانی در این حالت نیز برابر با است.
پیچیدگی زمانی الگوریتم مرتب سازی انتخابی در هر سه مورد باهم برابر است. در هر مرحلهای ابتدا باید کوچکترین عنصر مربوط به آرایه را پیدا کرده و در جای درست خود قرار دهیم. اما تا زمانی که پیمایش آرایه تا به آخر انجام نشده، کوچکترین عنصر شناخته نمیشود.
![پسر برنامه نویس در یک کافه رو به استادیوم رم نشسته است و با لپتاپ کار میکند.](https://blog.faradars.org/wp-content/uploads/2024/07/In-a-charming-cafe-in-Rome-Italy-a-programmer-works-alot.jpg)
پیچیدگی فضایی
«پیچیدگی فضایی» (Space Complexity) در این الگوریتم برابر با است. زیرا برای حل مسئله باید از متغیر اضافی به نام فرضی temp استفاده کنیم.
مزایا و معایب مرتب سازی انتخابی
هر الگوریتمی دارای مزایا و معایب خاص خود است. الگوریتم مرتب سازی انتخابی نیز از این قضیه مستثنا نیست. در این بخش از مطلب با مزایا و معایب این الگوریتم آشنا میشویم.
مزیت های مرتب سازی انتخابی
مزایا استفاده از الگوریتم مرتب سازی انتخابی را میتوان به صورت خلاصه در دو مورد بیان کرد.
- این الگوریتم فرایند درک و یادگیری سادهای دارد. به همین ترتیب پیادهسازی و استفاده این الگوریتم کار سادهای است.
- در مقابل مجموعه دادههای کوچک بسیار خوب عمل میکند.
عیب های مرتب سازی انتخابی
معایب این الگوریتم را میتوان به صورت خلاصه در سه مورد زیر بیان کرد.
- پیچیدگی زمانی این الگوریتم در حالتهای میانگین و بد برابر با است.
- بر روی مجموعه دادههای بزرگ به خوبی کار نمیکند.
- نظم نسبی عناصری که مقدار برابر دارند را حفظ نمیکند. در نتیجه الگوریتمی ناپایدار است.
آمادگی برای شرکت در آزمونهای دانشگاهی مربوط به طراحی الگوریتم
این قسمت از مطلب به طور ویژه مناسب دانشجویانی ارائه شده که نه تنها میخواهند روش نوشتن صحیح الگوریتمها را بیاموزند بلکه باید برای آزمونهای دانشگاهی و کنکور ارشد نیز آماده شوند. وبسایت آموزشی فرادرس در این زمینه به طور ویژه فیلمهای بسیار خوبی را تولید و ارائه کرده است. این سری از فیلمهای آموزشی درباره طراحی، نوشتن و کار با الگوریتمها و با استفاده از اساتید حرفهای تهیه کرده شدهاند. در این فیلمهای آموزشی به تجزیه و تحلیل سوالات کنکور سالهای متمادی در سطوح کارشناسی ارشی و دکتری پرداخته شده است.
![مجموعه آموزش طراحی الگوریتم](https://blog.faradars.org/wp-content/uploads/2024/04/Algorithm-design-and-data-structure-series.png)
در فهرست زیر چند مورد از این فیلمهای آموزشی را معرفی کردهایم. این فیلمها هم برای دانشجویان، هم برای برنامهنویسان و هم برای افرادی مفید است که میخواهند با مبحث طراحی الگوریتم تا حد بسیار خوبی آشنا شوند.
- فیلم آموزشی طراحی الگوریتم همراه با مرور و تست کنکور ارشد فرادرس
- فیلم آموزش پیشرفته ساختمان داده به همراهحل سوالات کنکور ارشد و دکتری فرادرس
- فیلم آموزش روش تقسیم و حل در طراحی الگوریتم همراه با مرور و تست کنکور کارشناسی ارشد فرادرس
- فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته بههمراه مرور و تست کنکور ارشد فرادرس
جمع بندی
الگوریتم «مرتب سازی انتخابی» (Selection sort) رویکرد بسیار سرراستی را برای مرتبسازی دادهها - به خصوص وقتی مجموعه داده کوچک باشد - ارائه میدهد. سادگی این الگوریتم در درک روش کار و پیادهسازی، آن را به گزینهای بسیار خوب برای شروع آشنایی با الگوریتمهای مرتبسازی تبدیل کرده است. با اینکه مرتبسازی انتخابی شاید کارآمدترین الگوریتم برای اجرای عملیات مرتبسازی بر روی مجموعه دادههای بزرگ نباشد اما هنوز هم کاربردهای عملی دارد. همچنین به عنوان پایهای برای بررسی بیشتر در الگوریتمهای مرتبسازی پیچیدهتر عمل میکند.
در این مطلب از مجله فرادرس، با الگوریتم مرتب سازی انتخابی آشنا شدیم. ابتدا روش کار این الگوریتم را یاد گرفتیم و سپس شبهه کدی را دیدیم که میتواند پایه مناسبی برای نوشتن کدهای این الگوریتم باشد. مرحله بعد، کدهای مربوط به مرتبسازی انتخابی را با هفت زبان برنامهنویسی رایج بین کاربران نوشتیم. در آخر هم پیچیدگیهای فضایی و زمانی این الگوریتم را بررسی کردیم.