Algorithm Design and Problem-Solving

This section explores fundamental algorithms used to solve computational problems. We will cover linear search, bubble sort, and their applications.

Standard Search Algorithms

Linear Search

Linear search is the simplest search algorithm. It involves examining each element in a list sequentially until the target element is found or the end of the list is reached.

How it works:

1. Start at the beginning of the list.
2. Compare the current element with the target value.
3. If the current element matches the target value, the search is successful.
4. If the current element does not match the target value, move to the next element in the list.
5. Repeat step 2 and 3 until the target value is found or the end of the list is reached. If the end of the list is reached without finding the target value, the search is unsuccessful.

Pseudocode:

function linearSearch(list, target):
  for each element in list:
    if element == target:
      return "Target found at index" + index of element
  return "Target not found"

Example:

Consider the list: [5, 2, 9, 1, 5, 6] and the target value 9.

The algorithm will compare 5, then 2, then 9. When it reaches 9, it will return "Target found at index 2".

Efficiency:

• Best Case: The target is the first element in the list. Time complexity: O(1)
• Worst Case: The target is the last element in the list or not present. Time complexity: O(n), where n is the number of elements in the list.
• Average Case: O(n)

Binary Search

Binary search is a more efficient search algorithm that works on sorted lists. It repeatedly divides the search interval in half.

How it works:

1. Start with the entire sorted list.
2. Find the middle element of the list.
3. Compare the middle element with the target value.
4. If the middle element matches the target value, the search is successful.
5. If the target value is less than the middle element, search the left half of the list.
6. If the target value is greater than the middle element, search the right half of the list.
7. Repeat steps 2-4 until the target value is found or the search interval is empty.

Pseudocode:

function binarySearch(list, target):
  low = 0
  high = length of list - 1
  while low <= high:
    mid = (low + high) / 2
    if list[mid] == target:
      return "Target found at index" + mid
    else if list[mid] < target:
      low = mid + 1
    else:
      high = mid - 1
  return "Target not found"

Example:

Consider the sorted list: [1, 2, 5, 9, 10] and the target value 5.

The algorithm will first check the middle element (which is 5). Since it matches the target, the search is successful.

Efficiency:

• Best Case: The target is the middle element in the list. Time complexity: O(1)
• Worst Case: The target is not in the list or is at one of the extreme ends. Time complexity: O(log n)
• Average Case: O(log n)

Standard Sort Algorithms

Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The largest element "bubbles" to the end of the list with each pass.

How it works:

1. Start at the beginning of the list.
2. Compare the first two elements. If the first element is greater than the second element, swap them.
3. Move to the next pair of elements and repeat step 2.
4. Continue this process until the end of the list is reached.
5. Repeat steps 1-4 for the remaining unsorted elements.

Pseudocode:

function bubbleSort(list):
  n = length of list
  for i = 0 to n - 2:
    for j = 0 to n - i - 2:
      if list[j] > list[j + 1]:
        swap list[j] and list[j + 1]

Example:

Consider the list: [5, 1, 4, 2, 8].

After the first pass, the largest element (8) will be at the end: [5, 1, 4, 2, 8] becomes [1, 4, 2, 5, 8].

After the second pass, the second largest element (5) will be in its correct position: [1, 4, 2, 5, 8] becomes [1, 4, 2, 5, 8].

Efficiency:

• Best Case: The list is already sorted. Time complexity: O(n)
• Worst Case: The list is sorted in reverse order. Time complexity: O(n2)
• Average Case: O(n2)

Selection Sort

Selection sort finds the minimum element in the unsorted portion of the list and places it at the beginning.

How it works:

1. Find the minimum element in the unsorted portion of the list.
2. Swap the minimum element with the first element of the unsorted portion.
3. Move to the next unsorted portion of the list and repeat step 1 and 2.

Efficiency:

• Best Case: The list is already sorted. Time complexity: O(n2)
• Worst Case: The list is sorted in reverse order. Time complexity: O(n2)
• Average Case: O(n2)

Insertion Sort

Insertion sort builds the final sorted list one item at a time. It iterates through the input list, picking an element and inserting it into its correct position in the already sorted portion of the list.

Efficiency:

• Best Case: The list is already sorted. Time complexity: O(n)
• Worst Case: The list is sorted in reverse order. Time complexity: O(n2)
• Average Case: O(n2)

Algorithm	Best Case	Worst Case	Average Case
Linear Search	O(1)	O(n)	O(n)
Binary Search	O(1)	O(log n)	O(log n)
Bubble Sort	O(n)	O(n2)	O(n2)
Selection Sort	O(n2)	O(n2)	O(n2)
Insertion Sort	O(n)	O(n2)	O(n2)