boykopetevboev/softuni-algorithms-fundamentals-november-2020

RECURSION / SEARCHING / SORTING / GRAPH THEORY

Sorting Algorithms

Name	Best	Average	Worst	Memory	Stable	Method
Selection Sort	n2	n2	n2	1	No	Selection
Bubble Sort	n	n2	n2	1	Yes	Exchanging
Insertion Sort	n	n2	n2	1	Yes	Insertion
Merge Sort	n*log(n)	n*log(n)	n*log(n)	1 (or n)	Yes	Merging
Quick Sort	n*log(n)	n*log(n)	n2	log(n)	Depends	Partitioning

Selection Sort

Simple, but inefficient algorithm. Swap the first with the min element on the right, then the second, etc.

• Memory: O(1)
• Stable: No
• Method: Selection

Bubble Sort

Simple, but inefficient algorithm. Swaps to neighbor elements when not in order until sorted.

• Memory: O(1)
• Stable: Yes
• Method: Exchanging

Insertion Sort

Simple, but inefficient algorithm. Move the first unsorted element left to its place.

• Memory: O(1)
• Stable: Yes
• Method: Insertion

Merge Sort

Efficient sorting algorithm.

1. Divide the list into sub-lists (typically 2 sub-lists)
2. Sort each sub-list (recursively call merge-sort)
3. Merge the sorted sub-lists into a single list

Best, average and worst case: O(n*log(n))

• Memory: O(n) / O(1)
• Stable: Yes
• Method: Merging

Quick Sort

Efficient sorting algorithm.

1. Choose a pivot
2. Move smaller elements left & larger right
3. sort left & right

Best & average case: O(n*log(n)); Worst: O(n2)

• Memory: O(log(n))
• Stable: Depends
• Method: Partitioning