Searching and Sorting Algorithms Summary elect C chap 6

Searching Algorithms

  • Searching involves finding a target value within a dataset (list/array).
  • Efficiency depends on whether the list is sorted or unsorted.

Linear Search

  • Simplest method: sequentially checks each element from the beginning until the target is found or the end of the list is reached.
  • Commonly used for unsorted lists.
  • Efficiency can be improved using a whilewhile loop that terminates upon finding the target.
  • Can be modified to output the index of the target value if found, or a message if not found.
  • Number of evaluations required: depends on the position of the target value in the list or if it's not present.

Binary Search

  • Applicable only to sorted lists.
  • Involves comparing the target value with the middle item of the list.
  • If a mismatch occurs, the search range is halved based on whether the target is greater or smaller than the middle item.
  • Efficiency: the search range is halved after each comparison.
  • Worst-case scenario: target is the last item or doesn't exist.
  • Maximum number of iterations for a binary search of NN items in the worst case: log2Nlog_2 N.

Comparison of Search Algorithms

  • Linear Search: Simpler but less efficient for large lists.
  • Binary Search: More efficient for large, sorted lists due to its divide-and-conquer approach.

Swapping

  • Involves exchanging the values of two variables using a temporary variable.
  • Example: temp=A,A=B,B=temptemp = A, A = B, B = temp

Sorting Algorithms

  • Arranging data in ascending or descending order.
  • Essential for binary search and data organization.

Selection Sort

  • Based on linear search to find the minimum or maximum value in the unsorted part of the list.
  • Swaps the found value with the first item of the unsorted list.
  • Repeats the process until the entire list is sorted.
  • Number of comparisons for selection sort: For N items, N(N−1)2\frac{N(N-1)}{2}.

Insertion Sort

  • Divides the list into sorted and unsorted parts.
  • Inserts the first item from the unsorted part into its correct position in the sorted part.
  • Repeats until all items are sorted.
  • Best case: list is already in sorted order.
  • Worst case: list is in reverse sorted order.

Bubble Sort

  • Compares adjacent items and swaps them if they are in the wrong order.
  • After each pass, the smallest element "bubbles" to its correct position at the end.
  • Repeats until the entire list is sorted.
  • Number of comparisons: N(N−1)2\frac{N(N-1)}{2}.

Merging Two Sorted Lists

  • Combines two sorted lists into a single sorted list.
  • Compares the first unmerged elements of both lists and copies the smaller element to the merged list.
  • Repeats until all elements are merged.

Other Sorting Algorithms:

  • Faster algorithms exist: Merge sort and Quick sort.

Efficiency Comparison of Sorting Algorithms:

  • Selection Sort, Insertion Sort, and Bubble Sort require more comparisons than Merge Sort, and Quick Sort with the increase in list length (NN).