Задание. на тему "Обработка последовательности информации"

Курсовая работа

на тему "Обработка последовательности информации"

Вариант 1.1

 

Выполнил:

студент гр. ИС-441

Трофименко П.М.

 

Новосибирск, 2014

 

Задание

Реализовать динамическую библиотеку сортировок. Алгоритмы сортировок выбираются в соответсвии с вариантом задания. Проанализировать эффективность алгоритмов сортировки. Разработать демонстрационную программу, использующую созданную билиотеку.

Алгоритм Bubble Sort

Алгоритм Bubble Sort...Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n^2).

Исходныйт код BubbleSort:

void bubble_sort (int *a, int n) {

int i, t, s = 1;

while (s) {

s = 0;

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

if (a[i] < a[i - 1]) {

t = a[i] = a[i - 1];

a[i - 1] = t;

s = 1;

}

}

}

}

Алгоритм Quick Sort

Quicksort - один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(nlogn) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Исходный код алгоритма:

void quick_sort (int *a, int n) {

int i, j, p, t;

if (n < 2)

return;

p = a[n / 2];

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

while (a[i] < p)

i++;

while (p < a[j])

j--;

if (i >= j)

break;

t = a[i];

a[i] = a[j];

a[j] = t;

}

quick_sort(a, i);

quick_sort(a + i, n - i);

}

 

 

Ход работы

 

Для создания динамической библиотеки, в первую очередь, необходимо создать файлы, в которых будут содержаться функции, которые войдут в нашу библиотеку. Я создал 2 файла quick.c и bubble.c. После этого необходимо скомпилировать их с ключом –fPIC. Команда будет выглядеть так:

gcc -fPIC –c quick.c

В результате мы получим файлы quick.o и bubble.o.

Для создания динамической библиотеки используется ключ –shared:

gcc –shared –o libsort.so quick.o bubble.o

Эта команда скомпилировала нашу библиотеку.

Следующим шагом будет компиляция программы с подключением нашей новой библиотеки. Для начала необходимо скомпилировать файл, содержащий main:

gcc –c bubble_sort.c

На выходе получаем файл bubble_sort.o. Следующим шагом будет компиляция результирующей программы с подключением библиотеки:

gcc bubble_sort.o –L. libsort.so –o bubbleprog

В итоге мы получили файл, который будет получать функцию сортировки из динамической библиотеки. Но есть одно «но». При запуске мы получили ошибку. Проблема в том, что динамический линковщик не может найти нашу библиотеку, так как у него нет данных о её местоположении. Эта проблема решается созданием специальной переменной среды LD_LIBRARY_PATH, в которой перечисляются все каталоги, содержащие пользовательские динамические библиотеки. Устанавливается она следующим образом:

LD_LIBRARY_PATH=/root^${LD_LIBRARY_PATH}

export LD_LIBRARY_PATH

После проделанных манипуляций наша программа запустилась и отработала без ошибок.