Постановка задачи: выполнить сортировку целых чисел по возрастанию сортировкой выбором
Сначала приведем листинг программы. Попробуйте самостоятельно понять суть сортировки.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void select_sort(int* a, int n) { int imin, tmp; for (int i=0; i<n-1; i++) { imin=i; for (int j=i+1; j<n; j++) // www.itmathrepetitor.ru if (a[j]<a[imin]) imin=j; if (imin>i) { tmp=a[imin]; a[imin]=a[i]; a[i]=tmp; } } } |
Среди чисел a[0], a[1], …, a[n-1] находим наименьший элемент и меняем его местами с элементом a[0]. Далее рассматриваем числа a[1], …, a[n-1], то есть все, кроме первого элемента, и наименьший среди них меняем с числом a[1]. Далее продолжаем процесс аналогичным образом.
Сложность сортировки: \(\Theta (n^2)\). При больших \(n\) работает слишком медленно, на практике применяют крайне редко (как и сортировка пузырьком). Хотя простота и скорость написания такого кода иногда может оказаться значительным достоинством.
Код написан на С++. Индексы массива от 0 до n-1, если размер массива равен n.