Курсовая работа: Порівняльний аналіз ефективності та складності прямих алгоритмів сортування масивів

1) на i -ому етапі серед елементів mas[i], mas[i+1],…,mas[n] вибирається елемент з найменшим ключем mas[j]=min ;

2) проводиться обмін місцями mas[j] та mas[i] .

Процес послідовного вибору і перестановки проводиться поки не залишиться один єдиний елемент - з самим найбільшим ключем.

Взагалі, існує декілька способів реалізації даного алгоритму. Можна використовувати два масиви і копіювати елементи в потрібному порядку із одного масиву в другий. Проте, це є більш затратний спосіб. Наведемо графічний аналіз реалізації самого методу. Нехай маємо задачу, на прикладі масиву, зображеного нижче. Спробуємо впорядкувати цей масив по зростанню.

На першому кроці переглядаємо весь масив від індексу 1 до індексу n (в даному випадку n=7 ) з метою пошуку найменшого елемента масиву. Далі беремо цей індекс на кожному кроці записуємо в комірку з індексом 0 . По закінченню проходження циклу міняємо елементи з індексом і- початкове та елемент індекс якого записаний у комірці під номером 0 .

Дальше переглядаємо масив вже без першого елемента, оскільки ж відомо що в ньому записаний найменший елемент масиву.

Маємо, що мінімальний елемент решти масиву знаходиться в позиції 5 , при його пошуку індекс заноситься в комірку з індексом 0 . Знову проводимо обмін.

Запишемо саму програму реалізації даного методу (Файл SORT_3.CPP):

#include <conio.h>

#include <iostream.h>

#include <stdlib.h>

int mas[1000];

void vuv(int s)

{ for(int i=1;i<=s;i++)

cout<<mas[i]<<‘ ‘;

cout<<endl<<"--------------------------------"<<endl;

}

main()

{clrscr();

cout<<"Vvedit kilkist elementiv masuvy - n"<<endl;

int n,tmp,k;

cin>>n;

for (int i=1;i<=n;i++)

{

cout<<"vvedit "<<i<<" -eltment masuvy"<<endl;