Алгоритъм за сортиране на избора

В този урок ще научите как работи сортирането на подбора. Също така ще намерите работни примери за сортиране на подбор в C, C ++, Java и Python.

Сортирането по избор е алгоритъм, който избира най-малкия елемент от несортиран списък във всяка итерация и поставя този елемент в началото на несортирания списък.

Как работи сортирането на подбора?

  1. Задайте първия елемент като minimum. Изберете първия елемент като минимум
  2. Сравнете minimumс втория елемент. Ако вторият елемент е по-малък от minimum, присвоете втория елемент като minimum.
    Сравнете minimumс третия елемент. Отново, ако третият елемент е по-малък, тогава присвойте minimumна третия елемент иначе не правете нищо. Процесът продължава до последния елемент. Сравнете минимума с останалите елементи
  3. След всяка итерация minimumсе поставя в предната част на несортирания списък. Разменете първия с минимум
  4. За всяка итерация индексирането започва от първия несортиран елемент. Стъпки 1 до 3 се повтарят, докато всички елементи се поставят в правилните им позиции. Първата итерация Втората итерация Третата итерация Четвъртата итерация

Алгоритъм за сортиране на избора

 selectionSort (array, size) repeat (size - 1) пъти задайте първия несортиран елемент като минимум за всеки от несортираните елементи, ако елемент <currentMinimum set element като нов минимален минимум на суап с първа несортирана позиция end 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)

Интересни статии...