Реферат: Сравнение эффективности алгоритмов сортировки - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Сравнение эффективности алгоритмов сортировки

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 20 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы



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

Владивостокский государственный университет экономики и сервиса















«Сравнение эффективности алгоритмов сортировки»


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

по дисциплине

«Алгоритмизация и программирование»









Выполнил:

студент гр. ИТ-0401

Иванова Т.А.


Проверил:

доцент. каф. ИСКТ

к.т.н. Гриняк В.М.



















Владивосток 2006

ВВЕДЕНИЕ


Целью курсовой работы является закрепление основ и углубление знаний приемов программирования на алгорит­мических языках высокого уровня, получение практических на­выков в создании программного продукта, отработка приёмов проведения вычислительных экспериментов на ЭВМ.

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



ПОСТАНОВКА ЗАДАЧИ


Сравнить эффективность алгоритмов сортировки – пузырьковой и сортировки вставками.


ОПИСАНИЕ РЕШЕНИЯ ЗАДАЧИ



СОРТИРОВКА ВСТАВКАМИ


Сортировка вставками элементов a1, a2, …, an относится к наиболее очевидным методам. При таком подходе вводится фиктивный элемент a0=-, а затем каждый элемент, начиная со второго, сравнивается с элементами уже упорядоченной части последовательности и вставляется в нужное место. При вставке элемент aj временно размещается в переменной w, и просматриваются элементы aj-1, aj-2, …,a1 (уже к этому времени упорядоченные). Они сравниваются с w и сдвигаются, если обнаруживается, что они больше чем w.

//----------------------------------------------

for (j=2; j

{

w=a[j]; i=j-1;

while(w

a[i+1]=w;

};

//----------------------------------------------

Сложность алгоритма определяется числом проверок условия w


ПУЗЫРЬКОВАЯ СОРТИРОВКА


Метод пузырьковой сортировки последовательности a1, a2, …, an представляет собой систематический обмен местами слева направо смежных элементов, не отвечающих выбранному порядку, до тех пор, пока они не оказываются на правильном месте. Большие элементы при этом как бы «всплывают пузырьками вверх» в конец списка. В приведённом ниже алгоритме используется переменная b, значение которой содержит число ещё не отсортированных элементов

//---------------------------------------

b=n;

while (b!=0)

{

t=0;

for(j=1;j

{

if (a[j]>a[j+1]) {w=a[j]; a[j]=a[j+1]; a[j+1]=w; t=j;};

}

b=t;

}

//--------------------------------------------

Сложность данного алгоритма определяется числом проверок условия a[j]>a[j+1] в цикле и является квадратичной O(n2). Число реально проделанных сравнений существенно зависит от первоначального расположения элементов массива.

Рассмотренный ниже другой алгоритм так называемой «полной» пузырьковой сортировки является наиболее популярным и легко программируемым её вариантом.

//-----------------------------------

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

{

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

{

if (a[j]>a[j+1]) {w=a[j];a[j]=a[j+1];a[j+1]=w;};

}
}

//-------------------------------------

Сложность приведённого алгоритма определяется числом сравнений a[j]>a[j+1]. Она остаётся постоянно равной n(n-1)/2 (то есть квадратичной) и не зависит от расположения исходных данных.



ЗАКЛЮЧЕНИЕ


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







СПИСОК ЛИТЕРАТУРЫ


  1. Лекции по курсу «Алгоритмизация и программирование. Структуры и алгоритмы компьютерной обработки данных».

  2. Б.Н. Иванов Дискретная математика. Алгоритмы и программы: Учеб. пособие. – Владивосток: Изд-во ДВГТУ, 2000.


1Авиация и космонавтика
2Архитектура и строительство
3Астрономия
 
4Безопасность жизнедеятельности
5Биология
 
6Военная кафедра, гражданская оборона
 
7География, экономическая география
8Геология и геодезия
9Государственное регулирование и налоги
 
10Естествознание
 
11Журналистика
 
12Законодательство и право
13Адвокатура
14Административное право
15Арбитражное процессуальное право
16Банковское право
17Государство и право
18Гражданское право и процесс
19Жилищное право
20Законодательство зарубежных стран
21Земельное право
22Конституционное право
23Конституционное право зарубежных стран
24Международное право
25Муниципальное право
26Налоговое право
27Римское право
28Семейное право
29Таможенное право
30Трудовое право
31Уголовное право и процесс
32Финансовое право
33Хозяйственное право
34Экологическое право
35Юриспруденция
36Иностранные языки
37Информатика, информационные технологии
38Базы данных
39Компьютерные сети
40Программирование
41Искусство и культура
42Краеведение
43Культурология
44Музыка
45История
46Биографии
47Историческая личность
 
48Литература
 
49Маркетинг и реклама
50Математика
51Медицина и здоровье
52Менеджмент
53Антикризисное управление
54Делопроизводство и документооборот
55Логистика
 
56Педагогика
57Политология
58Правоохранительные органы
59Криминалистика и криминология
60Прочее
61Психология
62Юридическая психология
 
63Радиоэлектроника
64Религия
 
65Сельское хозяйство и землепользование
66Социология
67Страхование
 
68Технологии
69Материаловедение
70Машиностроение
71Металлургия
72Транспорт
73Туризм
 
74Физика
75Физкультура и спорт
76Философия
 
77Химия
 
78Экология, охрана природы
79Экономика и финансы
80Анализ хозяйственной деятельности
81Банковское дело и кредитование
82Биржевое дело
83Бухгалтерский учет и аудит
84История экономических учений
85Международные отношения
86Предпринимательство, бизнес, микроэкономика
87Финансы
88Ценные бумаги и фондовый рынок
89Экономика предприятия
90Экономико-математическое моделирование
91Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Гардеробщица решила покончить с собой, но не смогла из-за отсутствия петельки.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Сравнение эффективности алгоритмов сортировки", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru