При сортуванні вибором на кожному кроці, для i від 1 до (n-1), знаходимо найменший елемент серед a[i], a[i+1], …, a[n] з номером k, після чого міняемо місцями елементи a[i] та a[k].
void selection (int* array, int length){.
for (int i=0;i.
{.
int minIndex=i;
for (int j=i;j.
{.
if (array[minIndex]>array[j]).
{.
//Finds smallest number.
minIndex=j;
}.
}.
int swapVal=array[i];
array[i]=array[minIndex];
array[minIndex]=swapVal;
} }.
Послідовність сортування масива по кроках:
Якщо розглянути необхідну кількість дій, то вона має порядок O (n2). Дійсно, зовнішній цикл виконується (n-1) раз, а на кожному його кроці внутрішній цикл виконується, в середньому, n div 2 раз.
Обмінне сортування
Алгоритм засновано на порівнянні пар сусідніх елементів масиву. При необхідності елементи у парі міняються місцями. Так продовжується до впорядкування всіх елементів. Цей метод також відомий як «бульбашкове» сортування, оскільки за один крок зовнішнього циклу найменший («найлегший») елемент серед розглянутих елементів масива переміщується до початку масива (немов би «спливає» нагору).
#include.
void bubbleSort (int* array, int size).
{.
//для швидшого сортування посортованих.
bool wasSwapped = true;
for (int i = 1; (i <= size) && wasSwapped; ++i).
{.
wasSwapped = false;
for (int j = 0; j < (size — i); ++j).
{.
if (array[j] > array[j + 1]).
{.
std:swap (array[j], array[j + 1]);
wasSwapped = true;
}.
}.
}.
}.
Якщо розглянути необхідну кількість дій, то вона має порядок O (n2). Зовнішній цикл виконується (n-1) раз, а на кожному його кроці внутрішній цикл виконується, в середньому, n div 2 раз. Взагалі, «бульбашкове» сортування відноситься до найменш ефективних методів. Дещо покращати його можна, чергуючи порядок проходу масива та зупиняючись, коли всі елементи відсортовано (дійсно, на кроках 6, 7 та 8 обмінного сортування наш масив вже відсортований та не змінюється). Такий модифікований алгоритм дістав назву «шейкерного» сортування.
Хоча шейкерне сортування дещо ефективніше за «бульбашкове», воно відноситься до простих методів сортування та вимагає порядку O (n2) операцій.
Розглянемо тепер швидкі методи сортування.
