Алгоритм сортировки выбора

В этом руководстве вы узнаете, как работает сортировка по выбору. Также вы найдете рабочие примеры сортировки выбора на C, C ++, Java и Python.

Сортировка по выбору - это алгоритм, который выбирает наименьший элемент из несортированного списка на каждой итерации и помещает этот элемент в начало несортированного списка.

Как работает сортировка по выбору?

  1. Установите первый элемент как minimum. Выберите как минимум первый элемент
  2. Сравните minimumсо вторым элементом. Если второй элемент меньше minimum, присвоить второму элементу значение minimum.
    Сравните minimumс третьим элементом. Опять же, если третий элемент меньше, то назначьте minimumего третьему элементу, иначе ничего не сделайте. Процесс продолжается до последнего элемента. Сравните минимум с остальными элементами
  3. После каждой итерации minimumпомещается в начало несортированного списка. Поменять первый на минимум
  4. Для каждой итерации индексация начинается с первого несортированного элемента. Шаги с 1 по 3 повторяются до тех пор, пока все элементы не будут размещены на своих правильных позициях. Первая итерация Вторая итерация Третья итерация Четвертая итерация

Алгоритм сортировки выбора

 selectionSort (array, size) repeat (size - 1) раз установить первый несортированный элемент как минимум для каждого из несортированных элементов if element <currentMinimum установить элемент как новый минимальный минимум подкачки с первой несортированной позицией 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-й (п-1)
2-й (п-2)
3-й (п-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)

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