Прилади, устаткування та інструменти

Для виконання лабораторної роботи використовується ПЕОМ з установленим пакетом Sun Mіcrosystems JDK 1.5 і вище та інтегрованим середовищем розробки BlueJ або Eclipse. Для написання програми на Java може бути використаний будь-який текстовий редактор, наприклад, Notepad, WordPad в MS Wіndows і ін.

Правила техніки безпеки та охорони праці

Правила техніки безпеки при виконанні лабораторної роботи регламентуються «Правилами техніки безпеки при роботі в комп'ютерній лабораторії».

Порядок проведення лабораторної роботи

Для виконання роботи кожен студент повинен:

1. Відповісти на контрольні питання та пройти усне опитування за теоретичним матеріалом лабораторної роботи;

2. Пройти інструктаж за правилами охорони праці;

3. Отримати варіант завдання у викладача;

4. Скласти алгоритм розв’язання задачі;

5. Записати код програми на комп’ютері;

6. Відкомпілювати програму та виправити всі помилки;

7. Запустити програму на виконання;

8. Отримати результати роботи програми і показати їх викладачу;

9. Підготувати і захистити звіт до лабораторної роботи.

Оформлення і захист звіту

Підготовлений до захисту звіт до лабораторної роботи повинен містити:

1. титульний лист, де вказані номер і назва лабораторної роботи, відомості про виконавця;

2. номер варіанта роботи та текст завдання;

3. відповіді на контрольні запитання до лабораторної роботи;

4. текст програми алгоритмічною мовою Java;

5. лістинг результатів виконання програми.

Лабораторна робота № 1.2

Тема: «Прості та покращені алгоритми сортування»

Мета роботи

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

Завдання до лабораторної роботи

Використовуючи алгоритми, розглянуті на практичному занятті, скласти програму розрахунку заданих величин.

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

Лабораторна робота спирається на знання й уміння, отримані при вивченні наступних тем лекційного курсу:

- Прості алгоритми сортування: обмін, вибір, вставка.

- Покращені алгоритми сортування –сортування Шелла, сортування Хоара (швидке сортування), сортування злиттям.

- Аналіз обчислювальної складності алгоритмів сортування

Тому під час підготовки до лабораторної роботи рекомендується повторити зазначені розділи дисципліни.

Розглянемо фрагменти програм, де використовуються алгоритми сортуваньмасивів:

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

public static void bubbleSort(int[] data) {

int n = data.length;

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

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

if (data[j] > data [j+1]) {

int tmp = data[j];

data[j] = data[j+1];

data[j+1] = tmp;

} }

}}

Сортування двійковими вставками

public static void binInsertSort(int[] data) {

int n = data.length; // Длина массива

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

int c = data[i]; // Вставляемое значение

// Организация поиска места для вставки значения c

int low = 0, high = i;

// Inv : (low <= high) && место для c - внутри data[low:high]

while (low < high) {

int m = (low+high) >> 1;

// low <= m < high

if (data[m] < c) low = m+1; else high = m;

}

// Найдено место вставки - low

// Сдвигаем элементы в сторону больших индексов.

for (int j = i-1; j >= low; j--) {

data[j+1] = data[j];

}

// Заносим значение на найденное место

data[low] = c;

}

}

Сортування Шелла

public static void ShellSort(int[] data) {

int n = data.length; // Длина массива

int step = n; // Шаг поисков и вставки

int i, j;

do {

// Вычисляем новый шаг

step = step / 3 + 1;

/ / Виробляємо сортування простими вставками з заданим кроком

for (i = step; i < n; i++) {

int c = data[i];

for (j = i-step; j >= 0 && data[j] > c; j -= step) {

data[j+step] = data[j];

}

data[j+step] = c;

}

} while (step != 1);}

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

Сортування злиттям сортує заданий масив шляхом розділення його на дві половини і , рекурсивного сортування кожної половини і злиття двох відсортованих половин в один відсортований масив

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

Сортування методом злиття в асимптотичній межі поводиться як ), що краще, ніж , але процедура злиття, яка використовується в цьому алгоритмі, не працює без додаткової пам`яті.

//Алгоритм злиття впорядкованих масивів

public static int[] merge(int[] a, int[] b) {

int na = a.length,

nb = b.length,

nc;

int[] c = new int[nc = na + nb];

int ia = 0,

ib = 0,

ic = 0;

while (ia < na && ib < nb) {

if (a[ia] < b[ib])

c[ic++] = a[ia++];

else

c[ic++] = b[ib++];

}

while (ia < na) c[ic++] = a[ia++];

while (ib < nb) c[ic++] = b[ib++];

return c;

}

Пірамідальна сортування

public static void heapSort(int[] data) {

int n = data.length; // Довжина масиву

buildPyramid: // Побудова піраміди

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

int c = data[i];

int p = i, q;

do { q = p;

if ((p = (q-1) >> 1) >= 0 && data[p] < c) data[q] = data[p];

else {

data[q] = c;

continue buildPyramid;

}

} while (true);

}

meltPyramid: // Поступове руйнування піраміди

for (int i = n-1; i > 0; i--) {

int c = data[i];

data[i] = data[0];

int q, p = 0;

do { q = p;

p = (q << 1) | 1;

if (p >= i) { // Вышли за границу пирамиды

data[q] = c;

continue meltPyramid;

}

if (p < i-1 && data[p+1] > data[p]) p++;

if (data[p] > c) data[q] = data[p];

else {

data[q] = c;

continue meltPyramid;

}

} while (true);

}

}

Швидке сортування (Хоара)

Швидке сортування– важливий алгоритм сортування, ґрунтований на методі декомпозиції. На відміну від сортування злиттям, яке розділяє елементи масиву відповідно до їх положення в масиві, швидке сортування розділяє елементи масиву відповідно до їх значень. Конкретно, воно виконує перестановку елементів цього масиву для отримання розбиття, коли усі елементи до деякої позиції не перевищують елементу , а елементи після позиції не менше . В силу важливості ролі елементу він називається опорним

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

public static void quickSort(int[] data) {

quickSort(data, 0, data.length-1);

}

private static void quickSort(int[] data, int from, int to) {

if (to-from < 50)

// Небольшие фрагменты быстрее сортировать методом простых вставок

simpleSort(data, from, to);

else {

int c = data[from]; // Выбираем некоторый элемент

/ Распределяем элементы массива на значения меньшие и большие c.

int low = from, high = to+1;

// Inv: (low <= high) && data[from:(low-1)] <= c && data[high:to] >= c

while (low < high) {

while (low < high && data[--high] >= c) ;

data[low] = data[high];

while (low < high && data[++low] <= c) ;

data[high] = data[low];

}

// Вставляем элемент на свое место

data[low] = c;

// Независимо сортируем верхнюю и нижнюю половины массива

quickSort(data, from, low-1);

quickSort(data, low+1, to);

}}

Цифрове сортування

public static void digitSort(int[] data) {

int n = data.length;

int[] data2 = new int[n];

for (int step = 0; step < 8; step++) {

// step - номер "цифры"

// Сортировка "подсчетом" по цифре с заданным номером

countSort(data, step, data2);

int[] temp = data; data = data2; data2 = temp;

}

}

private static void countSort (int[] src, int nDig, int[] dest) {

int n = src.length;

int[] count = new int[16];

// 1. Подсчет

nDig <<= 2;

for (int i = 0; i < n; i++) {

count[(src[i] & (0xF << nDig)) >> nDig]++;

}

// 2. Суммирование

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

count[i] += count[i-1];

}

// 3. Расстановка

for (int i = n-1; i >= 0; i--)

{

dest[--count[(src[i] & (0xF << nDig)) >> nDig]] = src[i];

}

}

Приклад програми

Дан масив data = {2,9,6,4,8,3,9,3,6,8}. Виконаємо сортування масиву методом Хоара.

Нижче представлений код програми.

import java.util.*;

public class sort {

// Метод простих вставок

public static void simpleSort(int[] data,int from, int to) {

int i, j;

for (i = from; i < to+1; i++) {

int c = data[i];

for (j = i-1; j >= from && data[j] > c; j--) {

data[j+1] = data[j];

}

data[j+1] = c;

}

}

// Метод швидкого сортування

public static void quickSort(int[] data) {

quickSort(data, 0, data.length-1);

}

private static void quickSort(int[] data, int from, int to) {

if (to-from < 50)

// Невеликі фрагменти швидше сортувати методом простих вставок

simpleSort(data, from, to);

else {

int c = data[from]; // Вибираємо деякий елемент

/ / Розподіляємо елементи масиву на значення менші і більші c.

int low = from, high = to+1;

//Inv: low <= high)&&data[from:(low-1)] <= c&&data[high:to] >= c

while (low < high) {

while (low < high && data[--high] >= c) ;

data[low] = data[high];

while (low < high && data[++low] <= c) ;

data[high] = data[low];

}

// Вставляємо елемент на своє місце.

data[low] = c;

/ / Незалежно сортуємо верхню і нижню половини масиву.

quickSort(data, from, low-1);

quickSort(data, low+1, to);

}

}

public static void main(String[]args){

int n=10;

int data[]={2,9,6,4,8,3,10,5,7,1};

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

System.out.print(data[i]+" ");

quickSort(data);

System.out.println();

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

System.out.print(data[i]+" ");

}

}

В результаті виконання лабораторної роботи студент повинен порівняти алгоритми сортування. Наприклад, за результатами експериментів з випадковим масивом обчислити кількість перестановок елементів (таб.2.1)

Таблиця 2.1 ̶ Кількість перестановок елементів (

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

1. У чому полягає задача сортування?

2. Визначте групи алгоритмів сортування.

3. Опишіть сутність алгоритмів групи елементарного сортування (вибору, вставки, бульбашки, Шелла).

4. Опишіть сутність групи алгоритмів порозрядного сортування, їх особливості, приклад.

5. У чому полягає ідея алгоритму сортування вставками?

6. У чому полягає ідея алгоритму сортування вибором?

7. У чому полягає ідея алгоритму сортування злиттям?

8. У чому полягає ідея алгоритму швидкого сортування?

9. У чому полягає ідея алгоритму пірамідальне сортування?