Algorithms: Searching and Sorting Cheatsheet | Codecademy (2024)

Merge Sort is a divide and conquer algorithm. It consists of two parts:

1) splitting the original list into smaller sorted lists recursively until there is only 1 element in the list,2) merging back the presorted 1-element lists into 2-element lists, 4-element lists, and so on recursively.

The merging portion is iterative and takes 2 sublists. The first element of the left sublist is compared to the first element of the right sublist. If it is smaller, it is added to a new sorted list, and removed from the left sublist. If it is bigger, the first element of the right sublist is added instead to the sorted list and then removed from the right sublist.This is repeated until either the left or right sublist is empty. The remaining non-empty sublist is appended to the sorted list.

function binSearchIterative(target, array, left, right) {
 while(left < right) {
 let mid = (right + left) / 2;
 if (target < array[mid]) {
 right = mid;
 } else if (target > array[mid]) {
 left = mid;
 } else {
 return mid;
 }
 }
 return -1;
}

In a recursive binary search, there are two cases for which that is no longer recursive. One case is when the middle is equal to the target. The other case is when the search value is absent in the list.

binary_search(sorted_list, left_pointer, right_pointer, target) if (left_pointer >= right_pointer) base case 1 mid_val and mid_idx defined here if (mid_val == target) base case 2 if (mid_val > target) recursive call with left pointer if (mid_val < target) recursive call with right pointer

In a recursive binary search, if the value has not been found then the recursion must continue on the list by updating the left and right pointers after comparing the target value to the middle value.

If the target is less than the middle value, you know the target has to be somewhere on the left, so, the right pointer must be updated with the middle index. The left pointer will remain the same. Otherwise, the left pointer must be updated with the middle index while the right pointer remains the same. The given code block is a part of a function binarySearchRecursive().

function binarySearchRecursive(array, first, last, target) {
 let middle = (first + last) / 2;
 // Base case implementation will be in here.
 if (target < array[middle]) {
 return binarySearchRecursive(array, first, middle, target); 
 } else {
 return binarySearchRecursive(array, middle, last, target);
 }
}

The binary search starts the process by comparing the middle element of a sorted dataset with the target value for a match. If the middle element is equal to the target value, then the algorithm is complete. Otherwise, the half in which the target cannot logically exist is eliminated and the search continues on the remaining half in the same manner.

The decision of discarding one half is achievable since the dataset is sorted.

The binary search algorithm takes time to complete, indicated by its time complexity. The worst-case time complexity is O(log N). This means that as the number of values in a dataset increases, the performance time of the algorithm (the number of comparisons) increases as a function of the base-2 logarithm of the number of values.

Example: Binary searching a list of 64 elements takes at MOST log2(64) = 6 comparisons to complete.

class InsertionSort {
 public static void sort(int[] array) {
 for (int i = 1; i < array.length; i++) {
 int current = array[i];
 int j = i -1;
 while (j >= 0 && array[j] > current) {
 array[j + 1] = array[j];
 j--;
 }
 array[j+1] = current;
 }
 }
 public static void main(String[] args) {
 }
}

class InsertionSort {
 public static void sort(int[] array) {
 // outer loop iterates through input array starting with second element
 for (int i = 1; i < array.length; i++) {
 // store value of current element
 // inner loop
 while (j >= 0 && array[j] > current) {
 // compare current element to predecessor(s)
 }
 // move the greater element(s) one position to make space for swapped element
 }
 }
}

int[] ascendingNumbers = {2, 4, 6, 8};
insertionSort(ascendingNumbers);
// sort second element - 4 is greater than 2 - no shift or further comparisons
// sort third element - 6 is greater than 4 - no shift or further comparisons
// sort fourth element - 8 is greater than 6 - no shift or further comparisons

class InsertionSort {
 public static void sort(int[] array) {
 for (int i = 1; i < array.length; i++) {
 // nested loop structure indicates O(n^2)
 while (j >= 0 && array[j] > current) {
 // compare current element to predecessor
 }
 // code to swap
 }
 }
}

int[] descendingNumbers = {8, 6, 4, 2};
insertionSort(descendingNumbers);
// result of first sort - {6, 8, 4, 2}
// result of second sort - {4, 6, 8, 2}
// comparisons to sort last element - 2 is less than 8, 2 is less than 6, 2 is less than 4, insert 2

class Main {
 public static void selectionSort (int arr[]) {
 int size = arr.length;
 for (int i = 0; i < size - 1; i++) {
 int currentMinimumIndex = i;
 for (int j = i + 1; j < arr.length; j++) {
 if (arr[j] < arr[currentMinimumIndex]) {
 currentMinimumIndex = j;
 }
 }
 int temp = arr[currentMinimumIndex];
 arr[currentMinimumIndex] = arr[i];
 arr[i] = temp;
 }
}
 public static void main(String args[]) {
 }
}

public static void selectionSort (int arr[]) {
 //for loop to loop through all unsorted elements
 for (int i = 0; i < size - 1; i++) {
 // for loop to find the smallest value of unsorted elements 
 for (int j = i + 1; j < arr.length; j++) {
 // Code that keeps track of the smallest value
 }
 // Code that swaps the smallest value to the correct place 
 }
 }

 public static void selectionSort (int arr[]) {
 // nested for loop indicates runtime of O(n^2)
 for (int i = 0; i < size - 1; i++) {
 for (int j = i + 1; j < arr.length; j++) {
 }
 }
 }
See Also
SHA256 vs Scrypt: How Comparing Hash Rates is Misleading | NKMAG

The number of comparison statements made by selection sort is less than n^2. This is because the inner for loop that searches for the smallest remaining value in the unsorted section of the list does not have to search through all n items. It only needs to search through the remaining unsorted values.

Nevertheless, the runtime remains O(n^2).

class Main {
 public static void selectionSort (int arr[]) {
 // outer for loop makes n - 1 comparisons
 for (int i = 0; i < size - 1; i++) {
 // inner for loop only searches remaining unsorted values
 for (int j = i + 1; j < arr.length; j++) {
 // code that keeps track of the smallest value
 }
 // code that swaps elements
 }
}
 public static void main(String args[]) {
 }
}

// worst case scenario
int[] inputArray1 = { 19, 15, 12, 7 };
selectionSort(inputArray1);
// determine 1st index 
 // compare 19 to 15, then 15 to 12, then 12 to 7
 // 7 is the lowest value, swap with 19
 // 3 comparisons were made 
// best case scenario 
int[] inputArray2 = { 7, 12, 15, 19 };
selectionSort(inputArray2);
// determine 1st index
 // compare 7 to 12, then 7 to 15, then 7 to 19
 // 7 is the lowest, no swap
 // 3 comparisons were made

public static void selectionSort (int arr[]) {
 // for loop to loop through all unsorted elements
 for (int i = 0; i < size - 1; i++) {
 // for loop to find the smallest value of unsorted elements 
 for (int j = i + 1; j < arr.length; j++) {
 // Code that keeps track of the smallest value
 }
 // Code that swaps the smallest value to the correct place 
 int temp = arr[currentMinimumIndex];
 arr[currentMinimumIndex] = arr[i];
 arr[i] = temp;
 }
}

Linear search will start with the first element and check if it is a match for our target element, and will continue the search till it finds a match. The steps are:
Step 1: Examine the current element in the list.
Step 2: If the current element is equal to the target value, stop.
Step 3: If the current element is not equal to the target value, check the next element in the list.
Continue steps 1 - 3 until the element is found or the end of the list is reached.

for each element in the search_list if element equal target value then print location and return indexif element is not found then print message not found and return -1

class LinearSearch
{
 public static int linearSearch(int[] arr, int target)
 {
 // loop through the input array
 // check if array at current index is equal to `target`
 // if true
 System.out.println("Element is present at index " + i);
 return i;
 // if we finish looping through our array and the element is not found 
 System.out.println("Element is not present in the array");
 return -1;
 }
 public static void main(String args[])
 {
 int arr[] = { 2, 3, 4, 10, 40 };
 int target = 10;
 linearSearch(arr, target);
 }
}

The best-case performance for the Linear Search algorithm is when the search item appears at the beginning of the list and is O(1). The worst-case performance is when the search item appears at the end of the list or not at all. This would require N comparisons, hence, the worse case is O(N).

In Java, a linear search on a 2D array is usually accomplished with nested for loops.

for each row in the search_list for each column of that row if element at that row and column equals the target value then print the index of the row and column and return 1 print message that element is not found and return -1

class BinarySearch
{
 public static int binarySearch(int[] arr, int target)
 {
 int left = 0; 
 int right = array.length - 1;
 while (left <= right)
 {
 int mid = (left + right) / 2;
 if (target == array[mid]) {
 return mid;
 }
 // code to run if `target` is greater or lesser than `array[mid]`
 }
 return -1;
 }
}

The iterative binarySearch() algorithm is implemented with the following steps:

• Accepts a sorted array and target value as parameters
• Sets a left integer to 0 and right integer to arr.length
• Executes a while loop as long as right is greater than left
• Inside the while loop, finds the value in the array at the middle index, equal to the average of left and right
• If the current mid-value equals the target value, return the middle index
• If the target value is greater than the value being checked, set left equal to the middle index + 1
• If the target value is less than the value being checked, set right equal to the middle index
• Outside of the while loop, return -1

public class BinarySearch {
 public static int search(int[] arr, int target) {
 int left = 0;
 int right = arr.length;
 while (left < right) {
 int mid = Math.floorDiv(left + right, 2);
 int midValue = arr[mid];
 if (midValue == target) {
 return mid;
 } else if (midValue < target) {
 left = mid + 1;
 } else {
 right = mid;
 }
 }
 return -1;
 }
}

Linear search can be used to search for the smallest or largest value in an unsorted list rather than searching for a match. It can do so by keeping track of the largest (or smallest) value and updating as necessary as the algorithm iterates through the dataset.

Create a variable called max_value_index Set max_value_index to the index of the first element of the search list For each element in the search list if element is greater than the element at max_value_index Set max_value_index equal to the index of the elementreturn max_value_index

Linear search runs in linear time and makes a maximum of n comparisons, where n is the length of the list. Hence, the computational complexity for linear search is O(N).

The running time increases, at most, linearly with the size of the items present in the list.

A linear search can be expressed as a function that compares each item of the passed dataset with the target value until a match is found.

The given pseudocode block demonstrates a function that performs a linear search. The relevant index is returned if the target is found and -1 with a message that a value is not found if it is not.

For each element in the array if element equal target value then return its index if element is not found, return “Value Not Found” message

A function that performs a linear search can return a message of success and the index of the matched value if the search can successfully match the target with an element of the dataset. In the event of a failure, a message as well as -1 is returned as well.

For each element in the array if element equal target value then print success message return its index if element is not found print Value not found message return -1

A linear search can be modified so that all instances in which the target is found are returned. This change can be made by not ‘breaking’ when a match is found.

For each element in the searchList if element equal target value then Add its index to a list of occurrencesif the list of occurrences is empty raise ValueErrorotherwise return the list occurrences

Linear search sequentially checks each element of a given list for the target value until a match is found. If no match is found, a linear search would perform the search on all of the items in the list.

For instance, if there are n number of items in a list, and the target value resides in the n-5th position, a linear search will check n-5 items total.