Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных»




Скачать 133.98 Kb.
НазваниеКурсовая работа по дисциплине «Структуры и алгоритмы обработки данных»
Дата конвертации21.12.2012
Размер133.98 Kb.
ТипКурсовая



КАЗАНСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ НАНОМАТЕРИАЛО И НАНОТЕХНОЛОГИЙ

Кафедра интеллектуальных систем и управления информационными ресурсами


КУРСОВАЯ РАБОТА

по дисциплине «Структуры и алгоритмы обработки данных»

тема: «Алгоритм быстрой сортировки»


Выполнила студентка

Гр.4301-21

Гатауллина А.К.


Казань 2012

Введение.

Сортировка – один из наиболее распространенных процессов современной обработки данных. Задачи на сортировку данных встречаются на компьютере очень часто. Главным образом, это связано с тем, что разбираться в отсортированных данных намного проще, чем в неотсортированных.

        Алгоритм сортировки — это порядок действий для упорядочения элементов в списке. Обычно говорят о сортировке записей (содержащих любые данные) по ключам – фрагментам этих записей, допускающих отношение упорядочения. Например, ключи могут быть числами (в этом случае используется естественный математический порядок возрастания или убывания чисел) или строковыми значениями (в этом случае упорядочение производится по алфавиту).

Наверно, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший алгоритм? Возможно, нет. Однако, имея приблизительные характеристики исходных данных, можно подобрать метод, работающий оптимальным образом.

Оценка алгоритма сортировки.

Для того чтобы обоснованно сделать выбор метода сортировки, рассмотрим параметры, по которым будет производиться оценка алгоритмов.


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

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

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

• Естественность поведения — эффективность метода при обработке уже

отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:

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

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


Быстрая сортировка.

Основа алгоритма была разработана в 1960 году Хором (C.A.R.Hoare) и с тех пор внимательно изучалась многими людьми. Быстрая сортировка особенно популярна ввиду легкости ее реализации; это довольно хороший алгоритм общего назначения, который хорошо работает во многих ситуациях, и использует при этом меньше ресурсов, чем другие алгоритмы.

Описание быстрой сортировки

Быстрая сортировка(quicksort), как и сортировка слиянием, основана на принципе «разделяй и властвуй». Сортировка участка А[p..r] происходит так:

- Элементы массива А переставляются так, чтобы любой из элементов A[p],…,A[q] был не больше любого из элементов A[q+1],…,A[r], где q- некоторое число в интервале

Эту операцию мы будем называть разделением (partition).

-Процедура сортировки рекурсивно вызывается для массивов

A[p..q] и A[q+1..r].

После этого массив A[p..r] отсортирован.

Процедура сортировки QUICKSORT выглядит следующим образом:

QUICKSORT (A,p,r)

1 if p

2 then q PARTITION (A,p,r)

3 QUICKSORT (A,p,q)

4 QUICKSORT (A,p+1,r)


Разбиение массива

Основной шаг алгоритма – процедура PARTITION, которая переставляет элементы массива A[p..r] нужным образом:

1 int partition (vector &A, int p, int r) {


2 int x = A[p];


3 int i = p;


4 for(int j = p + 1; j < r; j++) {


5 if (A[j] <= x)


6 swap(A[++i], A[j]);


7 }


8 swap(A[p], A[i ]);


9 return i;


10 }

Процедура быстрой сортировки.

1 void quicksort(vector &A, int p, int r) {


2 if (r �� p > 1) {


3 int q = partition(A, p, r );


4 quicksort(A, p, q);


5 quicksort(A, q+1, r);


6 }

7 }


Работа быстрой сортировки

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

Наихудшее разбиение

«Наиболее неравные части» получатся, если одна часть содержит n-1 элемент, а вторая- всего 1.Предположим, что на каждом шаге происходит именно так. Поскольку процедура разбиения занимает время Q(n), для времени работы T(n) получаем соотношение T(n)= T(n-1)+ Q(n)

Поскольку T(1)=Q(1), имеем

T(n)= T(n-1)+ Q(n)=)

Видим, что при максимально несбалансированном разбиении время работы составляет , если массив изначально отсортирован.

Θ(n)


n
Θ(1) θ(n-1)


Θ(n)
Θ(1) θ(n-2)

Θ(1) …

Θ(1)



Наилучшее разбиение

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

T(n)=2T(n/2)+Q(n)

и по теореме T(n)=Q(nlgn)

Промежуточный случай

Среднее время работы( с точностью до множителя) совпадает с временем работы в наилучшем случае, чтобы объяснить это, посмотрим как меняется рекуррентное соотношение в зависимости от степени сбалансированности разбиения.

Пусть, например, на каждом шаге массив разбивается на 2 части с соотношением размеров 9:1.Тогда

T(n)=T(9n/10)+T(n/10)+n

(Для удобства заменили Q(n) на n)

Размер стека

Так же как и в главе 3, для выполнения быстрой сортировки можно воспользоваться стеком магазинного типа,рассматривая его как стек, в котором в виде сортируемых подфайлов содержится перечень работ, которые предстоит выполнить. Каждый раз когда возникает необходимость в обработке подфайла, он выталкивается из стека. После разделения файла получаются два подфайла, требующих дальнейшей обработки, которые и заталкиваются в стек. В рекурсивной реализации, представленной программой 7.1, стек, который поддерживается системой, содержит именно эту информацию. Что касается файлов с произвольной организацией, то максимальный раздел стека пропорционален значению log N (см. раздел ссылок), однако в условиях вырожденного случая стек может расширяться до размеров, пропорциональных N, как показано на рис. 7.5. В самом деле, наиболее трудный случай имеет место тогда, когда файл уже отсортирован. Потенциальная возможность увеличения размеров стека до пропорциональных размерам сортируемого файла в условиях рекурсивной реализации быстрой сортировки представляет собой не очевидную, но в то же время вполне реальную проблему: в условиях этого метода сортировки всегда используется стек, а в вырожденном случае при работе с файлом большого размера подобное обстоятельство может послужить причиной аварийной остановки программы ввиду нехватки памяти. Такое поведение совершенно недопустимо для библиотечной программы сортировки. (По всей вероятности, мы скорее столкнемся с проблемой недопустимо длительной сортировки, нежели с проблемой нехватки памяти.) Трудно гарантировано исключить подобное поведение программы, но нетрудно предусмотреть специальные средства, которые делают вероятность возникновения таких вырожденных случаев исключительно мало.

РИСУНОК 7.5. РАЗМЕР СТЕКА ДЛЯ БЫСТРОЙ СОРТИРОВКИ.

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



Достоинства и недостатки

Достоинства:

  • Один из самых быстродействующих (на практике) из алгоритмов внутренней сортировки общего назначения.

  • Прост в реализации.(За первые 3 года после публикации математического алгоритма он так и не был реализован на ЭВМ ни разу).

  • Требует лишь O(logn) дополнительной памяти для своей работы.

  • Хорошо сочетается с механизмами кэширования и виртуальной памяти.

  • Существует эффективная модификация (алгоритм Седжвика) для сортировки строк — сначала сравнение с опорным элементом только по нулевому символу строки, далее применение аналогичной сортировки для «большего» и «меньшего» массивов тоже по нулевому символу, и для «равного» массива по уже первому символу.

Недостатки:

  • Сильно деградирует по скорости (до Θ(n2)) при неудачных выборах опорных элементов, что может случиться при неудачных входных данных. Этого можно избежать, используя такие модификации алгоритма, как Introsort, или вероятностно, выбирая опорный элемент случайно, а не фиксированным образом.

  • Наивная реализация алгоритма может привести к ошибке переполнения стека, так как ей может потребоваться сделать O(n) вложенных рекурсивных вызовов. В улучшенных реализациях, в которых рекурсивный вызов происходит только для сортировки бо́льшей из двух частей массива, глубина рекурсии гарантированно не превысит O(logn).

  • Неустойчив — если требуется устойчивость, приходится расширять ключ.



Улучшение.

Улучшить алгоритм быстрой сортировки является большим искушением: более быстрый алгоритм сортировки - это своеобразная "мышеловка" для программистов. Почти с того момента, как Хор впервые опубликовал свой алгоритм, в литературе стали появляться "улучшенные" версии этого алгоритма. Было опробовано и проанализировано множество идей, но все равно очень просто обмануться, поскольку алгоритм настолько хорошо сбалансирован, что результатом улучшения в одной его части может стать более сильное ухудшение в другой его части. Мы изучим в некоторых деталях три модификации этого алгоритма, которые дают ему существенное улучшение.

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

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

Вычислительная сложность «быстрой» сортировки

Общий анализ эффективности «быстрой» сортировки достаточно труден. Будет лучше показать ее вычислительную сложность, подсчитав число сравнений при некоторых идеальных допущениях. Допустим, что n – степень двойки, n = 2k (k = log2n), а центральный элемент располагается точно посередине каждого списка и разбивает его на два подсписка примерно одинаковой длины.

При первом сканировании производится n-1 сравнений. В результате создаются два подсписка размером n/2. На следующей фазе обработка каждого подсписка требует примерно n/2 сравнений. Общее число сравнений на этой фазе равно 2(n/2) = n. На следующей фазе обрабатываются четыре подсписка, что требует 4(n/4) сравнений, и т.д. В конце концов процесс разбиения прекращается после k проходов, когда получившиеся подсписки содержат по одному элементу. Общее число сравнений приблизительно равно

n + 2(n/2) + 4(n/4) + ... + n(n/n) = n + n + ... + n = n * k = n * log2n

Для списка общего вида вычислительная сложность «быстрой» сортировки равна O(n log2 n). Идеальный случай, который мы только что рассмотрели, фактически возникает тогда, когда массив уже отсортирован по возрастанию. Тогда центральный элемент попадает точно в середину каждого подсписка.

Если массив отсортирован по убыванию, то на первом проходе центральный элемент обнаруживается на середине списка и меняется местами с каждым элементом как в первом, так и во втором подсписке. Результирующий список почти отсортирован, алгоритм имеет сложность порядка O(n log2n).

сортировка данных в массиве 

Наихудшим сценарием для «быстрой» сортировки будет тот, при котором центральный элемент все время попадает в одноэлементный подсписок, а все прочие элементы остаются во втором подсписке. Это происходит тогда, когда центральным всегда является наименьший элемент. Рассмотрим последовательность 3, 8, 1, 5, 9.

На первом проходе производится n сравнений, а больший подсписок содержит n-1 элементов. На следующем проходе этот подсписок требует n-1 сравнений и дает подсписок из n-2 элементов и т.д. Общее число сравнений равно:

n + n-1 + n-2 + ... + 2 = n(n+1)/2 - 1

Сложность худшего случая равна O(n2), т.е. не лучше, чем для сортировок вставками и выбором. Однако этот случай является патологическим и маловероятен на практике.

Алгоритм QuickSort выбирается за основу в большинстве универсальных сортирующих утилит. Если вы не можете смириться с производительностью наихудшего случая, используйте пирамидальную сортировку – более устойчивый алгоритм, сложность которого равна O(n log2n) и зависит только от размера списка.


Вывод


При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки — O(n log n).

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

С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла — примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит log2n, а в худшем случае она вообще будет не более 2 — вся обработка пройдёт в цикле первого уровня рекурсии.


Оглавление

Введение

1. Описание

2. Работа быстрой сортировки

2.1 Наихудшее разбиение

2.2 Наилучшее разбиение

2.3 Промежуточный случай

3. Улучшение

4. Достоинства и недостатки

5. Вывод

6. Реализация алгоритма на Си

Список использованной литературы


Список использованной литературы


    1. Т. Кормен, Ч. Лейзер - Алгоритмы. Построение и анализ




    1. Роберт Седжвик Фундаментальные алгоритмы на С++



Реализация алгоритма на Си.

#include

#include

#include

#include

#include


using namespace std;


template

void QSort(T array[], int first, int last){

if(first < last){

int i;

int j;

T temp;

T point;

point = array[first];

i = first;

j = last;

while(i < j){

while(array[i] <= point && i < last)

i++;

while(array[j] >= point && j > first)

j--;

if(i < j){

temp = array[i];

array[i] = array[j];

array[j] = temp;

}

}

temp = array[first];

array[first] = array[j];

array[j] = temp;

QSort(array, first, j - 1);

QSort(array, j + 1, last);

}

}


template

void PrintArray(T array[], int size){

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

if(i % 5 == 0)

cout << endl;

cout << setw(15) << array[i];

}

cout << endl;

}


int main(){

system("chcp 1251");

srand(time(0));

const int N =10000;

int i;

int a[N];

for(i = 0; i < N; i++){

a[i] = rand()% 10000;

}


cout << "Array A: ";

PrintArray(a, N);

QSort(a, 0, N - 1);

cout << endl;

cout << "Array A:\n";

PrintArray(a, N);

return 0;

}

Добавить в свой блог или на сайт

Похожие:

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconУчебное пособие по курсу «Структуры и алгоритмы обработки данных»
Рассмотрены структуры и алгоритмы, которые являются основой современной методологии разработки программ. Изложено детальное описание...

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconТест по дисциплине "Структуры и алгоритмы обработки данных" Задания закрытого типа
Структура данных работа с элементами которой организована по принципу fifo (первый пришел первый ушел) это

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconКурсовая работа на тему: Распределенные системы обработки данных в корпоративных информационных системах
Технология клиент-сервер 23 Глава 3 Аппаратное и программное обеспечение распределенной обработки данных 33 1 Интегрированные информационные...

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconКурсовая работа По дисциплине «Базы данных»
Программное обеспечение для создания систем управления базами данных

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» icon3. Исследование параметрических и непараметрических методов определения коэффициента корреляции данных
Алгоритмы статистической обработки данных межлабораторных сличений, проводимых с целью проверки квалификации поверочных и калибровочных...

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconПрограмма дисциплины сд. 03 “Программирование и структуры данных
Основной целью преподавания дисциплины является обучение студентов методам разработки программ, языкам программирова­ния, средствам...

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconМодели, методы и алгоритмы обработки и анализа разнородных данных пространственно-распределенных объектов в геоинформационных системах
Работа выполнена на кафедре «Информационные системы» Муромского института (филиала) государственного образовательного учреждения...

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconБюллетень новых поступлений за декабрь 2011 г
С++; Методы защитного программирования; Структуры данных и алгоритмы; Сжатие и криптообработка данных; Программирование в операционной...

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconПрактическая работа «Алгоритмы и методы архивации»
Цель: Изучить основные алгоритмы и методы архивации данных; закрепить навыки по созданию презентаций и работе с литературой

Курсовая работа по дисциплине «Структуры и алгоритмы обработки данных» iconКурсовая работа по дисциплине: «Маркетинг»
Маркетинговая концепция формирования оптимальной структуры управления предприятием


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница