9.1.2. Метод прямого вибору

При сортуванні цим методом фіксується перший лівий елемент масиву й проглядається права частина масиву (N-1) елементів. Шукається найменший елемент праворуч. Якщо знайдений елемент менше першого, він переставляється з першим елементом. Далі фіксується другий елемент масиву й проглядаються (N-2) елементів праворуч. Розшукується найменший елемент і переставляється з елементом 2. Подібна процедура триває доти, поки не залишиться найбільший елемент.

Наведемо приклад функції selectSort, що здійснює сортування масиву методом прямого вибору: У списку аргументів є: покажчик на масив *a; розмір масиву num; посилання на змінну &mov, що враховує число пересилань..

void selectSort(int *a, int num, int &mov){

for (int i=0; i<num-1; i++){ //Задати лівий ел-т

int min = i; //Змінна для індексу мінімального ел-та

for (int j=i+1; j<num; j++) //Задати правий ел-т

if (a[j]<a[min]) min=j; //Порівняти із мінімальним

if (min!=i){ //Якщо знайдено ел-т, що менше лівого

swap(a[min],a[i]); //Переставити лівий і мінімальний

mov+=3;

display(a, num); //Вивести на екран перестановку };

}

}

Приклад сортування масиву методом вибору (білим кольором показані елементи, які не змінюються при ітерації, сірим кольором – елементи, що міняються місцями):

Вихідний масив	22	19	14	23	18
1-я ітерація	14	19	22	23	18
2-я ітерація	14	18	22	23	19
3-я ітерація	14	18	19	23	22
4-я ітерація	14	18	19	22	23

9.1.3. Метод вставок

Елементи масиву розміром N умовно розділяють на готову (упорядковану) послідовність і вхідну послідовність. Спочатку в готову послідовність включається один елемент – a[0]. Вхідна послідовність починається з елемента a[1]. Ці елементи порівнюються, і якщо a[1]<a[0], елементи обмінюються місцями. На кожній ітерації вибирається перший елемент вхідної послідовності й передається в готову послідовність шляхом вставки. Місце вставки визначається порівнянням цього елемента з елементами готової послідовності. Ітерації тривають, поки довжина готової послідовності не стане рівній N.

Запишемо функцію сортування методом вставок insertSort, у списку аргументів якої: *a - покажчик на масив; num - розмір масиву; &mov - посилання на змінну, що враховує число пересилань.

void insertSort(int *a, int num, int &mov){

int i, j, key;

for(i = 1; i <num; i++){ //Взяти 1-й ел-т вхідної посл-сті

key = a[i];

mov++;

j = i - 1;

while (a[j] > key){ //Порівняти ел-ти готової посл-ти з key,

a[j+1] = a[j]; //Ел-ти > key зсунути вправо на 1 позицію

mov++;

j--;

}

if(a[j+1]!=key){ //Вилучити перестановки однакових ел-тів

a[j+1] = key; //Вставити key у місце, що звільнилося mov++;

display(a, num);

}

}

}

Наведемо приклад сортування методом включень (білі комірки - вхідна послідовність, сірі комірки - готова послідовність):

Вихідний масив	22	19	14	23	18
1-я ітерація	19	22	14	23	18
2-я ітерація	14	19	22	23	18
3-я ітерація	14	19	22	23	18
(N-1)-я ітерація, вхідна послідовність вичерпана	14	18	19	22	23

Відзначимо, що у функції сортування insertSort завдяки умові if(a[j+1]!=key) виключені ітерації, при яких не виконується вставка (у даному прикладі – це 3-я ітерація).