Sorting and Searching

Сортиране чрез броене

• Сортиране чрез броене (counting sort) е много ефективен алгоритъм за сортиране (онагледяване)
• Сортира малки числа чрез броене на техните срещания
• Не е базиран на сравнение
• Най-добър, обичаен и най-лош случай: O(n + k)
• k е диапазонът на сортираните числа
• Например [-1000 ... 1000]  k = 2001
• Памет: O(n + k) Място: O(k)
• Стабилен: Да
• Метод: Броене

Bucket сортиране

• Bucket sort разделя масива на много „ведра“
• Всяко „ведро“ се сортира с различен алгоритъм
• Не е сортиране, базирано на сравнение
• Обичайните случаи: O(n + k)
• k = броя на „ведрата“
• Най-лошия случай: O(n * log n)
• Стабилен: Да (зависи от алгоритъма)
• Памет: O(n) – k „ведра“ съдържащи общо n елемента

Сравнение на сортиращи алгоритми

Обобщение

• Бавни алгоритми за сортиране:
• Чрез пряка селекция, метод на мехурчето, сортиране чрез вмъкване
• Бързи алгоритми за сортиране:
• Бързо сортиране, сортиране чрез сливане и т.н.
• Как да изберем най-удачния метод за сортиране?
• http://stackoverflow.com/a/1934004

Други алгоритми за сортиране

https://it-kariera.mon.bg/e-learning/

Министерство на образованието и науката (МОН)

• Настоящият курс (презентации, примери, задачи, упражнения и др.) е разработен за нуждите на Национална програма "Обучение за ИТ кариера" на МОН за подготовка по професия "Приложен програмист"
• Курсът е базиран на учебно съдържание и методика, предоставени от фондация "Софтуерен университет" и се разпространява под свободен лиценз CC-BY-NC-SA