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

Информатика и программирование. Алгоритмы сортировки данных

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

Алгоритм сортировки выбором более эффективная сортировка обменами за критерием М(n), то есть за количеством пересылок, но также является не очень эффективным. Из этих причин были разработаны некоторые новые алгоритмы сортировки, которые получили название быстрых алгоритмов сортировки. Это такие алгоритмы, как сортировка деревом, пирамидальная сортировка, быстрая сортировка Хоора и метод цифровой сортировки.

Целью данной курсовой работы является реализация трех алгоритмов сортировки массива и выявления наиболее эффективного метода сортировки.

Задачи:

анализ научной и технической литературы;
реализация алгоритмов сортировки;
выявление наиболее эффективного алгоритма сортировки.

Используемый язык программирования – С++.

Используемая страда разработки - VisualStudio 2010.

ГЛАВА 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Алгоритмы сортировки

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

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

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

Время сортировки — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для сортировки важны худшее, среднее и лучшее поведения алгоритма в терминах размера списка (n). Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это Ω(n²). Идеальное поведение для сортировки — O(n). Алгоритмы сортировки, которые используют только абстрактную операцию сравнения ключей, всегда нуждаются, по меньшей мере, в Ω(n log n) сравнениях в среднем;
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. При оценке используемой памяти не будет учитываться место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Такое свойство может быть очень полезным, если они состоят из нескольких полей, а сортировка происходит по одному из них.
Естественность поведения — эффективность метода при обработке уже отсортированных, или частично отсортированных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов сортировки две:
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно сортируются на том же месте, без дополнительных затрат.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (сортировка файлов), т.е в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам сортировки, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим. Объём данных не позволяет им разместиться в ОЗУ.

Алгоритмы устойчивой сортировки:

Сортировка пузырьком (англ. Bubblesort ) — сложность алгоритма: Q(n²); для каждой пары индексов производится обмен, если элементы расположены не по порядку
Сортировка перемешиванием (Сортировка коктейлем, Cocktailsort, bidirectionalbubblesort) — Сложность алгоритма: O(n²)
Сортировка методом вставок (Insertionsort) — Сложность алгоритма: O(n²); определяем где текущий элемент должен находится в отсортированном списке и вставляем его туда
Блочная сортировка (Корзинная сортировка, Bucketsort) — Сложность алгоритма: O(n); требуется O(k) дополнительной памяти
Сортировка подсчетом (Countingsort) — Сложность алгоритма: O(n+k); требуется O(n+k) дополнительной памяти
Сортировка слиянием (Mergesort) — Сложность алгоритма: O(nlogn); требуется O(n) дополнительной памяти; сортируем первую и вторую половину списка отдельно, а затем — сливаем отсортированные списки
In-place merge sort — Сложностьалгоритма: O(n²)
Двоичное древо сортировки (Binarytreesort) — Сложность алгоритма: O(nlogn); требуется O(n) дополнительной памяти
Цифровая сортировка (Сортировка по отделениям, Pigeonholesort) — Сложность алгоритма: O(n+k); требуется O(k) дополнительной памяти
Поразрядная сортировка (Radixsort) — Сложность алгоритма: O(n·k)
Гномья сортировка (Gnomesort) — Сложность алгоритма: O(n²)

Алгоритмы неустойчивой сортировки

Сортировка методом выбора (Selectionsort) — Сложность алгоритма: O(n²); поиск наименьшего или наибольшего элемента и помещения его в начало или конец отсортированного списка
Сортировка методом Шелла (Shellsort) — Сложность алгоритма: O(nlogn); попытка улучшить сортировку вставками
Сортировка расчёской (Combsort) — Сложность алгоритма: O(nlogn)
Пирамидальная сортировка (Сортировка кучи, Heapsort) — Сложность алгоритма: O(nlogn); превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
Плавная сортировка (Smoothsort) — Сложность алгоритма: O(nlogn)
Быстрая сортировка (Quicksort) — Сложность алгоритма: O(nlogn) — среднее время, O(n²) — худший случай; широко известен как быстрейший из известных для сортировки больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине
Introsort — Сложность алгоритма: O(nlogn)
Patiencesorting — Сложность алгоритма: O(nlogn + k) — наихудший случай, требует дополнительно O(n + k) памяти, также находит самую длинную увеличивающуюся подпоследовательность

Непрактичные алгоритмы сортировки

Сортировка Акульшина (Akulshinsort) — O(n × n!) — худшее время. Генерируем всевозможные перестановки исходного массива и для каждой осуществдяем проверку верной отсортированности.
Глупая сортировка (Stupidsort) — O(n³); рекурсивная версия требует дополнительно O(n²) памяти
BeadSort — O(n) or O(√n), требуется специализированное железо
Блинная сортировка (Pancakesorting) — O(n), требуется специализированное железо

1.1.1 Сортировка пузырьком

Сортировка пузырьком (англ. bubblesort) — простой алгоритм сортировки. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, "всплывает" до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

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

1.1.2 Сортировка методом вставок

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

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

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

Сортировка вставками требует фиксированного числа проходов. На n-1 проходах вставляются элементы от A[1] до A[n-1]. На i-ом проходе вставки производятся в подсписок A[0]–A[i] и требуют в среднем i/2 сравнений. Общее число сравнений равно:

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

В отличие от других методов, сортировка вставками не использует обмены. Сложность алгоритма измеряется числом сравнений и равна O(n²). Наилучший случай – когда исходный список уже отсортирован. Тогда на i-ом проходе вставка производится в точке A[i], а общее число сравнений равно n-1, т.е. сложность составляет O(n). Наихудший случай возникает, когда список отсортирован по убыванию. Тогда каждая вставка происходит в точке A[0] и требует i сравнений. Общее число сравнений равно n(n-1)/2, т.е. сложность составляет O(n²).

В принципе, алгоритм сортировки вставками можно значительно ускорить. Для этого следует не сдвигать элементы по одному, как это продемонстрировано в приведенном выше примере, а находить нужный элемент с помощью бинарного поиска, описанного в предыдущем номере (то есть, в цикле разбивая список на две равные части, пока в списке не останется один-два элемента), а для сдвижки использовать функции копирования памяти. Такой подход дает довольно высокую производительность на небольших массивах. Основным узким местом в данном случае является само копирование памяти. Пока объем копируемых данных (около половины размера массива) соизмерим с размером кэша процессора 1 уровня, производительность этого метода довольно высока. Но из-за множественных непроизводительных повторов копирования, этот способ менее предпочтителен, чем метод «быстрой» сортировки. Этот же метод можно рекомендовать в случае относительно статичного массива, в который изредка производится вставка одного-двух элементов.

Сортировка вставками похожа на процесс тасования карточек с именами. Регистратор заносит каждое имя на карточку, а затем упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее место. Опишем этот процесс на примере нашего пятиэлементного списка A = 50, 20, 40, 75, 35 (см. рисунок 1.1).

Рисунок 1.1 Графическое представление сортировки

1.1.3 Сортировка методом выбора

Сортировка методом выбора (англ. selectionsort) — алгоритм сортировки, относящийся к неустойчивым алгоритмам сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n²), предполагая, что сравнения делаются за постоянное время.

Шаги алгоритма:

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

ГЛАВА 2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Исходные данные

Исходным массивом будет являться следующий массив целочисленных значений:

Реализация метода вывода значений массива на дисплей:

voidprintArray(int* arr, int size)

{

for(int i = 0; i < size; ++i) // i - номертекущегошага

{

std::cout<<arr[i] <<" ";

}

std::cout<<std::endl;

}

2.2 Реализация алгоритмов сортировки на языке C++

2.1.1 Сортировка пузырьком

Реализация алгоритма:

voidbubbleSort(int* arr, int size)

{

inttmp;

for(int i = 0; i < size - 1; ++i) // i - номерпрохода

{

for(int j = 0; j <size - 1; ++j) // внутренний цикл прохода

{

if (arr[j + 1] <arr[j])

{

tmp = arr[j + 1];

arr[j + 1] = arr[j];

arr[j] = tmp;

}

std::cout<<"Sortirovkapyzirkem"<<std::endl;

}

Результат работы:

2.1.2 Сортировка методом вставок

Реализация алгоритма:

voidinsertSort(int* a, int size)

{

inttmp;

for (int i = 1, j; i < size; ++i) // циклпроходов, i - номерпрохода

{

tmp = a[i];

for (j = i - 1; j >= 0 && a[j] >tmp; --j) // поиск места элемента в готовой последовательности

a[j + 1] = a[j]; // сдвигаем элемент направо, пока не дошли

a[j + 1] = tmp; // место найдено, вставить элемент

}

std::cout<<"Sortirovkavstavkami"<<std::endl;

}

Результат работы:

2.1.3 Сортировка методом выбора

Реализация алгоритма:

voidselectSort(int* arr, int size)

{

inttmp;

for(int i = 0; i < size; ++i) // i - номертекущегошага

{

intpos = i;

tmp = arr[i];

for(int j = i + 1; j <size; ++j) // цикл выбора наименьшего элемента

{

if (arr[j] <tmp)

{

pos = j;

tmp = arr[j];

}

arr[pos] = arr[i];

arr[i] = tmp; // меняемместаминаименьшийс a[i]

}

std::cout<<"Sortirovkaviborom"<<std::endl;

}

Результат работы:

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

Было проведено сравнение алгоритмов сортировки, испытав их на массивах, содержащих 4000, 8000, 10000, 15000 и 20000 целых чисел, соответственно. Время выполнения измерено в тиках (1/60 доля секунды). Среди всех алгоритмов порядка O(n²) время сортировки вставками отражает тот факт, что на i-ом проходе требуется лишь i/2 сравнений. Этот алгоритм явно превосходит все прочие сортировки порядка O(n²). Заметьте, что самую худшую общую производительность демонстрирует сортировка методом пузырька. Результаты испытаний показаны в таблице 2.1.

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

Таблица 2.1 – Сравнение алгоритмов

n	Сортировка выбором	Пузырьковая сортировка	Сортировка вставками
4 000	17.30	15.78	5.67
8 000	29.43	64.03	23.15
10 000	46.02	99.10	35.43
15 000	103.00	223.28	80.23
20 000	185.05	399.47	143.67

ЗАКЛЮЧЕНИЕ

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

среднее время выполнения алгоритма
наибольшее значение времени выполнения алгоритма
объем занимаемой оперативной памяти
скорость оперирования сортируемыми данными
специфичность области и среды применения алгоритма

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

Д. Кнут. Искусство программирования. М.: перевод на русский язык «Мир» 1978. 202 с.
С.Д. Кузнецов. Методы сортировки и поиска. М.: Наука 1987.
Стенли Б. Липман. Язык программирования С++. СПб.: «Невский диалект» 2003 перевод на русский язык А. Слинкин.

ПРИЛОЖЕНИЕ

Исходный код программы

// project.cpp : Defines the entry point for the console application.

#include"stdafx.h"

#include<iostream>

voidprintArray(int* arr, int size)

{

for(int i = 0; i < size; ++i) // i - номертекущегошага

{

std::cout<<arr[i] <<" ";

}

std::cout<<std::endl;

}

voidselectSort(int* arr, int size)

{

inttmp;

for(int i = 0; i < size; ++i) // i - номертекущегошага

{

intpos = i;

tmp = arr[i];

for(int j = i + 1; j <size; ++j) // цикл выбора наименьшего элемента

{

if (arr[j] <tmp)

{

pos = j;

tmp = arr[j];

}

arr[pos] = arr[i];

arr[i] = tmp; // меняемместаминаименьшийс a[i]

}

std::cout<<"Sortirovkaviborom"<<std::endl;

}

voidbubbleSort(int* arr, int size)

{

inttmp;

for(int i = 0; i < size - 1; ++i) // i - номерпрохода

{

for(int j = 0; j <size - 1; ++j) // внутренний цикл прохода

{

if (arr[j + 1] <arr[j])

{

tmp = arr[j + 1];

arr[j + 1] = arr[j];

arr[j] = tmp;

}

std::cout<<"Sortirovkapyzirkem"<<std::endl;

}

voidinsertSort(int* a, int size)

{

inttmp;

for (int i = 1, j; i < size; ++i) // циклпроходов, i - номерпрохода

{

tmp = a[i];

for (j = i - 1; j >= 0 && a[j] >tmp; --j) // поиск места элемента в готовой последовательности

a[j + 1] = a[j]; // сдвигаем элемент направо, пока не дошли

a[j + 1] = tmp; // место найдено, вставить элемент

}

std::cout<<"Sortirovkavstavkami"<<std::endl;

}

int _tmain(intargc, _TCHAR* argv[])

{

intarr[15] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 45, 56, -1, -5, 50, 100 };

int size = 15;

selectSort(arr, 15);

printArray(arr, 15);

bubbleSort(arr, 15);

printArray(arr, 15);

insertSort(arr, 15);

printArray(arr, 15);

system("PAUSE");

return 0;

}