Сортировка выбором — довольно простой метод сортировки, поскольку он включает в себя только поиск наименьшего элемента в каждом проходе и размещение его в правильном положении.
Как следует из самого названия, метод сортировки выбором сначала выбирает наименьший элемент в массиве, а затем меняет его местами с первым элементом в массиве. Затем он меняет местами второй наименьший элемент в массиве со вторым элементом и так далее.
Таким образом, для каждого прохода выбирается наименьший элемент в массиве и помещается в правильное место до тех пор, пока весь массив не будет отсортирован.
Сортировка выбором работает эффективно, когда сортируемый список имеет небольшой размер, но его производительность сильно снижается по мере увеличения размера сортируемого списка.
Следовательно, мы можем сказать, что сортировка выбором не рекомендуется для больших списков данных.
Общий алгоритм сортировки выбором приведен ниже:
Сортировка выбором (A, N)
Шаг 1: Повторить шаги 2 и 3 для значений от K = 1 до N-1
Шаг 2: Вызов наименьшей процедуры (A, K, N, POS)
Шаг 3: Поменять местами A[K] на A [POS]
[Конец цикла]
Шаг 4: вывод данных
Обычный наименьший (A, K, N, POS)
Шаг 1: [инициализация] установить наименьший элемент = A[K]
Шаг 2: [инициализация] установить POS = K
Шаг 3: для J = K+1 до N-1, повторить,
если наименьший элемент > A [J]
установить наименьший элемент = A [J]
установить POS = J
[если конец]
[конец цикла]
Шаг 4: возврат POS
Псевдокод для сортировки выбором
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Процедура selection_sort(array,N) array – массив элементов, подлежащих сортировке N – размер массива начала массива for I = 1 to N-1 начать установить min = i for j = i+1 to N начать если array[j] < array[min] тогда min = j; закончить если закончить для //замените минимальный элемент текущим элементом если minIndex != I тогда поменять местами массив[min[] и массив[i] закончить если закончить для завершение процедуры |
Пример алгоритма сортировки выбором, показан ниже:
Приведенные выше схемы можно обобщить в табличной форме:
| Несортированный список | Наименьший элемент | Отсортированный список |
| {18,10,7,20,2} | 2 | {} |
| {18,10,7,20} | 7 | {2} |
| {18,10,20} | 10 | {2,7} |
| {18,20} | 18 | {2,7,10) |
| {20} | 20 | {2,7,10,18} |
| {} | {2,7,10,18,20} |
Из таблицы видно, что при каждом проходе следующий наименьший элемент помещается в нужное (правильное) место в отсортированном массиве. Из приведенных выше схем ясно, что для сортировки массива из 5 элементов потребовалось четыре прохода. Это означает, что в общем случае для сортировки массива из N элементов нам потребуется всего N-1 проходов.
Ниже приведена реализация алгоритма сортировки выбором на C++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> using namespace std; int findSmallest (int[],int); int main () { int myarray[10] = {11,5,2,20,42,53,23,34,101,22}; int pos,temp,pass=0; cout<<"\n Input list of elements to be Sorted\n"; for(int i=0;i<10;i++) { cout<<myarray[i]<<"\t"; } for(int i=0;i<10;i++) { pos = findSmallest (myarray,i); temp = myarray[i]; myarray[i]=myarray[pos]; myarray[pos] = temp; pass++; } cout<<"\n Sorted list of elements is\n"; for(int i=0;i<10;i++) { cout<<myarray[i]<<"\t"; } cout<<"\nNumber of passes required to sort the array: "<<pass; return 0; } int findSmallest(int myarray[],int i) { int ele_small,position,j; ele_small = myarray[i]; position = i; for(j=i+1;j<10;j++) { if(myarray[j]<ele_small) { ele_small = myarray[j]; position=j; } } return position; } |
Вывод данных:
| Введите список элементов для сортировки: 11 5 2 20 42 53 23 34 101 22 Отсортированный список элементов: 2 5 11 20 22 23 34 42 53 101 Количество проходов, необходимых для сортировки массива: 10 |
Как показано в приведенной выше программе, мы начинаем сортировку выбором, сравнивая первый элемент массива со всеми остальными элементами массива. В конце этого сравнения наименьший элемент массива помещается на первую позицию.
На следующем проходе, используя тот же подход, следующий наименьший элемент в массиве помещается в правильное положение. Это продолжается до N элементов или до тех пор, пока не будет отсортирован весь массив.
Далее мы реализуем технику сортировки выбором на языке Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Main { public static void main(String[] args) { int[] a = {11,5,2,20,42,53,23,34,101,22}; int pos,temp; System.out.println("\nInput list to be sorted...\n"); for(int i=0;i<10;i++) { System.out.print(a[i] + " "); } for(int i=0;i<10;i++) { pos = findSmallest(a,i); temp = a[i]; a[i]=a[pos]; a[pos] = temp; } System.out.println("\nprinting sorted elements...\n"); for(int i=0;i<10;i++) { System.out.print(a[i] + " "); } } public static int findSmallest(int a[],int i) { int smallest,position,j; smallest = a[i]; position = i; for(j=i+1;j<10;j++) { if(a[j]<smallest) { smallest = a[j]; position=j; } } return position; } } |
Вывод данных:
| Список ввода для сортировки… 11 5 2 20 42 53 23 34 101 22 печать отсортированных элементов… 2 5 11 20 22 23 34 42 53 101 |
В приведенном выше примере на Java, мы применяем ту же логику. Мы многократно находим наименьший элемент в массиве и помещаем его в отсортированный массив, пока весь массив не будет полностью отсортирован.
Таким образом, сортировка выбором — самый простой алгоритм для реализации, поскольку нам просто нужно многократно находить следующий наименьший элемент в массиве и заменять его элементом в соответствующей позиции.
Анализ сложности сортировки выбором
Как видно из приведенного выше псевдокода для сортировки выбором, что сортировка выбором требует двух циклов for, вложенных друг в друга, для своего завершения. Один цикл for проходит через все элементы в массиве, и мы находим индекс минимального элемента, используя другой цикл for, который вложен во внешний цикл for.
Следовательно, при заданном размере N входного массива алгоритм сортировки выбором имеет следующие значения времени и сложности:
| Временная сложность в худшем случае | O( n 2 ) ; O(n) свопов |
| Временная сложность в лучшем случае | O( n 2 ) ; O(n) свопов |
| Средняя временная сложность | O( n 2 ) ; O(n) свопов |
| Пространственная сложность | O(1) |
Временная сложность O( n 2 ) в основном связана с использованием двух циклов for. Обратите внимание, что метод сортировки выбором никогда не требует больше O(n) свопов и полезен, когда операция записи в память оказывается трудоемкой.
Итог
Сортировка выбором — еще один простейший метод сортировки, который можно легко реализовать. Сортировка выбором работает лучше всего, когда известен диапазон сортируемых значений. Таким образом, что касается сортировки структур данных с использованием сортировки выбором, мы можем сортировать только структуры данных, которые являются линейными и имеют конечный размер.
Это означает, что мы можем эффективно сортировать структуры данных, такие как массивы, используя сортировку выбором.
В этой статье мы подробно обсудили сортировку выбором, включая реализацию сортировки выбором с использованием языков C++ и Java. Логика сортировки выбором состоит в многократном поиске наименьшего элемента в списке и размещении его в нужном месте.
В следующей статье мы подробно узнаем о сортировке вставками, которая считается более эффективной, чем два других метода, которые мы обсуждали до них, т. е. пузырьковая сортировка и сортировка выбором.
С Уважением, МониторБанк