5. Методичні вказівки

1. Формування, друк і обробку масивів оформити у вигляді функції. Масиви передавати як параметри функцій.

2. Реалізувати масиви як псевдодінаміческіе, їх розмірності передавати як параметри функцій.

3. Формування масивів виконати з використанням ДСЧ. В масиви записувати і позитивні, і негативні числа.

6. Сортування масивів організувати за допомогою одного з простих методів сортування.

7. Функція main () повинна містити тільки опис масивів і виклики функцій для формування, друку та обробки масивів.

6. Зміст звіту

1. Постановка завдання (загальна і для конкретного варіанту).

2. Визначення функцій, використовуваних для формування, друку та обробки масивів (для кожного завдання).

3. Визначення функції main ().

4. Результати тестів.

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

1. Яким чином можна визначити кількість елементів у рядку символів?

2. У чому відмінність оформлення списку параметрів, коли відомо і не відомо кількість елементів у вхідному для функції масиві?

3. Що являє собою ім'я масиву і як воно зв'язане з нульовим елементом масиву?

4. Яким чином можна одержати як результат виконання функції масив?

5. Як визначаються в С++ багатомірні масиви?

6. Поясніть зв'язок між масивами і вказівниками.

Практична робота № 14

Тема: Сортування масивів за допомогою основних методів сортування

1. Мета завдання:

1) Створення алгоритмів простих методів сортування масивів.

2) Придбання навичок створення програм простих методів сортування масивів.

2. Теоретичні відомості

2.1 Сортування бульбашкою

Алгоритм сортування бульбашкою, як і сортування вибором порівняно неефективний. Його приблизний час роботи О(n^2), де n - кількість елементів масиву.

Цей метод сортування характеризується дуже простим кодом і алгоритмом. Наведу по-кроково роботу сортування бульбашкою:

5 4 3 2 1 // початкова послідовність елементів

4 5 3 2 1

4 3 5 2 1

4 3 2 5 1

4 3 2 1 5

3 4 2 1 5

3 2 4 1 5

3 2 1 4 5

2 3 1 4 5

2 1 3 4 5

1 2 3 4 5 // результат

Сортування бульбашкою «пробігає» починаючи з першого елементу масиву до останнього. При цьому кожен елемент порівнюється з наступним. Якщо наступний елемент менший за попередній, міняє їх місцями. Дані операції тривають до тих пір, поки найменший елемент не стане першим в масиві. Потім починаємо ті ж операції з другого елементу, третього і так до кінця.

Ми порівнюємо 1 і 2 елементи масиву і якщо 1 більше 2 то міняємо їх місцями; потім порівнюємо 2 і 3 елементи... і так до кінця, поки не завершимо перший прохід.

Якщо зробити n-1 проходів то ми повністю відсортуємо всі n елементів.

В наступному прикладі вже після переходу i=7 буде видно кінцевий результат (і вже можна припиняти роботу miniaty = false)

Рисунок 15 – Схема сортування масива методом бульбашки

Білі клітинки - це клітинки з вже відсортованими найбільшими елементами, які вже не треба порівнювати.

C++ функція що сортує масив чисел arr[ ] і складається з n елементів має наступний вигляд: 1. Суть.

for(j= 0; j < n - 1; j++)

{ for(i = 0; i < n - 1; i++)

{

if (arr[i] > arr[i + 1])

{// перевірка, якщо так, то міняти місцями

tmp = arr[i]; // зберігаємо і

arr[i] = arr[i + 1]; // в і кладемо і+1

arr[i + 1] = tmp; // в і+1 кладемо і

}

}

}

Аналогічне сортування можна виконати, коли найбільший елемент буде «спливати», а найменший «тонути», тобто навпаки.

Реалізація алгоритму:

#include <iostream>

#include <cstdlib>

using namespace std;

const int SIZE = 25;

int array[SIZE];

// заповнення масиву випадковими числами

void GenerationArray()

{

// прив'язка до часу для генерації чисел без повторень

srand(time(0));

for (int i=0; i<SIZE; i++)

{

// заповнення масиву числами <100

array[i] = rand()%100;

}

}

// виведення масиву на екран

void ShowArray()

{

for (int i=0; i<SIZE; i++)

{

cout << array[i] << " ";

}

cout << endl;

}

int main()

{

int temp;

GenerationArray();

ShowArray();

// сортування бульбашкою

for (int x=SIZE; x>0; x--)

{

for (int i=0; i<SIZE-1; i++)

{

// якщо число більше за попереднє

if (array[i] > array[i+1])

{

// міняємо їх місцями

temp = array[i];

array[i] = array[i+1];

array[i+1] = temp;

}

}

}

ShowArray();

return 0;

}

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

Головною проблемою сортування бульбашкою є велика кількість перестановок елементів. В сортуванні вибором ця проблема вирішена. Тут елемент відразу займає свою кінцеву позицію.

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

Рисунок 16 – Перший крок

Якщо відшукано min, то він обмінюється значенням з першим елементом.

Потім операція повторюється для підмасиву a[2..n]:

Рисунок 17 – Повторення операції

і т.д.

Покрокова робота сортування:

5 4 6 9 3 2 1 7 8 // початкова послідовність

1 4 6 9 3 2 5 7 8

1 2 6 9 3 4 5 7 8

1 2 3 9 6 4 5 7 8

1 2 3 4 6 9 5 7 8

1 2 3 4 5 9 6 7 8

1 2 3 4 5 6 9 7 8

1 2 3 4 5 6 7 9 8

1 2 3 4 5 6 7 8 9 // результат

Принцип сортування: масив також поділяється на відсортовану та невідсортовану частини. На першому кроці весь масив - невідсортований. У невідсортованій частині знаходиться мінімальний (або максимальний) елемент та міняється місцями з першим елементом невідсортованої частини. Межа відсортованої частини зсувається вправо на 1. Процедура виконується ціклічно, n-1 раз (останній елемент пересувати не треба ).

Один елемент завжди можна вважати відсортованим масивом довжини 1. Розглядаючи послідовно решту елементів масиву будемо включати їх у відсортовану частину масиву, ставлячи на потрібне місце, тобто не порушуючи відсортованості цієї частини. Повторивши операцію включення n-1 раз, одержимо відсортований масив.

Приклад. Візьмемо кілька випадкових чисел:

Рисунок 18 – Схема сортування масиву вибором

Весь масив відсортовано.

На і-му кроці вважається масив a[1]…a[i], а вставляємо елемент a[i+1]. Вставляти можна, послідовно порівнюючи a[i+1] з a[1], a[2],…, поки не знайдеться «дірка» j.

Тоді слід зсунути елементи a[j+1] .. a[i] вправо на один елемент, а a[i+1] записати на місце a[j+1].

Може статися, що a[i+1] більше за будь-який з членів відсортованої частини. Тоді дірку не буде знайдено. Тому слід контролювати номер j, щоб не вийти за межі відсортованої частини.

Реалізація алгоритму:

#include <iostream>

#include <cstdlib>

using namespace std;

const int SIZE = 25;

int array[SIZE];

// заповнення масиву випадковими числами

void GenerationArray()

{

// прив'язка до часу для генерації чисел без повторень

srand(time(0));

for (int i=0; i<SIZE; i++)

{

// заповнення масиву числами <100

array[i] = rand()%100;

}

}

// виведення масиву на екран

void ShowArray()

{

for (int i=0; i<SIZE; i++)

{

cout << array[i] << " ";

}

cout << endl;

}

int main()

{

int temp, start = 0, min_position, min_element;

GenerationArray();

ShowArray();

// сортування вибором

while (start != SIZE-1)

{

// припустимо, що елемент з індексом лівої межі мінімальний

min_element = array[start];

// запам'ятовуємо індекс цього елемента

min_position = start;

// шукаємо мінімальний елемент у підмасиві

for (int i=start; i<SIZE; i++)

{

if (array[i] < min_element)

{

min_element = array[i];

min_position = i;

}

}

// якщо елемент з індексом лівої межі не мінімальний,

// міняємо його місцями з знайденим мінімальним числом

if (min_position != start)

{

temp = array[start];

array[start] = array[min_position];

array[min_position] = temp;

}

start++;

}

ShowArray();

return 0;

}

Час сортування 100 тисяч елементів сортуванням бульбашкою склав 1 хвилину 38.731 секунд, у той час як алгоритм сортування вибором виконав це завдання за 28.313 секунд. Але все одно обидва алгоритми не підходять для сортування великих масивів чисел. При збільшенні числа елементів у 10 разів, кількість циклів буде зростати в 100(!) разів. Для таких обсягів чисел існують інші алгоритми сортування, про які ми дізнаємося у наступній серії нашої передачі;)