CSCS Visual Lab
Модул: Алгоритми

Търсене и сортиране с визуален псевдокод

Сравнете линейното и двоичното търсене, след което експериментирайте с пет алгоритъма за сортиране. Проследете всяка операция, наблюдавайте псевдокода и анализирайте сложността.

Търсене в масив

Линейното търсене проверява последователно всеки елемент, докато намери търсената стойност. Сравнете го с двоичното търсене използва стратегия „разделяй и владей“ върху сортиран масив за бързо намиране на стойност..

ЛинейноO(n/2)
ДвоичноO(log n)

Манипулация на масив и търсене

Сравнете линейното и двоичното търсене. Въведете стойности, изберете алгоритъм и проследете стъпките.

#02
#14
#27
#311
#415
#520

Последна стъпка: —

Псевдокод

  1. #compare

    обход за i от 0 до n

  2. #found

    връщане на индекса при съвпадение

  3. #not-found

    върни -1 при липса

Линейно търсене

Разбиране на линейното обхождане • Оценка на сложността O(n) • Сравнение с двоично търсене

  • Алгоритъм стъпка по стъпка: Методът е прост: започваме от първия елемент и сравняваме, докато намерим съвпадение или стигнем края.
  • Сложност: В най-добрия случай стойността е на първа позиция (O(1)), а в най-лошия – отсъства (O(n)).

Двоично търсене

Разделяне на диапазона наполовина • Обработка на среден индекс • Сравнение с линейно търсене

  • Изисквания: Нужен е сортиран масив и достъп по индекс. При несортирани данни алгоритъмът не работи коректно.
  • Сложност: При всяка итерация размерът се дели на две, което води до сложност O(log n).

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

Сравнение на основните алгоритми за сортиране: балонно, избор, вмъкване, сливане и бързо сортиране.

Средна сложностO(n log n)
Най-лош случайO(n^2)
ПаметO(n)

Сортиране: Балонно сортиране

Повтарящ се алгоритъм, който сравнява съседни елементи и ги разменя при нужда, докато масивът се подреди.

Брой елементи
12
4
9
2
7
5

Стъпка: Очаква старт

Сложност (средна): O(n^2) | Най-лош случай: O(n^2)

Псевдокод

  1. #compare

    сравни съседни елементи

  2. #swap

    ако са в грешен ред → размени

  3. #update-min

    обнови индекса на минималния елемент

  4. #shift

    премести елемент надясно за освобождаване

  5. #insert

    вмъкни ключовия елемент

  6. #split

    раздели масива на две части

  7. #merge

    сливане на подмасиви

  8. #select-pivot

    избери пивот

  9. #partition

    раздели елементи около пивота

  10. #place-pivot

    постави пивота на място

  11. #end

    резултат: подреден масив

Балонно сортиране

Проследяване на итерациите.

Повтарящи се сравнения и размени на съседни елементи. Лесно за разбиране, но бавно при големи масиви.

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

Разбиране на избора на минимум.

Намира се минималният елемент и се поставя в началото, след което процесът продължава за останалите.

Сортиране чрез вмъкване

Наблюдение на сравнението за вмъкване.

Изгражда се сортирана част чрез вмъкване на всеки следващ елемент на правилното място.

Сливане

Проследяване на рекурсивните извиквания.

Рекурсивно разделяне на масива и сливане на подредени подмасиви. Сложност O(n log n).

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

Разбиране на избор на пивот и подразделяне.

Избира се пивот, разделя се масивът на по-малки и по-големи елементи и се сортират рекурсивно.

Quick Sort (TypeScript)

Quick Sort (C#)

Кратък куиз

Тествайте знанията си по темата. Отговорете на всички въпроси и натиснете „Провери“.

Въпрос 1: Какво връща линейното търсене при ненамерен елемент?

Въпрос 2: Как калкулираме сложността?

Кратък куиз

Тествайте знанията си по темата. Отговорете на всички въпроси и натиснете „Провери“.

Въпрос 1: Кой алгоритъм е стабилен по подразбиране?

Въпрос 2: Кой алгоритъм има най-добра средна сложност?

Въпрос 3: Какво е предимство на quick sort?

Предстоящи теми

TODO: Добавяне на визуализации за BFS и DFS върху графи.