Сортування вибору це простий і ефективний алгоритм сортування, який працює шляхом повторного вибору найменшого (або найбільшого) елемента з невідсортованої частини списку та переміщення його до відсортованої частини списку.
Алгоритм кілька разів вибирає найменший (або найбільший) елемент із невідсортованої частини списку та міняє його місцями з першим елементом невідсортованої частини. Цей процес повторюється для решти невідсортованої частини, доки не буде відсортовано весь список.
Як працює алгоритм сортування вибору?
Рекомендована практика Вибір Сортування Спробуйте!Розглянемо як приклад наступний масив: arr[] = {64, 25, 12, 22, 11}
Перший прохід:
- Для першої позиції в сортованому масиві весь масив обходиться послідовно від індексу 0 до 4. Перша позиція де 64 зберігається наразі, після обходу всього масиву зрозуміло, що одинадцять є найменшим значенням.
- Таким чином, замініть 64 на 11. Після однієї ітерації одинадцять , яке є найменшим значенням у масиві, має тенденцію з’являтися на першій позиції відсортованого списку.
Алгоритм сортування вибору | Заміна 1-го елемента на мінімальний у масиві
Другий прохід:
- Для другої позиції, де присутній 25, знову послідовно перейдіть до решти масиву.
- Після обходу ми це виявили 12 є другим найнижчим значенням у масиві, і воно має відображатися на другому місці в масиві, таким чином помінявши ці значення місцями.
Алгоритм сортування вибору | заміна i=1 на наступний мінімальний елемент
Третій прохід:
- А тепер третє місце, де 25 присутній, знову пройдіть решту масиву та знайдіть третє найменше значення в масиві.
- Під час проходження, 22 виявилося третім найменшим значенням, і воно має з’явитися на третьому місці в масиві, отже, поміняти місцями 22 з елементом, присутнім на третій позиції.
Алгоритм сортування вибору | заміна i=2 на наступний мінімальний елемент
Четвертий прохід:
- Подібним чином, для четвертої позиції обійдіть решту масиву та знайдіть четвертий найменший елемент у масиві
- як 25 є 4-м найнижчим значенням, отже, він розміститься на четвертій позиції.
Алгоритм сортування вибору | заміна i=3 на наступний мінімальний елемент
П'ятий прохід:
- Нарешті найбільше значення в масиві автоматично розміщується в останній позиції в масиві
- Отриманий масив є відсортованим масивом.
Алгоритм сортування вибору | Необхідний відсортований масив
Нижче наведено реалізацію вищезазначеного підходу:
C++ // C++ program for implementation of // selection sort #include using namespace std; // Function for Selection sort 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 if (min_idx != i) 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 int main() { int arr[] = { 64, 25, 12, 22, 11 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call selectionSort(arr, n); cout << 'Sorted array:
'; printArray(arr, n); return 0; } // This is code is contributed by rathbhupendra> C // C program for implementation of selection sort #include 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 if(min_idx != i) 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++) printf('%d ', arr[i]); printf('
'); } // 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); printf('Sorted array:
'); printArray(arr, n); return 0; }> Java // Java program for implementation of Selection Sort import java.io.*; public class SelectionSort { void sort(int arr[]) { int n = arr.length; // One by one move boundary of unsorted subarray for (int i = 0; i < n-1; i++) { // Find the minimum element in unsorted array int min_idx = i; for (int j = i+1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first // element int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } // Prints the array void printArray(int arr[]) { int n = arr.length; for (int i=0; i Python3 # Python program for implementation of Selection # Sort A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)-1): # Find the minimum element in remaining # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx]>A[j]: min_idx = j # Поміняти місцями знайдений мінімальний елемент # першим елементом A[i], A[min_idx] = A[min_idx], A[i] # Код драйвера для перевірки над print ('Відсортований масив ') для i в діапазоні (len(A)): print(A[i],end=' ')> C# // C# program for implementation // of Selection Sort using System; class GFG { static void sort(int []arr) { int n = arr.Length; // One by one move boundary of unsorted subarray for (int i = 0; i < n - 1; i++) { // Find the minimum element in unsorted array int min_idx = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[min_idx]) min_idx = j; // Swap the found minimum element with the first // element int temp = arr[min_idx]; arr[min_idx] = arr[i]; arr[i] = temp; } } // Prints the array static void printArray(int []arr) { int n = arr.Length; for (int i=0; i Javascript >
PHP // PHP program for implementation // of selection sort function selection_sort(&$arr, $n) { for($i = 0; $i < $n ; $i++) { $low = $i; for($j = $i + 1; $j < $n ; $j++) { if ($arr[$j] < $arr[$low]) { $low = $j; } } // swap the minimum value to $ith node if ($arr[$i]>$arr[$low]) { $tmp = $arr[$i]; $arr[$i] = $arr[$low]; $arr[$low] = $tmp; } } } // Код драйвера $arr = array(64, 25, 12, 22, 11); $len = count($arr); сортування_вибору($arr, $len); echo 'Відсортований масив:
'; для ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed // by Deepika Gupta. ?>> Вихід
Sorted array: 11 12 22 25 64>
Аналіз складності вибіркового сортування
Часова складність: Часова складність Selection Sort становить O(N 2 ) оскільки є два вкладені цикли:
- Один цикл для вибору елементів масиву один за одним = O(N)
- Ще один цикл для порівняння цього елемента з усіма іншими елементами масиву = O(N)
- Тому загальна складність = O(N) * O(N) = O(N*N) = O(N2)
Допоміжний простір: O(1), оскільки єдина додаткова пам’ять використовується для тимчасових змінних під час заміни двох значень у масиві. Сортування вибору ніколи не виконує більше ніж O(N) обмінів і може бути корисним, коли запис у пам’ять є дорогим.
тестування продуктивності
Переваги алгоритму сортування вибору
- Простий і зрозумілий.
- Добре працює з невеликими наборами даних.
Недоліки алгоритму сортування вибору
- Сортування вибору має часову складність O(n^2) у найгіршому та середньому випадку.
- Погано працює з великими наборами даних.
- Не зберігає відносний порядок елементів з однаковими ключами, що означає, що він не стабільний.
Часті запитання щодо сортування вибору
Q1. Чи стабільний алгоритм сортування вибору?
Типовою реалізацією алгоритму сортування вибору є не стабільний . Однак його можна зробити стабільним. Будь ласка, перегляньте стабільне сортування вибору для деталей.
Q2. Чи працює алгоритм сортування вибору?
Так, алгоритм сортування вибору є алгоритмом на місці, оскільки він не вимагає додаткового місця.