Інші методи сортування

Обмінне сортування має свої переваги та недоліки. Його недоліком є невисока швидкість. Нижче наведено словесний опис алгоритмів [].

Сортування методом вибору

З вхідного масиву вибирається найменший (найбільший) елемент, який розміщується на перше місце результуючого масиву. Вибраний елемент вилучається з подальших перевірок шляхом присвоєння йому максимально (мінімально) можливого значення. Процедура перегляду елементів вхідного масиву продовжується до тих пір, доки останній його елемент не буде перенесено у результуючий масив.

Сортування методом перестановки за індексами

У масиві, що складається з N елементів, послідовним порівнянням у процесі пошуку знаходиться найменший (найбільший) елемент і запам’ятовується його індекс (К). Після перегляду всього масиву обмінюються місцями перший та К-й елементи. Процедура повторюється, починаючи з другого, третього, четвертого,…, (N-1)-го елементу.

Сортування підрахунком

Ідея методу базується на тому, що значення j-го елемента в упорядкованій послідовності перевищує рівно (j-1) інших елементів. Таким чином, попарно порівнюються усі елементи та підраховується, скільки з них менше (більше) кожного окремого елемента, що дозволяє визначити номер розглянутого елемента в упорядкованому масиві.

Приклад 3. Задано масив U(N) та натуральне число К. Упорядкувати елементи, починаючи з елементу з номером К, за зростанням. Для розв’язання цієї задачі застосуємо комбінований метод.

#include <stdio.h>

main()

{

float u[1000];

int i,n,k,j;

float tmp;

m:printf(“Ведіть розмірність масиву n та індекс k”);

scanf(“%d%%d”, &n, &k);

if(k>=1&&k<=n)

{

for(i=0;i<m;i++) scanf(“%g”, &u[i]);

printf(“Неупорядкований масив:”);

for(i=0;i<m;i++) printf(“%g”,u[i]);

printf(“\n”);

for(i=k-1;i<n;i++)

{

for(j=i;j<=n;j++)

{

if(u[j]<u[j+1])

{

tmp=u[j];u[j]=u[j+1];u[j+1]=tmp;

}

}

}

printf(“Упорядкований масив:”);

for(i=0;i<n;i++) printf(“%d”,u[i]);

}

else goto m;

return 0;

}

Практика показала, що розв’язання задачі на сортування елементів масиву доцільно подавати у вигляді таких етапів:

· ввести вхідний масив;

· надрукувати вхідний (не впорядкований масив);

· визначити номери початкового та кінцевого елементів тієї частини масиву, яка підлягає сортуванню;

· здійснити сортування;

· вивести впорядкований масив.

Контрольні питання

1. Сортування елементів масиву – що це?

2. Як відсортувати масив за:

· зростанням;

· спаданням?

3.

Рис. 1. Блок-схема

Перечисліть пункти, з яких складається розв’язання задачі на сортування.

4. Перечисліть відомі вам методи сортування.

5. Наведіть (словесно) алгоритми розповсюджених методів сортування.