Создать базу данных фильмографии актера Кристиана Бейла, произвести анализ информации и её сортировку

             Министерство образования и науки  РФ

Федеральное государственное бюджетное образовательное учреждение

                    высшего профессионального образования

           «Тульский государственный университет»

 

                          Политехнический институт

    Факультет транспортных и технологических систем

Кафедра  «Технология полиграфического производства и

                                        защиты информации»

 

 

 

 

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

по дисциплине «Информатика»

 

на тему:

 

«Создать базу данных фильмографии актера Кристиана Бейла, произвести анализ информации и её сортировку»

 

 

 

 

 

 

 

 

 

 

 

Выполнил студент гр. 622211

Дергачев В.Н.

 

Проверил доцент

Пальчун Е.Н.

 

 

 

 

 

 

 

 

Тула  2012

 

Содержание

 

1.	Теоретическая часть……………………………………………………2
2.	Проектная часть………………………………………………………12
3.	Вывод…………………………………………………………………17
4.	Библиографический список………………………………………….18
	Приложения………………………………………………………….19

 

 

Введение

 

На протяжении последних 10 лет идет планомерное вытеснение карточной системы в библиотеках, архивах на поисковые системы общего доступа, реализованные на основе ЭВМ.  При этом в последние годы такие системы выходят за рамки учреждения в общий доступ средствами Интернет технологий.

В данной работе не идет речь о создании подобной системы, а рассматривается вопрос, связанный с дальнейшей обработкой информации, после выполнения поискового запроса, а именно – сортировка данных. При всей, на первый взгляд простоте процесса, это всё еще не до конца отработанная процедура.

Решение данного вопроса является важным этапом в эволюции технологии обработки информации.

 

Теоретическая часть

 

Достаточно часто пользователям  Интернет ресурсов приходится сталкиваться с большим объемом информации, представленным в виде таблиц, списков и других видов представления информации, после неких действий. Не менее часто требуется получить результаты в ином порядке, чем они представлены первоначально. Большинство программистов решает эту проблему применением сортировки на сервере, для чего используется перезагрузка страницы. Действительно, серверные языки предоставляют гораздо больше возможностей отсортировать многомерный массив по определенному значению, чем пользовательские языки, выполняющиеся непосредственно на стороне клиента.

Решение сортировать данные на стороне сервера вполне оправданно и с точки зрения трудозатрат программиста, так как многие из них имеют встроенные функции сортировки многомерных массивов, и поэтому не требуется вдумываться в алгоритмы сортировки, что-то изобретать или перестраивать алгоритм под свои нужды. Но все-таки такое решение не оправдано, если подходить к этой проблеме с точки зрения удобства использования пользователями.

Вначале посетителю сайта требуется  дождаться достаточно длительной загрузки страницы, просмотреть результаты, нажать на кнопку "Отсортировать" и опять дожидаться, пока сервер закончит работу и вернет результат. Такие множественные перезагрузки страницы никак не способствуют популярности сайта у посетителя. В конце-концов, устав дожидаться очередной загрузки страницы, или испугавшись лишнего траффика, он покинет сайт в поисках более лояльного к нему ресурса.

В общем понимании сортировка - это упорядочивание элементов по возрастанию или убыванию. Сортировка очень важная операция во всех сферах программирования.

Во всех обменных сортировках сравниваются два элемента отстоящие друг от друга  на расстоянии d. При этом два элемента сравниваются и элемент с большим весом перемещается вправо, а с меньшим влево.

Существует большое количество способов сортировки, разработаны математические приемы обработки данных. Условно эти методы можно разделить на две категории: универсальные и методы, позволяющие обработать конкретные типы данных.

К последним, можно отнести обработку  числовых данных на предмет выявления  ложных (нулевых или сильно заниженных, завышенных) значений. Это бывает очень важно при решении технических задач, например, никто не может утверждать, что в полученных во время эксперимента данных нет результатов, которые могут привести к потере работоспособности программного продукта в дальнейших расчетах. В этом случае статистическая сортировка позволяет решить данную проблему.

Однако данный метод не применим к текстовым или тем более  смешанному типу данных.

Для решения проблемы сортировки смешанных или текстовых типов данных существуют так называемые универсальные методы. В числе наиболее часто применяемых решений выделяют три основных, речь о которых пойдет ниже. Именно эти методы и необходимо реализовывать в нашем случае, так как данные, хранимые в библиотечных каталогах, далеко не всегда являются однородными по типу (могут содержать год, число страниц и другую числовую составляющую, и при этом иметь название, автора и другую текстовую информацию).

Среди наиболее востребованных и проверенных методов выделяют три основных.

 

 

Стандартный обмен

 

Метод стандартного обмена еще называется "Методом Пузырька". В этом методе d=1, т.е. сравниваются рядом стоящие элементы. При первом проходе алгоритм последовательно сравнивает по два элемента и меняет их местами в зависимости от условия сортировки. При этом на последнем месте оказывается самый максимальный (минимальный) элемент. На втором шаге алгоритм сравнивает первые N-1 элементов в ставит предпоследним самый большой. При каждом последующем шаге интервал уменьшается на единицу.

Давайте рассмотрим пример:

Дано множество 

{8,3,4,2,5}

 

1. {3,8,4,2,5} - сравниваются 8 и 3, переставляются т.к. 8>3

2. {3,4,8,2,5} - сравниваем 8 и 4, также переставляем.

3. {3,4,2,8,5}

4. {3,4,2,5,8}

 

В результате этого первого шага элемент весом в 8, переместился в конец. Далее он не рассматривается и операция сортировки производится с множеством {3,4,2,5}.

В результате всех шагов у нас  образуется отсортированное по возрастанию  множество {2,3,4,5,8}.

Программная реализация этого алгоритма на языке СИ представлена ниже.

 

#include <stdio.h>

#include <stdlib.h>

 

 

int BubbleSort(int *array,int len)

{

int i,j,c;

int k=0;

for (i=len;i>1;i--)

{

k=0;

for (j=1;j<i;j++)

if (array[j]<array[j-1])

{

c=array[j];

array[j]=array[j-1];

array[j-1]=c;

k=1;

};

if (k==0) return 0;

};

};

 

 

Условия Айверсона

 

На каком-то этапе, может даже на начальном, массив окажется полностью отсортированным, и для того, чтобы зря не тратить время на сортировку существует условие Айверсона.

Условие: Сортировку можно прекратить досрочно, если на каком-то этапе в ходе сравнения не будет сделано ни одной перестановки.

За это условие в процедуре BubbleSort() отвечает переменная k, и условие if (k==0) return 0;.

 

 

Метод Шекла

 

Сортировка по методу Шелла также относится к обменным сортировкам, и даже принцип функционирования очень похож на "метод пузырька".

В этом методе первоначально рассматриваются  элементы, отстоящие друг от друга на расстояние d=[n/2], где [ ] - операция взятия целой части, и n - количество элементов исходного массива.

На следующих шагах d меняется по закону d=[d/2], при d=1 метод Шелла вырождается в метод стандартного обмена ("Метод Пузырка").

Для объяснения данного приема, рассмотрим пример:

Дано множество:

{6,3,4,8,2,9}

 

d=[n/2]=[6/2]=3

 

{6,3,4,8,2,9} - сравниваем 6 и 8

{6,2,4,8,3,9} - сравниваем 3 и 2, переставляем

{6,3,4,8,2,9} - сравниваем 4 и 9

 

далее d=[d/2]=[3/2]=1

выродился в метод "Пузырька"

 

В этом примере не очень видна  эффективность этого метода, но представьте, что вы сортируете 1000 элементов. Этот метод обеспечивает более быстрое перебрасывание больших элементов вправо и меньших влево, чем метод "Пузырька" и этим обеспечивает большее быстродействие.

 

Программная реализация на СИ может  быть записана следующим образом:

 

int BubbleSort(int *array,int len)

{

/* Код сортировки из  предыдущего шага */

};

 

int ShellSort(int *array,int len)

{

long d=len,i,j;

int c;

do

{

d=d/2;

i=0;

while ((j=i+d)<len)

{

if (array[i]>array[j])

{

c=array[i];

array[i]=array[j];

array[j]=c;

};

i++;

};

}

while (d>1);

BubbleSort(array,len);

};

 

Результат выполнения:

8  -5  1  7  3  -10  6  5  10  9

-10  -5  1  3  5  6  7  8  9  10

 

Для теста эффективности обычно создают счетчик циклов, и на конкретном примере до вырождения в метод "Пузырька" было выполнено всего 3 прохода. Причем, массив был получен в следующем виде:

 

-10  -5  1  3  5  6  7  8  9  10

 

Из него видно, что он уже отсортирован и метод "Пузырька" работал в холостую, но совершил всего один цикл, т.к. в нем выполнилось условие Айверсона.

Очевидно, что метод Шелла обладает большим быстродействием.

При обходе оригинального массива  процедура может создавать вспомогательный, или же напрямую работать с оригинальным массивом, при этом она удаляет ненужные элементы. Для того чтобы хранить список данных надо всегда помнить ссылку на один из его компонентов. Обычно хранят ссылку на первый компонент, так как это самый рациональный выбор.

Вся проблема заключается в том, что "ходящая" процедура не в курсе какой элемент она удаляет, и ей все равно будь он первый, средний или последний. И возникает вопрос, что же будет, если она нечаянно удалит первый элемент, адрес которого Вы храните неизвестно в каком количестве переменных. Получается, что весь список пропадет разом.

Так вот как уберечься от удаления первого элемента? Идея, как всегда крайне проста. Обработчик списка надо написать таким образом, чтобы он анализировал положение удаляемого элемента списка, т.е. если удаляемый элемент находится в середине списка, то он удаляется обычным образом, а вот если он был первым, то не удаляет себя, а удаляет следующий по списку элемент, при этом полностью скопировав его содержимое.

Все просто, надо чтобы элемент  как бы удалялся, но при этом второй строго занимал бы его прежнее место. Таким образом, помня адрес первого элемента, Вы можете с ним делать, что хотите, так как Вы его никогда не потеряете.

 

Сортировка Хоара

 

Сортировка Хоара это третий метод относящийся к обменным сортировкам. Этот метод признан одним из лучших методов сортировки, которые когда-либо изобрели. Он даже носит название "Быстрой сортировки".

В методе Хоара первоначально выделяют базовый элемент, относительно которого ключи с большим весом перебрасываются  вправо, а с меньшим влево. Базовый  элемент сравнивается с противоположным элементом.

В качестве базового элемента очень  удобно брать крайние элементы.

Для наглядного представления, рассмотрим следующий пример:

Дано множество:

 

{9,6,3,4,10,8,2,7}

 

Берем 9 в качестве базового элемента. Сравниваем 9 с противоположностоящим элементом, в данном случае это 7. 7 меньше, чем 9, следовательно элементы меняются местами.

 

{7,6,3,4,10,8,2,9}

 

Далее последовательно сравнивают элементы с 9, и меняют их местами в зависимости от сравнения.

 

{7,6,3,4,10,8,2,9}

{7,6,3,4,10,8,2,9}

{7,6,3,4,10,8,2,9}

{7,6,3,4,9,8,2,10} - 9 и 10 меняем местами.

{7,6,3,4,8,9,2,10} - 9 и 8 меняем местами.

{7,6,3,4,8,2,9,10} - 2 и 9 меняем местами.

 

После такого перебрасывания элементов  весь массив разбивается на два подмножетсва, разделенных элементом 9.

 

{7,6,3,4,8,2}

{10}

 

Далее по уже отработанному алгоритму  сортируются эти подмножества.

Подмножество из одного элемента естественно  можно не сортировать. Выбираем в  первом подмножестве базовый элемент 7.

 

{7,6,3,4,8,2}

 

{2,6,3,4,8,7} - меняем местами 2 и 7.

{2,6,3,4,8,7}

{2,6,3,4,8,7}

{2,6,3,4,8,7}

{2,6,3,4,7,8}- меняем местами 7 и 8

 

 

Получили снова два подмножества.

 

{2,6,3,4}

{8}

 

Скорость работы алгоритма зависит  прежде всего от его реализации, поэтому самое главное найти  эту правильную реализацию. Единственный путь к ускорению всегда лежит через уменьшение количества сравнений на каждой итерации.

 

 

Проектная часть

 

В нашем задании существует условие, что данные сортируются в среде  Интернет. Поэтому задачу необходимо решать, основываясь именно на этом сегменте языков программирования.

В сфере web-программирования, существуют уже готовые решения по сортировке на стороне клиента. В большинстве случаев они основаны на сортировке методом Хоара. Условно их можно разделить на 2 вида: сортировку таблиц, на основе анализа их содержания, и сортировку массивов, а после формирования таблицы, для удобного вывода информации.

К первому способу относятся  способы сортировки на основе библиотек  jquery. В них уже заложены проверенные методы сортировки, в частности Хоара.

Ко второму – отдельные программы (скрипты), способные обрабатывать информацию, взятую из массивов или баз данных.

У обоих методов есть свои плюсы  и минусы, в частности у первого  способа, уже должны быть готовые  таблицы, оформленные синтаксисом HTML. Конечно, их можно получать методами обхода массивов, однако это потребует большей трудоемкости при написании программы. У второго же способа серьезным недостатком является неотработанность и возможность наличия ошибок в алгоритме, а также сложности при оформлении результатов, так как почти всегда используется способ динамического создания таблиц с применением объектного программирования. Это сложная система получения таблицы результатов, при этом не всегда удобно рассматривать подобный код с точки зрения нахождения ошибки при формировании сложных табличных структур (объединение ячеек, установка размеров, как всей таблицы так и её ячеек, обводки и т.д.).