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

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

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

Выполнила:

Студентка гр. 2101

Баланина Ю.В.

Проверил:

Тюрин И.С.

_________________________

Введение

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

Описание алгоритма

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

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

Листинг программы

mycode = '''

import timeit

import random

a=[]

n=10

for i in range(n):

    a.append(random.randint(0,9))

count=[0]*10

for i in a:

    count[i]+=1

for i in range(10):

    if count[i]>0:

        print((str(i)+" ")*count[i],end="")

'''

print(timeit.timeit(stmt = mycode, number = 1))

Тестирование

В данной работе использован диапазон значений [0;9].

1. Тестирование алгоритма сортировки без учета времени, количество элементов массива n=10:

[pic 1]

Вывод: алгоритм работает

1. Тестирование алгоритма с учетом времени, n=10:

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

[pic 2]

График результатов:

[pic 3]

Согласно полученным результатам, приближенное максимальное количество элементов при заданном максимальном времени выполнения (39 секунд) ––– n=2 750 000.

Заключение

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