Algorithm Review 1

1. Binary Search

💡Key Idea
The left and right variables are used to define the boundaries of the search space, and are updated iteratively based on the results of comparisons between the target value and the values in the search space.

⏱️Time Complexity
The time complexity of binary search is O(log n), where n is the size of the sorted array being searched. This means that the time taken by binary search to find a target element in a sorted array increases logarithmically with the size of the array.
Specifically, in each iteration of the algorithm, the size of the search space is divided in half, so the worst-case time complexity of binary search is proportional to the logarithm of the number of elements in the array. This makes binary search an efficient algorithm for searching large sorted arrays.

int BinarySearch(int* arr, int left, int right, int x) {
	
    // Enter loop if the search space is not empty
	while (left <= right) {
		int middle = (left + right) / 2; // Calculate the middle index of the search space
		if (x == arr[middle]) // If the middle element is the target, return its index
			return middle;
		// If the target is less than the middle element, narrow the search space to the left half
		else if (x < arr[middle]) {
			right = middle - 1;
		}
		// If the target is greater than the middle element, narrow the search space to the right half
		else {
			left = middle + 1;
		}
	}
	// If the target is not found, return -1
	return -1;
}

2. Bubble Sort

💡Key Idea
During the bubbling up process, the largest value gradually moves towards the rear (end) of the array.

⏱️Time Complexity
The time complexity of bubble sort is O(n^2), where "n" is the number of elements in the array being sorted. This is because the algorithm involves iterating over the entire array multiple times, and for each element, it compares it to all the other elements in the array.
As the number of elements in the array increases, the number of comparisons and swaps also increase quadratically, making bubble sort inefficient for larger arrays.

// Sort an array of integers in ascending order using the bubble sort algorithm
void bubbleSort(int* arr, int n) {
	// Loop over the array n-1 times
	for (int i = n - 1; i >= 0; i--) {
		// Loop over the unsorted portion of the array
		for (int j = 0; j < i; j++) {
			// If adjacent elements are out of order, swap them
			if (arr[j] > arr[j + 1]) {
				int temp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = temp;
			}
		}
	}
	// The array is now sorted in place
}

3. Insertion Sort

💡Key Idea
In the Insertion Sort algorithm, each element of the array is compared with the elements to its left, starting from the rightmost position. As the comparison is made, the current element is moved one position to the right until the correct position for the element is found. Once the correct position is identified, the current element is inserted into that position. This process is repeated for all elements in the array, resulting in a sorted array at the end.

⏱️Time Complexity
The time complexity of Insertion Sort is O(n^2) in the worst-case scenario. This is because for each element in the array, the algorithm needs to compare it with the elements to its left and potentially swap its position until it is in the correct sorted order. As the size of the array grows, the number of comparisons and swaps required also increases quadratically.

However, in practice, Insertion Sort can perform better than some other sorting algorithms for small arrays or partially sorted arrays because it has a small constant factor and is an adaptive algorithm. When the array is almost sorted, the number of comparisons and swaps required can be significantly reduced, resulting in a faster sorting time.

void InsertionSort(int* arr, int n) {
	// Iterate over each element in the array
	for (int i = 1; i < n; i++) {
		// Store the current element in a temporary variable
		int tmp = arr[i];
		
		// Compare the current element with the elements to its left
		// and move them one position to the right until the correct
		// position for the current element is found
		int j = i - 1;
		while (j >= 0 && arr[j] > tmp) {
			arr[j + 1] = arr[j];
			j--;
		}
		
		// Insert the current element into its correct position in the sorted array
		arr[j + 1] = tmp;
	}
}