Сортування масивів в C - Курсовая работа

В наш час нові інформаційні технології посідають дуже важливе місце не лише в спеціалізованих, але й в повсякденних сферах життя. Компютери застосовуються в бізнесі, менеджменті, торгівлі, навчанні та багатьох інших сферах діяльності людини. Тому, кожна окрема галузь, яка використовує специфічні технічні засоби, потребує своїх власних програм, які забезпечують роботу компютерів. Розробкою програмного забезпечення займається така галузь науки, як програмування. У практиці програмування дуже часто виникає необхідність у впорядкуванні елементів використовуваних структур даних за якою-небудь ознакою, або, як іноді кажуть, за яким-небудь „ключем”.У подальшому розгляді ми будемо виходити з принципового допущення, що група даних, в якій треба шукати заданий елемент, є фіксованою. Будемо вважати, що множина з n елементів задана у вигляді масиву a типу t, де масив a та тип t описано наступним чином: тип t = масив [1..n] із t; Виникає питання: чи можна знайти у масиві потрібний елемент за меншу кількість кроків? Ідея методу пошуку, який називають бінарним, полягає у наступному: На кожному кроці алгоритму шукаємо x серед елементів масиву від нижньої до верхньої границі. Ось приклад функції, яка здійснює такий пошук. int binary_search(int a[], int low, int high, int target) {while (low <= high) {int middle = low (high - low)/2;Сортуванням називають впорядкування елементів деякої структури даних, на якій визначено відношення порядку, по ключах (тобто за якою-небудь ознакою).Сортування включенням - простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг: · простота у реалізації; · на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною; Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням.При сортуванні вибором на кожному кроці, для 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<length;i ) {if(array[MININDEX]>array[j]) //Finds smallest numberАлгоритм засновано на порівнянні пар сусідніх елементів масиву. При необхідності елементи у парі міняються місцями. Так продовжується до впорядкування всіх елементів. Цей метод також відомий як „бульбашкове” сортування, оскільки за один крок зовнішнього циклу найменший („найлегший”) елемент серед розглянутих елементів масива переміщується до початку масива (немов би „спливає” нагору). #include void BUBBLESORT(int* array, int size)Сортування злиттям - алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй». T tmp_elems, //temp array to hold intermediate results, should be same size as array "elems" size_t size) {if (size <= 1) {return;} //nothing to sort const size_t left_size = size / 2; const size_t right_size = size - left_size; merge_sort(elems left_size, tmp_elems left_size, right_size);Перш ніж розглядати сортування, розглянемо процес поділу масива. Далі продовжують перегляд та обмін значень елементів, поки нарешті у лівій частині масива опиняться всі елементи, менші за x, а у правій частині - більші за x. Швидке сортування полягає у застосуванні поділу спочатку до всього масива, потім до лівої та правої частин масива, потім для частин цих частин і так далі, поки кожна з частин не буде складатись тільки з одного елемента (отже буде відсортованою).//Прототип функції: float x0 (float x1, float x2, float k); float y0 (float y1, float y2, float k); float z0 (float z1, float z2, float k); //Оголошення констант та змінних: float x1,x2,y1,y2,z1,z2,k; float x0 (float x1, float x2, float k) {return (x1 k*x2)/(1 k); } float y0 (float y1, float y2, float k){ return (y1 k*y2)/(1 k);} float z0 (float z1, float z2, float k){ return (z1 k*z2)/(1 k);}/* Обчислення значення складної функції */ /* Обчислити значення складної функції у: */ /* y=y=log(fabs(b*x) 1)*log(fabs(b*x) 1) , якщо x>=10; */ #include/* Обчислити всі значення функції: */ #include #include #include #include using namespace std;/* Обчислити із заданою точністю eps=0.

Зміст

Вступ

Розділ 1. Теоритична частина. Пошук та сортування одновимірних масивів

1.1 Пошук елемента в одновимірному масиві

1.2 Сортування одновимірних масивів

1.2.1 Сортування включенням

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

1.2.3 Обмінне сортування

1.2.4 Сортування злиттям

1.2.5 Швидке сортування

Розділ 2. Практична частина

2.1 Розробка лінійних алгоритмів та програм

2.2 Розробка розгалужених алгоритмів та програм

2.3 Розробка циклічних алгоритмів та програм

2.4 Розробка ітераційних алгоритмів та програм

2.5 Розробка алгоритмів та програм обробки одновимірного масиву

2.6 Розробка алгоритмів та програм обробки двовимірного масиву

2.7 Розробка програм обробки стрічок

2.8 Розробка програм для роботи зі структурами

2.9 Розробка програм для роботи з файлами

2.10 Розробка програм для графічного режиму

2.11 Розробка програм для роботи з класами та обєктами

Висновки

Список використаних джерел

Додатки