Проект на тему "Алгоритмы сортировки"

МУНИЦИПАЛЬНОЕ БЮДЖЕТНОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ - СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА №11 ГОРОДА ИСКИТИМА НОВОСИБИРСКОЙ ОБЛАСТИ

Итоговый индивидуальный проект

«Методы сортировки массивов»

Выполнил: Перминова Екатерина

Ученица 11 «Б» класса

МБОУ-СОШ №11

Руководитель проекта: учитель информатики
Черепанова Елена Анатольевна

г. Искитим 2022 г.

Оглавление

Введение. 3

Методы сортировки. 4

Bubble Sort (пузырьковая сортировка) 4

Selection Sort (сортировка выбором) 4

Quicksort (быстрая сортировка) 5

Оценка сложности. 5

Сложность Bubble Sort 6

Сложность Selection Sort 6

Сложность Quicksort 7

Вывод.. 7

Введение

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

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

Цель

Определение сложности алгоритмов разных методов сортировки и понимание работы этих алгоритмов.

Задачи

                                      1) Изучить популярные методы сортировки

                                      2) Узнать, что такое сложность алгоритмов

                                      3) Сравнить алгоритмы по сложности

Методы сортировки

BubbleSort (пузырьковая сортировка)

Этот вид сортировки изучают в начале знакомства с дисциплиной ComputerScience, поскольку он максимально просто демонстрирует саму концепцию сортировки.

Из-за большого количества повторений у пузырьковой сортировки его сложность в худшем случае — O(n^2).

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

a = [-3, 5, 8, 0, -8, 1, 10]

N = len(a)

for j in range(N-1):

fori in range(N-1-j):

if a[i]>a[i+1]:

a[i], a[i+1] = a[i+1], a[i]

print(a)

SelectionSort (сортировка выбором)

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

a = [-3, 5, 8, 0, -8, 1, 10]

N = len(a)

fori in range(N-1):

   m = a[i]

   p = i

for j in range(i+1, N):

if m > a[j]:

           m = a[j]

           p = j

if p != i:

       t = a[i]

a[i] = a[p]

a[p] = t

print(a)

Quicksort (быстрая сортировка)

Быстрая сортировка относится к алгоритмам «разделяй и властвуй».

Алгоритм состоит из трех шагов:

1.            Выбрать элемент из массива. Назовём его опорным.

2.            Разбиение: перераспределение элементов в массиве таким образом, что элементы, меньшие опорного, помещаются перед ним, а большие или равные - после.

3.            Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.

def partition(array, begin, end):

pivot = begin

fori in range(begin+1, end+1):

if array[i] <= array[begin]:

pivot += 1

array[i], array[pivot] = array[pivot], array[i]

array[pivot], array[begin] = array[begin], array[pivot]

return pivot

defquick_sort(array, begin=0, end=None):

if end is None:

end = len(array) - 1

def _quicksort(array, begin, end):

if begin >= end:

return

pivot = partition(array, begin, end)

       _quicksort(array, begin, pivot - 1)

       _quicksort(array, pivot + 1, end)

return _quicksort(array, begin, end)

array = [29,19,47,11,6,19,24,12,17,23,11,71,41,36,71,13,18,32,26]

quick_sort(array)

print(array)

Оценка сложности

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

1. Количество операций – временная эффективность (timeefficiency), показывает скорость работы алгоритма.

2. Объем потребляемой памяти – пространственная эффективность (spaceefficiency), отражает максимальное количество памяти, требуемой для выполнения алгоритма.

Эти характеристики и включают в себя понятие сложности алгоритма.

Сложность алгоритма – это количество действий в вычислительном процессе этого алгоритма

Сложность BubbleSort

Сложность этого алгоритма равна O(N^2), т.е., является квадратичной. Он представляет собой два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива.

Сложность SelectionSort

Для сортировки выбором есть несколько вариантов кода, самыми популярными из которых являются:

1)                  Алгоритм со сложностью O(N^2) - каждый раз проходит по всем еще не отсортированным элементам, и, как только находит элемент меньше, чем первый из отсортированных, меняет их местами

2)                  Алгоритм со сложностью O(N) - сначала проходит по всем еще не отсортированным элементам в поисках минимального, а уже потом меняет местами минимальный и первый из неотсортированных

Сложность Quicksort

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

Вывод

После изучения работы трех алгоритмов сортировки и выявления их сложности, мы можем сделать вывод, что имеем сложность O(N^2) у алгоритмов BubbleSort и SelectionSort. Такой же сложностью будет обладать алгоритм Quicksort в худшем случае, однако в лучшем случае его сложность будет составлять O(NlogN).