Searching and Sorting

Question 1

How linear search works? What is its complexity?

Answer 1

Линейното търсене обхожда елементите в масив един по един, докато не намери търсения елемент.
- Worse-Case - O(n)
- Best-Case - O(1)

Question 2

How binary search works? What is its complexity?

Answer 2

Двоичното търсене работи върху сортиран масив, като на всяка стъпка разделя масива на две и сравнява средния елемент с търсения. Използва техниката разделяй и владей
- Worse-Case - O(log⁡ n)
- Best-Case - O(1)

Question 3

What is divide and conquer? Give examples.

Answer 3

Това е техника за решаване на проблеми, като ги разделя на по-малки подпроблеми, решава ги поотделно и след това ги комбинира. Примери: Merge Sort, QuickSort.

Question 4

List 4 sorting algorithms and compare them.

Answer 4

• Bubble Sort: O(n^2), бавен, прост.
• Selection Sort: O(n^2), бавен, но прави по-малко замени.
• Merge Sort: O(n log n), стабилен, използва повече памет.
• Quick Sort: O(n^2), бърз, но нестабилен в най-лошия случай.

Question 5

How does merge sort works?

Answer 5

Разделя масива на две половини, сортира всяка от тях и ги слива в един сортиран масив. Това се повтаря рекурсивно. Изполва техниката “разделяй и владей.”

Question 6

How does QuickSort work?

Answer 6

Избира pivot, разделя масива на две части (по-малки и по-големи от него) и след това сортира всяка част рекурсивно. Използва техниката “разделяй и владей”.
Конкатенира в реда ляв масив - pivot - десен масив.