Common sorting algorithms

• Algorithms are a sequence of well-defined instructions to solve a specific problem

Sorting Algorithms

• Sorting algorithms arrange elements of a list in a specific order (numerical or lexicographical)

Bubble Sort

• Bubble Sort repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order
• Inefficient for large datasets, due to its quadratic time complexity
• Best-case time complexity: O(n)
• Worst/Average-case time complexity: O(n^2)
• Space complexity: O(1)

Insertion Sort

• Insertion Sort builds the final sorted array one item at a time
• Efficient for small datasets or nearly sorted data
• Best-case time complexity: O(n)
• Worst/Average-case time complexity: O(n^2)
• Space complexity: O(1)

Selection Sort

• Selection Sort divides the input list into two parts: a sorted sublist and the remaining unsorted sublist
• The smallest element from the unsorted sublist is selected and moved to the sorted sublist
• Simple to implement, but inefficient for large datasets
• Time complexity: O(n^2) in all cases
• Space complexity: O(1)

Merge Sort

• Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges them
• Well suited for large datasets
• Time complexity: O(n log n) in all cases
• Space complexity: O(n)

Quick Sort

• Quick Sort is a divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the pivot
• Efficient in practice, but performance depends on pivot selection
• Best/Average-case time complexity: O(n log n)
• Worst-case time complexity: O(n^2)
• Space complexity: O(log n)

Heap Sort

• Heap Sort uses a binary heap data structure to sort the array
• Time complexity: O(n log n) in all cases
• Space complexity: O(1)

Search Algorithms

• Search algorithms find a specific element in a dataset or determine its absence

Linear Search

• Linear Search sequentially checks each element of the list until a match is found or the entire list has been searched
• Simple to implement
• Inefficient for large datasets
• Time complexity: O(n)
• Space complexity: O(1)

Binary Search

• Binary Search repeatedly divides the search interval in half
• Requires the input array to be sorted
• Efficient for large, sorted datasets
• Time complexity: O(log n)
• Space complexity: O(1) (iterative) / O(log n) (recursive)

Depth-First Search (DFS)

• DFS explores as far as possible along each branch before backtracking
• Uses a stack (or recursion) to keep track of visited nodes
• Useful for traversing or searching tree/graph structures
• Time complexity: O(V + E), where V is the number of vertices and E is the number of edges
• Space complexity: O(V)

Breadth-First Search (BFS)

• BFS explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level
• Uses a queue to keep track of visited nodes
• Useful for finding the shortest path in an unweighted graph
• Time complexity: O(V + E), where V is the number of vertices and E is the number of edges
• Space complexity: O(V)

Algorithm Analysis

• Algorithm analysis is performed to determine the amount of resources (such as time and storage) required to execute them
• Time complexity represents the amount of time taken by an algorithm to run as a function of the length of the input
• Space complexity represents the amount of memory space taken by an algorithm to run as a function of the length of the input

Big O Notation

• Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity
• Used to classify algorithms according to how their running time or space requirements grow as the input size grows
• Common examples: O(1) - Constant, O(log n) - Logarithmic, O(n) - Linear, O(n log n) - Linearithmic, O(n^2) - Quadratic, O(2^n) - Exponential, O(n!) - Factorial