Файл: Сортировка данных в массиве. Оценка эффективности метода.pdf

Количество обменов равно (N-1) N÷2.

Наилучший случай (улучшается):

Количество сравнений в теле цикла равно (N-1).

Количество сравнений в заголовках циклов (N-1).

Общее количество сравнений равно 2(N-1).

Количество обменов равно 0.

Время сортировки 10000 минемальных целых чисел в одной програмной операций, это среднее значение операции сравнения ≈3.4мкс, и обмена ≈2.3мкс, сортировкой выбором получится ≈40сек., ещё бысрее сортировка пузырьком ≈30сек, а быстрой сортировкой ≈0,027сек.

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

Пример кода алгоритма сортировки 2. Массив.

С

Пример кода алгоритма сортировки 3.Постороение програмы.

Пример работы алгоритма:

Пример массива с числами «6 2 5 3 9» и отсортируем элементы по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.

Первый проход:

(6 2 5 3 9) (2 6 5 3 9), Тут алгоритм сопоставляет оба первых элемента и меняет их местами.

(2 6 5 3 9) (2 5 6 3 9), Производим процедуру замены, потому что 5>4

(2 5 6 3 9) (2 5 3 6 9), Производим процедуру замены, потому что 6>3

(2 5 3 6 9) (2 5 3 6 9), Тут замены не происходит изза того что числа стоят на своих позициях (9>6), алгоритм не меняет их местами.

Второй проход:

(2 5 3 6 9) (2 5 3 6 9)

(2 5 3 6 9) (2 3 5 6 9), Меняет местами, потому что 5>3

(2 3 5 6 9) (2 3 5 6 9)

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

Третий проход:

(2 3 5 6 9) (2 3 5 6 9)

(2 3 5 6 9) (2 3 5 6 9)

Теперь массив отсортирован и алгоритм может быть завершён.

На Рис.1.Пример наглядной демонстрации алгоритма.

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

Глава 2. Проектная часть

---

2.1.Второй алгоритм «Сортировка выбором».

Алгоритм «Сортировка выбором» - этот алгоритм не выделяет дополнительной памяти.

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

1.Находит элемент наименьшено значения в данном списке

2.Заменяет этот элемент с элементом значения первой неотсортированной позиции , но замена не происходит, если этот элемент и так в начале списпа.

3.Сортируем конец списка, пропуская из анализа уже отсортированные элементы.

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

void SelectionSort (int k,int x[max]) {

int i,j,min,temp;

for (i=0;i<k-1;i++) {

min=i; //устанавливаем начальное значение наименьшего индекса

for (j=i+1;j<k;j++){ //находим наименьший индекс элемента

if (x[j]<x[min])

min=j; } //меняем значения местами

temp=x[i]; x[i]=x[min];

x[min]=temp; }

Пример неустойчивой реализации на C++ :

Пример неустойчивой реализации на Java:

Пример, почему данная вариация получается неустойчивой.

Представим массив из значений, каждый из них имеет два поля. Сортировка проходит по первому полю.

Массив до сортировки:

{ (2, a), (2, b), (1, a) }

После первой реализации цикла получим отсортированную последовательность:

{ (1, a), (2, b), (2, a) }

Оротим внимание, что элементы расположены взаимно (2, a) и (2, b) поменялось. Тем самым, рассмотренная реализация получелась неустойчивой.

Потому что после каждого оборота по внутреннему циклу происходит только одина замена, то общее число замен равно N-1, что в N/2 раз меньше, чем в сортировке пузырьком.

Количество проходов по внутреннему циклу равно N-1 даже в случае сортировки частично или полностью отсортированного массива.

Наихудший случай:

Количество сравнений в теле цикла равно (N-1)*N/2.

Количество сравнений в заголовках циклов (N-1)*N/2.

Количество сравнений перед операцией обмена N-1.

Суммарное количество сравнений N2−1.

Количество обменов N-1.

Наилучший случай:

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

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

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

---

Рис. 2. Демонстрация сортировки по неубыванию методом простого выбора.

Так и в пузырьковой сортировке, внешний цикл исполняется n-1 раз, а внутренний – в среднем n/2 раз. Отсюда, для сортировки методом простого выбора нужно

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

Рис.3. Демонстрация сортировки по неубыванию методом простого включения.

2.2.Третий алгоритм «Сортировка слиянием».

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

Пример решения задачи в эти три этапа:

1. Массив сортируемого элемента разделяется попалам на равные размеры;

2.Каждая из половинок массива сортируется по отдельности, то есть — тем же способом;

3.Обе отсортированые половинки массива обьединяются в один.

2.1. Рекурсивное деление пополам задачу повторяется, пока размер массива не дойдет до одного, каждый массив длиной 1 должен считать отсортированым.

3.1. Обьединение половинок отсортированых массивов в один.

Принцеп идеи слияния двух упорядоченых массивов можно показать на примере. Допустим у нас есть уже отсортированные половинки массива по неуменьшение подмассива. Получется:

3.2. Слияние половинок подмассива в один результирующий массив.

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

3.3. «Прицепление» остатка.

---

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

Разница между пузырьковой сортировкой и сортировкой простым выбором, число соостовлений в сортировкой вставки зависит от первоначального отсортироного списка. Если же список уже упорядочен, число сапостовлений получется n-1 ; иначе его скорость будет равна величине порядка n2.

Алгоритм придумал Джон фон Нейман в 1945 году.

В примере алгоритма на C++ языке выполняется проверка на равенство обоих сравниваемых содержимого подмассива с отличным блоком обработки если они равны. Дополнительная проверка на идентичность увеличевает число сравнений, это увеличивает количества кода программы. Что бы не усложнять программу дополнительными проверками в случаях равенства нужно применять две проверки if(L <= R) и if(L >= R), это в разы снижает колличество кода программы.

Пример быстрого алгоритма слияния без остатка на C++ :

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

Такой реализации нужно однократное разделание временни буфера памяти, соответсвующяя сортируемому массиву, и нет рекурсии. Шаги реализации:

InputArray = сортируемый массив, OutputArray = временный буфер

В каждом части входящего массива InputArray[N * MIN_CHUNK_SIZE..(N + 1) * MIN_CHUNK_SIZE] исполняется какой либо бополнительный алгоритм сортировки, пример: сортировка Шелла или быстрая сортировка.

вставляется ChunkSize = MIN_CHUNK_SIZE

обьяденяются обе половины: InputArray[N * ChunkSize..(N + 1) * ChunkSize] и InputArray[(N + 1) * ChunkSize..(N + 2) * ChunkSize] поочередно шагами слева и справа (см. выше), результат вставляется в OutputArray[N * ChunkSize..(N + 2) * ChunkSize], и так для всех N, до завершения массива.

ChunkSize удваивается

если ChunkSize получил >= размера массива, то ответ в OutputArray, который изза изменение в массиве получется отредактированный массив, или временный буфер,в другом случае масив полностью копируется в редактируемй массив.

В ином случае меняем местами InputArray и OutputArray перестановкой указателей, и повторям с пункта 4.

Этот способ так же позволяет размещять упорядочиваемого массива и временного буфера в секорах данныйх памяти, значит можно сортировать огромные объёмы данных. Реализация ORDER BY в СУБД MySQL если нет подходящего индекса утановлна таким оброзом источник: filesort.cc в исходном коде MySQL.

---

Устойчивость - сохраняется порядоке равных элементов находящиеся в одном классе эквивалентности по сравнению.

Псевдокод более быстрого алгоритма слияния без «прицепления» остатка на C++ языке:

Пример реализации алгоритма простого двухпутевого слияния на псевдокоде:

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

Способен работать на структурах данных последовательного доступа.

Хорошо сочетается с подкачкой и кэшированием памяти.

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

Не имеет «трудных» входных данных.

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

Пример сортировки на языке С:

Недостатки:

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

Требует дополнительной памяти по размеру исходного массива.

ЗАКЛЮЧЕНИЕ

В процессе курсовго исследования была достигнута цель работы - Оценка эффективности метода сортировки в массиве.

А так же решены следующие задачи:

1) Описана предметная область. Поставленны задачи;

2) Смоделированы методы сортировки данных в массиве алгоритмами: «Сортировка выбором»,

«Сортировка пузырьком»,

«Сортировка слиянием».

3)Проведены сравнения меодов сортировки.

4) Определена оценка эфективнось методов;

Моделирование алгоритмов сортировки в массиве позволяет проанализировать как работает метод в целом, но и как организована деятельность на каждом отдельно взятом месте массива.

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

Время — главный параметр, характеризующий быстродействие алгоритма. Используется так же вычислительная сложность. Для сортировки важные худшей, средней и лучшей поведения алгоритмов в терминах мощности входного множества A. Когда в начале алгоритма даётся множество A, то обозначаем n = |A|. Для обычного алгоритма нормальное решение — это O(n log n) а плохое решение — это O(n2). Отличным же будет сотрировка — O(n). Алгоритм сортировки, применяющий лишь абстрактную операцию сравнения ключей все время должен как минемум сравнивать их. Но при этом, есть алгоритмы сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n log log log n), применяющий факт, того что пространства ключей ограничены, это очень сложено, а за О-обозначением сокрыт большой коэффициент, изза чего его нельзя использовать повседневно практике. Так же есть понятие сортирующих сетей. Считающие, что можно одновременно пример, при параллельном вычислении, использовать несколько сравнений, можно редактировать n колличество за O(log2 n) операций. Но колличество n должно быть обозначено изначально;

---