У цьому підручнику ви дізнаєтесь, як працює сортування виділення. Крім того, ви знайдете робочі приклади сортування виділень на C, C ++, Java та Python.
Сортування виділення - це алгоритм, який вибирає найменший елемент із невідсортованого списку в кожній ітерації та розміщує цей елемент на початку несортованого списку.
Як працює сортування виділення?
- Встановіть перший елемент як
minimum.
Виберіть перший елемент як мінімум - Порівняйте
minimumз другим елементом. Якщо другий елемент меншеminimum, призначте другий елемент якminimum.
Порівняйтеminimumз третім елементом. Знову ж таки, якщо третій елемент менший, тоді призначтеminimumтретьому елементу, інакше нічого не робіть. Процес триває до останнього елемента.
Порівняйте мінімум з рештою елементів - Після кожної ітерації
minimumрозміщується в передній частині несортованого списку.
Поміняйте перший місце мінімальним - Для кожної ітерації індексація починається з першого невідсортованого елемента. Крок 1-3 повторюється, поки всі елементи не будуть розміщені у правильних положеннях.
Перша ітерація 
Друга ітерація 
Третя ітерація 
Четверта ітерація
Алгоритм сортування вибору
selectionSort (масив, розмір) повтор (розмір - 1) разів встановити перший невідсортований елемент як мінімум для кожного з несортованих елементів, якщо елемент <currentMinimum встановити елемент як новий мінімальний мінімум підкачки з першим невідсортованим положенням кінця selectionSort
Приклади Python, Java та C / C ++
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Складність
| Цикл | Номер порівняння |
|---|---|
| 1-й | (n-1) |
| 2-й | (n-2) |
| 3-й | (n-3) |
| … | … |
| останній | 1 |
Кількість порівнянь: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2майже дорівнює .n2
Складність =O(n2)
Крім того, ми можемо проаналізувати складність, просто спостерігаючи за кількістю петель. Є 2 петлі, тож складність .n*n = n2
Складність часу:
- Найгірша складність: якщо ми хочемо сортувати за зростанням, а масив - за спаданням, тоді трапляється найгірший випадок.
O(n2) - Складність найкращого випадку: Це відбувається, коли масив уже відсортований
O(n2) - Середня складність справи: Це відбувається, коли елементи масиву розташовані в порядку перемішування (ні за зростанням, ні за спаданням).
O(n2)
Складність часу сортування у всіх випадках однакова у всіх випадках. На кожному кроці ви повинні знаходити мінімальний елемент і ставити його в потрібне місце. Мінімальний елемент невідомий, поки не буде досягнуто кінець масиву.
Складність простору:
Складність простору полягає в O(1)тому, що використовується додаткова змінна temp.
Програми для сортування за вибором
Сортування виділення використовується, коли:
- слід відсортувати невеликий список
- вартість обміну не має значення
- перевірка всіх елементів є обов'язковою
- вартість запису в пам'ять має значення, як у флеш-пам'яті (кількість записів / обмінів
O(n)порівняно з сортуванням у міхурах)O(n2)
