Sorting and Searching

Изтегляне 1.67 Mb.

страница	1/2
Дата	23.09.2023
Размер	1.67 Mb.
	#118764

1 2

04.3.Други-алгоритми-за-сортиране
Свързани:
Albert-Camus - Chuzhdenetsyt - 14663

Разбъркване
Алгоритъм за разбъркване на Fisher–Yates
Сортиране чрез сливане
Сортиране чрез сливане: Как работи

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

Учителски екип
Обучение за ИТ кариера
https://it-kariera.mon.bg/e-learning/
Увод в алгоритмите

Съдържание

Разбъркване
Сортиране чрез сливане
Бързо сортиране
Сортиране чрез броене
Bucket сортиране
Сравнение на алгоритмите

Разбъркване

Разбъркване (shuffling) == постигане на случаен ред на елементите в колекция

Пораждане на случайни пермутации

Генерирането на случайни числа е прекалено важно, за да бъде оставено на шанса. —Robert R. Coveyou

Алгоритъм за разбъркване на Fisher–Yates

public static void Shuffle(T[] source)
{
Random rnd = new Random();

for (int i = 0; i < source.Length; i++)
{
// Exchange array[i] with random element in array[i … n-1]
int r = i + rnd.Next(0, source.Length - i);
T temp = source[i];
source[i] = source[r];
source[r] = temp;
}
}
Shuffle algorithms: visualization

Сортиране чрез сливане

Сортиране чрез сливане (merge sort) е ефективен алгоритъм за сортиране (онагледяване)

Разделя списъка на подсписъци (обикновено 2 подсписъка)
Сортира всеки подсписък (рекурсивно извиквайки merge-sort)
Слива сортираните подсписъци в един списък

Най-добър, обичаен и най-лош случай: O(n*log(n))
Памет:

Обикновено O(n)
Със сливане на място стига до O(1)

Приложим за паралелно изпълнение на множество ядра / машини  до O(log(n))

Стабилен: Да
Метод: Сливане

Сортиране чрез сливане: Как работи?

Бързо сортиране

Бързо сортиране (QuickSort) – ефективен алгоритъм за сортиране (онагледяване)

Избира се „опорен“ елемент; премества по-малките елементи вляво от него, а по-големите - вдясно; сортира лявата и дясната част
Най-добър и обичаен случай: O(n*log(n)); Най-лош: O(n2)
Памет: O(log(n)) място в стека (за рекурсия)
Стабилен: Зависи
Метод: Разделяне

Изтегляне 1.67 Mb.

Сподели с приятели:

1 2